《算法案例輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法與進位制第一課時課件-數(shù)學高一必修3第一章算法初步1.3人教A版.ppt》由會員分享，可在線閱讀，更多相關(guān)《算法案例輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法與進位制第一課時課件-數(shù)學高一必修3第一章算法初步1.3人教A版.ppt（48頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第一章 算法初步 1.3 算法案例 （輾轉(zhuǎn)相除法與更相減損術(shù) ,秦九韶算法與進位制） 1.理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法 . 2.理解秦九韶算法中求多項式的值的步驟原理 . 3.能利用除 k 取余法把十進制數(shù)化為 k 進制數(shù) . 1.輾轉(zhuǎn)相除法的算法步驟 第一步，給定兩個正整數(shù) m， n(mn). 第二步，計算 ________除以 ________所得的 ______數(shù) r. 第三步， m n， n r. 第四步，若 r 0，則 m， n 的最大公約數(shù)等于 ______；否 則，返回第二步 . m n 余 n 2.更相減損術(shù)的算法步驟 第一步，任意給定兩個正整數(shù)，判斷它們是否都
2、是偶數(shù) .若 是用 2 約簡；若不是，執(zhí)行第二步 . 第二步，以較大的數(shù)減去較 小的數(shù)，接著把所得的差與 ________比較，并以大數(shù)減小數(shù) .繼續(xù)這個操作，直到所得的數(shù) ________為止，則這個數(shù) (等數(shù) )或這個數(shù)與約簡的數(shù)的乘積就 是所求的最大公約數(shù) . 較小的數(shù) 相等 3.秦九韶算法 把一個 n次多項式 f(x) anxn an 1xn 1 a1x a0改寫 成如下形式： (anxn 1 an 1xn 2 a1)x a0 f(x) anxn an 1xn 1 a1x a0 _____________________________ (anxn 2 an 1xn 3 a2)x a1
3、)x a0 _____________________________________. ( (anx an 1)x an 2)x a1)x a0 求多項式的值時，首先計算最內(nèi)層括號內(nèi)的一次多項式的 值，即 v1 anx an 1，然后由內(nèi)向外逐層計算一次多項式的值， 即： n 這樣，求 n 次多項式 f(x)的值就轉(zhuǎn)化為求 ______個一次多項 式的值 . v1 anx an 1， v2 ____________， v3 v2x an 3， vn ____________， v1x an 2 vn 1x a0 4.進位制 (1)k進制數(shù) anan 1 a1a0(k)轉(zhuǎn)化為十進制數(shù)為 ___
4、__________________________________. (2)把十進制數(shù)化為 k 進制數(shù)用“ ____________”，即把所給 的十進制數(shù)除以 ________，得到商數(shù)和余數(shù)，再用商數(shù)除以 k， 得到商數(shù)和余數(shù)，直到商數(shù)為 ________ ，把上面各步所得的 ________從右到左排列，即得到 k 進制數(shù) . 除 k 取余 法 k 0 余數(shù) ankn an 1kn 1 a1k a0 【 問題導思 】 1如何求 18與 54的最大公約數(shù)？ 【 提示 】 短除法 2 要求 6 750與 3 492的最大公約數(shù)，上述法還好用嗎？ 【 提示 】 數(shù)值太大，短除法不方便用 知識
5、 1 求兩個正整數(shù)最大公約數(shù)的算法 (1)更相減損之術(shù) (等值算法 ) 用兩個數(shù)中較大的數(shù)減去較小的數(shù)，再用 和 構(gòu)成新的一對數(shù)，對這一對數(shù)再用 減 ，以同樣的操作一直做下去，直 到產(chǎn)生 ，這個數(shù)就是最大公約數(shù) (2)輾轉(zhuǎn)相除法 (歐幾里得算法 ) 用較大的數(shù)除以較小的數(shù)所得的 和 __________構(gòu)成新的一對數(shù)，繼續(xù)做上面的除法，直到 ，這個較小的數(shù)就是最大公約數(shù) . 差數(shù) 較小的數(shù) 大 數(shù) 小數(shù) 一對相等的數(shù) 余數(shù) 較小的數(shù) 大數(shù)被小數(shù)除盡 【 問題導思 】 1怎樣計算多項式 f(x) x5 x4 x3 x2 x 1當 x 5時 的值呢？統(tǒng)計所做的計算的種類及計算次數(shù)分別是什么？ 【
6、提示 】 f(5) 55 54 53 52 5 1 3 906.根據(jù)我 們的計算統(tǒng)計可以得出我們共需要 10次乘法運算， 5次加法 運算 知識 2 秦九韶算法 2我們把多項式變形為 f(x) x2(1 x(1 x(1 x) x 1， 再統(tǒng)計一下計算當 x 5時的計算的種類及計算次數(shù)分別是什 么？ 【 提示 】 從里往外計算僅需 4次乘法和 5次加法運算即 可得出結(jié)果 (1)把一元 n次多項式 P(x) anxn an 1xn 1 a1x a0 改寫為 P(x) anxn an 1xn 1 a1x a0 (anxn 1 an 1xn 2 a1)x a0 (anxn 2 an 1xn 3 a2)x
7、 a1)x a0 ( (anx an 1)x an 2)x a1)x a0， 令 vk ( (anx an 1)x an (k 1)x an k， 則遞推公式為 v 0 a n v k v k 1 x a n k 其中 k 1 ， 2 ， ， n. (2)計算 P(x0)的方法 先計算 ，然后 逐層計算， 直到 ，然后加上 最內(nèi)層括號 由內(nèi)向外 最外層括號 常數(shù)項 知識 3 進位制 進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示 不同的數(shù)值 .使用數(shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為 n，即稱為 n 進位制，簡稱 n 進制 .現(xiàn)在最常用的是十進制，通常使用 10 個 阿拉伯數(shù)字 0 9 進行記數(shù)
8、 . 例 1 .分別用輾轉(zhuǎn)相除法和等值算法求 319和 261的最大公 約數(shù) 【 分析 】 使用輾轉(zhuǎn)相除法可依據(jù) m nq r，反復(fù)執(zhí)行， 直到 r 0為止；用等值算法是根據(jù) m n r，直到 n 1為 止 【 解析 】 輾轉(zhuǎn)相除法： 319 261 1(余 58)， 261 58 4(余 29)， 58 29 2(余 0) 所以 319與 261的最大公約數(shù)是 29. 等值算法： 319 261 58， 261 58 203， 203 58 145， 145 58 87， 87 58 29， 58 29 29. 即 (319， 261)(261， 58)(203， 58)(145， 58)(
9、87， 58)(58， 29)(29， 29) 所以 319與 261的最大公約數(shù)是 29. 1利用 “ 等值算法 ” 求給定的兩個數(shù)的最大公約數(shù)， 即多次利用減法，用數(shù)對中較大的數(shù)減去較小的數(shù)，直到相 減的差與數(shù)對中較小的數(shù)相等為止 2更相減損之術(shù)的步驟： (1)判斷兩數(shù)是否都為偶數(shù)，若是，則都除以 2直到所得 兩數(shù)不全為偶數(shù) (2)用較大的數(shù)減去較小的數(shù)，將差和較小的數(shù)構(gòu)成一對 新數(shù)，繼續(xù)用較大數(shù)減去較小數(shù)，重復(fù)執(zhí)行 (3)當差和較小數(shù)相等時，結(jié)束執(zhí)行，此時差 (或較小數(shù) ) 為不全為偶數(shù)的兩數(shù)的最大公約數(shù) 用 “ 等值算法 ” (更相減損之術(shù) )求下列兩數(shù)的最大公約 數(shù) (1)98， 2
10、80； (2)72， 168. 【 解 】 (1)(98， 280)(98， 182)(98， 84)(14， 84)(14， 70)(14， 56)(14， 42)(14， 28)(14， 14) 最大公約數(shù)為 14. (2)(72， 168)(72， 96)(72， 24)(48， 24)(24， 24) 最大公約數(shù)為 24. 例 2. 用秦九韶算法計算多項式 f(x) x6 12x5 60 x4 160 x3 240 x2 192x 64當 x 2時的值 【 分析 】 改寫多項式 確定 v 0 依次計算 v i 求 f （ 2 ） 【 解析 】 將 f(x)改寫為 f(x) (x 12)
11、x 60)x 160)x 240)x 192)x 64， 由內(nèi)向外依次計算一次多項式當 x 2時的值 v0 1， v1 1 2 12 10， v2 10 2 60 40， v3 40 2 160 80， v4 80 2 240 80， v5 80 2 192 32， v6 32 2 64 0. f(2) 0，即 x 2時，原多項式的值為 0. 1用秦九韶算法計算多項式的值時，要正確將多項式 的形式進行改寫，然后由內(nèi)向外依次計算當多項式函數(shù)中 間出現(xiàn)空項式，要以系數(shù)為零的齊次項補充 2秦九韶算法的步驟： 【 變式訓練 】 利用秦九韶算法計算多項式 f(x) 11 5x 3x2 7x3 在 x 2
12、3 的值時，不會用到下列哪個值 ( ) D A.161 B.3772 C.86 641 D.85 169 解析： f(x) 11 5x 3x2 7x3 (7x 3)x 5x 11. 所以當 x 23時， v0 7； v1 7 23 3 161 3 164； v2 164 23 5 3772 5 3767； v3 3767 23 11 86 641 11 86 652. 例 3. 求 324， 243， 270三數(shù)的最大公約數(shù) 【 分析 】 先求 324和 243的最大公約數(shù)，再求這個數(shù)與 270的最大公約數(shù) 【 解析 】 (324， 243)(243， 81)(162， 81)(81， 81)
13、 則 324與 243的最大公約數(shù)為 81. 又 (270， 81)(189， 81)(108， 81)(81， 27)(54， 27)(27， 27) 則 270與 81的最大公約數(shù)為 27， 故 324， 243， 270三數(shù)的最大公約數(shù)為 27. 求三個數(shù)的最大公約數(shù)，可先求兩個數(shù)的最大公約數(shù) a， 再求 a與第三個數(shù)的最大公約數(shù) b，則 b為所求的三個數(shù)的最 大公約數(shù)該題的解法可推廣到求 n個數(shù)的最大公約數(shù) 用更相減損之術(shù)求 27 090， 21 672， 8 127的最大公約 數(shù) 【 解 】 先求 27 090與 21 672的最大公約數(shù) (27 090， 21 672)(21 67
14、2， 5 418)(16 254， 5 418)(10 836， 5 418)(5 418， 5 418) 27 090與 21 672的最大公約數(shù)是 5 418. 再求 5 418與 8 127的最大公約數(shù) (8 127， 5 418)(2 709， 5 418)(2 709， 2 709) 5 418與 8 127的最大公約數(shù)為 2 709. 27 090， 21 672， 8 172的最大公約數(shù)為 2 709. 類型 4 進制數(shù) 之間的轉(zhuǎn)化 例 4.(1)將 101 111 011(2)轉(zhuǎn)化為十進制數(shù)； (2)將 1231(5)轉(zhuǎn)化為七進制數(shù) . 【 分析 】 k進制數(shù) anan 1 a
15、2a1a0(k)(0aik)轉(zhuǎn)化為十進制數(shù)： anan 1 a2a1a0(k) an kn an 1 kn 1 a2 k2 a1 k a0 1.要將 k進制數(shù)轉(zhuǎn)化為 n進制數(shù) (n， k10)， 可先將 k 進制 數(shù)轉(zhuǎn)化為十進制數(shù) ， 然后再轉(zhuǎn)化為所求的 n進制數(shù) . 【 解析 】 (1)101 111 011(2) 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379(10). (2)1231(5) 1 53 2 52 3 5 1 191(10)， 1231(5) 362(7). 【 變式訓練 】 3.填空： 248 130 (1)11 111 0
16、00(2) ________(10)； (2)154(6) ________(7). 名稱 輾轉(zhuǎn)相除法 更相減損術(shù) 區(qū)別 以除法為主 兩個整數(shù)的差較大 時，運算次數(shù)減少 余數(shù)為 0 時結(jié)束 以減法為主 兩個整數(shù)的差較大時， 運算次數(shù)多 兩數(shù)相等時結(jié)束 聯(lián)系 都是求最大公約數(shù)的方法 都用到遞推方法 都用循環(huán)結(jié)構(gòu)來實現(xiàn) 1.輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的區(qū)別與聯(lián)系 . 2.秦九韶算法的優(yōu)點 . (1)減少乘法運算的次數(shù) . (2)規(guī)律性強，便于利用循環(huán)語句實現(xiàn) . (3)不用對 x 做冪的運算，每 次都是計算一個一次多項式的 值，提高了計算精度 . 3.進位制 對于任何一個數(shù)，我們可以用不同
17、的進位制來表示 .比如： 十進數(shù) 57，可以用二進制表示為 111 001，也可以用八進制表 示為 71，用十六進制表示為 39，它們所代表的數(shù)值都是一樣的 . 表示各種進制數(shù)時，一般要在數(shù)字右下角加注來表示 .如 111 001(2)表示二進制數(shù)， 34(5)表示五進制數(shù) .電子計算機一般都 使用二進制 . 1 用更相減損之術(shù)可求得 78與 36的最大公約數(shù)是 ( ) A 24 B 18 C 12 D 6 【 解析 】 78 36 42， 42 36 6， 36 6 30， 30 6 24， 24 6 18， 18 6 12， 12 6 6， 6為 78與 36的 最大公約數(shù) 【 答案 】
18、D 2用秦九韶算法計算 f(x) 6x5 4x4 x3 2x2 x3 2x2 9x，需要加法 (或減法 )與乘法運算的次數(shù)分別為 ( ) A 5， 4 B 5， 5 C 4， 4 D 4， 5 【 解析 】 n次多項式當最高次項的系數(shù)不為 1時，需進 行 n次乘法；若各項均不為零，則需進行 n次加法，缺一項就 減少一次加法運算 f(x)中無常數(shù)項，故加法次數(shù)要減少一次， 為 5 1 4. 【 答案 】 D 3用更相減損之術(shù)求 81與 135的最大公約數(shù)時，要進行 ________次減法運算 【 解析 】 135 81 54， 81 54 27， 54 27 27， 共進行了 3次減法運算 【
19、答案 】 3 4.將二進制數(shù) 101 101(2)化為八進制數(shù)，結(jié)果為 ________ 【 解析 】 101 101(2) 1 25 0 24 1 23 1 22 0 2 1 32 8 4 1 45. 101 101(2) 55(8) 【 答案 】 55(8) 5求當 x 2時， f(x) x5 5x4 x3 1的函數(shù)值 【 解 】 f(x) x5 5x4 x3 1 (x 5)x 1)x 0)x 0)x 1，利用公式有 v0 1， v1 1 2 5 3， v2 ( 3) 2 1 5， v3 ( 5) 2 0 10， v4 ( 10) 2 0 20， v5 ( 20) 2 1 41， f(2) 41.
算法案例輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法與進位制第一課時課件-數(shù)學高一必修3第一章算法初步1.3人教A版.ppt
