《算法案例輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法與進(jìn)位制第一課時課件-數(shù)學(xué)高一必修3第一章算法初步1.3人教A版.ppt》由會員分享，可在線閱讀，更多相關(guān)《算法案例輾轉(zhuǎn)相除法與更相減損術(shù)秦九韶算法與進(jìn)位制第一課時課件-數(shù)學(xué)高一必修3第一章算法初步1.3人教A版.ppt（48頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第一章 算法初步 1.3 算法案例 （輾轉(zhuǎn)相除法與更相減損術(shù) ,秦九韶算法與進(jìn)位制） 1.理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法 . 2.理解秦九韶算法中求多項式的值的步驟原理 . 3.能利用除 k 取余法把十進(jìn)制數(shù)化為 k 進(jìn)制數(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.進(jìn)位制 (1)k進(jìn)制數(shù) anan 1 a1a0(k)轉(zhuǎn)化為十進(jìn)制數(shù)為 ___
4、__________________________________. (2)把十進(jìn)制數(shù)化為 k 進(jìn)制數(shù)用“ ____________”，即把所給 的十進(jìn)制數(shù)除以 ________，得到商數(shù)和余數(shù)，再用商數(shù)除以 k， 得到商數(shù)和余數(shù)，直到商數(shù)為 ________ ，把上面各步所得的 ________從右到左排列，即得到 k 進(jìn)制數(shù) . 除 k 取余 法 k 0 余數(shù) ankn an 1kn 1 a1k a0 【 問題導(dǎo)思 】 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ù)除盡 【 問題導(dǎo)思 】 1怎樣計算多項式 f(x) x5 x4 x3 x2 x 1當(dāng) 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)計一下計算當(dā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 進(jìn)位制 進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示 不同的數(shù)值 .使用數(shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為 n，即稱為 n 進(jìn)位制，簡稱 n 進(jìn)制 .現(xiàn)在最常用的是十進(jìn)制，通常使用 10 個 阿拉伯?dāng)?shù)字 0 9 進(jìn)行記數(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)當(dāng)差和較小數(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當(dāng) 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)向外依次計算一次多項式當(dāng) 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用秦九韶算法計算多項式的值時，要正確將多項式 的形式進(jìn)行改寫，然后由內(nèi)向外依次計算當(dāng)多項式函數(shù)中 間出現(xiàn)空項式，要以系數(shù)為零的齊次項補充 2秦九韶算法的步驟： 【 變式訓(xùn)練 】 利用秦九韶算法計算多項式 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. 所以當(dāng) 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 進(jìn)制數(shù) 之間的轉(zhuǎn)化 例 4.(1)將 101 111 011(2)轉(zhuǎn)化為十進(jìn)制數(shù)； (2)將 1231(5)轉(zhuǎn)化為七進(jìn)制數(shù) . 【 分析 】 k進(jìn)制數(shù) anan 1 a
15、2a1a0(k)(0aik)轉(zhuǎn)化為十進(jìn)制數(shù)： anan 1 a2a1a0(k) an kn an 1 kn 1 a2 k2 a1 k a0 1.要將 k進(jìn)制數(shù)轉(zhuǎn)化為 n進(jìn)制數(shù) (n， k10)， 可先將 k 進(jìn)制 數(shù)轉(zhuǎn)化為十進(jìn)制數(shù) ， 然后再轉(zhuǎn)化為所求的 n進(jì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). 【 變式訓(xùn)練 】 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ī)律性強(qiáng)，便于利用循環(huán)語句實現(xiàn) . (3)不用對 x 做冪的運算，每 次都是計算一個一次多項式的 值，提高了計算精度 . 3.進(jìn)位制 對于任何一個數(shù)，我們可以用不同
17、的進(jìn)位制來表示 .比如： 十進(jìn)數(shù) 57，可以用二進(jìn)制表示為 111 001，也可以用八進(jìn)制表 示為 71，用十六進(jìn)制表示為 39，它們所代表的數(shù)值都是一樣的 . 表示各種進(jìn)制數(shù)時，一般要在數(shù)字右下角加注來表示 .如 111 001(2)表示二進(jìn)制數(shù)， 34(5)表示五進(jìn)制數(shù) .電子計算機(jī)一般都 使用二進(jìn)制 . 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次多項式當(dāng)最高次項的系數(shù)不為 1時，需進(jìn) 行 n次乘法；若各項均不為零，則需進(jìn)行 n次加法，缺一項就 減少一次加法運算 f(x)中無常數(shù)項，故加法次數(shù)要減少一次， 為 5 1 4. 【 答案 】 D 3用更相減損之術(shù)求 81與 135的最大公約數(shù)時，要進(jìn)行 ________次減法運算 【 解析 】 135 81 54， 81 54 27， 54 27 27， 共進(jìn)行了 3次減法運算 【
19、答案 】 3 4.將二進(jìn)制數(shù) 101 101(2)化為八進(jìn)制數(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求當(dāng) 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ù)秦九韶算法與進(jìn)位制第一課時課件-數(shù)學(xué)高一必修3第一章算法初步1.3人教A版.ppt
