《算法案例輾轉(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.理解秦九韶算法中求多項(xiàng)式的值的步驟原理 . 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ù)，判斷它們是否都是偶數(shù) .若 是用 2 約簡；若不是，執(zhí)行第二步

2、 . 第二步，以較大的數(shù)減去較 小的數(shù)，接著把所得的差與 _比較，并以大數(shù)減小數(shù) .繼續(xù)這個操作，直到所得的數(shù) _為止，則這個數(shù) (等數(shù) )或這個數(shù)與約簡的數(shù)的乘積就 是所求的最大公約數(shù) . 較小的數(shù) 相等 3.秦九韶算法 把一個 n次多項(xiàng)式 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)x a0 _. ( (anx an 1)x an 2)x a1)x a0 求多項(xiàng)式的值時，首先計算最內(nèi)層括號內(nèi)的一次多項(xiàng)式的 值，

3、即 v1 anx an 1，然后由內(nèi)向外逐層計算一次多項(xiàng)式的值， 即： n 這樣，求 n 次多項(xiàng)式 f(x)的值就轉(zhuǎn)化為求 _個一次多項(xiàng) 式的值 . 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ù)為 _. (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

4、1 a1k a0 【 問題導(dǎo)思 】 1如何求 18與 54的最大公約數(shù)？ 【 提示 】 短除法 2 要求 6 750與 3 492的最大公約數(shù)，上述法還好用嗎？ 【 提示 】 數(shù)值太大，短除法不方便用 知識 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ù) 一對

5、相等的數(shù) 余數(shù) 較小的數(shù) 大數(shù)被小數(shù)除盡 【 問題導(dǎo)思 】 1怎樣計算多項(xiàng)式 f(x) x5 x4 x3 x2 x 1當(dāng) x 5時 的值呢？統(tǒng)計所做的計算的種類及計算次數(shù)分別是什么？ 【 提示 】 f(5) 55 54 53 52 5 1 3 906.根據(jù)我 們的計算統(tǒng)計可以得出我們共需要 10次乘法運(yùn)算， 5次加法 運(yùn)算 知識 2 秦九韶算法 2我們把多項(xiàng)式變形為 f(x) x2(1 x(1 x(1 x) x 1， 再統(tǒng)計一下計算當(dāng) x 5時的計算的種類及計算次數(shù)分別是什 么？ 【 提示 】 從里往外計算僅需 4次乘法和 5次加法運(yùn)算即 可得出結(jié)果 (1)把一元 n次多項(xiàng)式 P(x) anx

6、n 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 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ù)項(xiàng) 知識 3 進(jìn)位制 進(jìn)位制是一種記數(shù)方式，用有

7、限的數(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ù) . 例 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， 2

8、61 58 203， 203 58 145， 145 58 87， 87 58 29， 58 29 29. 即 (319， 261)(261， 58)(203， 58)(145， 58)(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ù)減去較小

9、數(shù)，重復(fù)執(zhí)行 (3)當(dāng)差和較小數(shù)相等時，結(jié)束執(zhí)行，此時差 (或較小數(shù) ) 為不全為偶數(shù)的兩數(shù)的最大公約數(shù) 用 “ 等值算法 ” (更相減損之術(shù) )求下列兩數(shù)的最大公約 數(shù) (1)98， 280； (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. 用秦九韶算法計算多項(xiàng)式 f(x) x6 12x5 60 x4 160

10、 x3 240 x2 192x 64當(dāng) x 2時的值 【 分析 】 改寫多項(xiàng)式 確定 v 0 依次計算 v i 求 f （ 2 ） 【 解析 】 將 f(x)改寫為 f(x) (x 12)x 60)x 160)x 240)x 192)x 64， 由內(nèi)向外依次計算一次多項(xiàng)式當(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時，原多項(xiàng)式的值為 0. 1用秦九韶算法計算多項(xiàng)式的值時，要正確將多項(xiàng)式 的形式進(jìn)行改寫，然

11、后由內(nèi)向外依次計算當(dāng)多項(xiàng)式函數(shù)中 間出現(xiàn)空項(xiàng)式，要以系數(shù)為零的齊次項(xiàng)補(bǔ)充 2秦九韶算法的步驟： 【 變式訓(xùn)練 】 利用秦九韶算法計算多項(xiàng)式 f(x) 11 5x 3x2 7x3 在 x 23 的值時，不會用到下列哪個值 ( ) 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

12、三數(shù)的最大公約數(shù) 【 分析 】 先求 324和 243的最大公約數(shù)，再求這個數(shù)與 270的最大公約數(shù) 【 解析 】 (324， 243)(243， 81)(162， 81)(81， 81) 則 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ù)的最大

13、公約數(shù) 用更相減損之術(shù)求 27 090， 21 672， 8 127的最大公約 數(shù) 【 解 】 先求 27 090與 21 672的最大公約數(shù) (27 090， 21 672)(21 672， 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

14、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 a2a1a0(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 3

15、79(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 000(2) _(10)； (2)154(6) _(7). 名稱 輾轉(zhuǎn)相除法 更相減損術(shù) 區(qū)別 以除法為主 兩個整數(shù)的差較大 時，運(yùn)算次數(shù)減少 余數(shù)為 0 時結(jié)束 以減法為主 兩個整數(shù)的差較大時， 運(yùn)算次數(shù)多 兩數(shù)相等時結(jié)束 聯(lián)系 都是求最大公約數(shù)的方法 都用到遞推方法 都用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn) 1.輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的區(qū)別與聯(lián)系 . 2.秦九韶算法的優(yōu)點(diǎn) . (1)減少乘法運(yùn)算的次數(shù) . (2)規(guī)律

16、性強(qiáng)，便于利用循環(huán)語句實(shí)現(xiàn) . (3)不用對 x 做冪的運(yùn)算，每 次都是計算一個一次多項(xiàng)式的 值，提高了計算精度 . 3.進(jìn)位制 對于任何一個數(shù)，我們可以用不同的進(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 4

17、2， 42 36 6， 36 6 30， 30 6 24， 24 6 18， 18 6 12， 12 6 6， 6為 78與 36的 最大公約數(shù) 【 答案 】 D 2用秦九韶算法計算 f(x) 6x5 4x4 x3 2x2 x3 2x2 9x，需要加法 (或減法 )與乘法運(yùn)算的次數(shù)分別為 ( ) A 5， 4 B 5， 5 C 4， 4 D 4， 5 【 解析 】 n次多項(xiàng)式當(dāng)最高次項(xiàng)的系數(shù)不為 1時，需進(jìn) 行 n次乘法；若各項(xiàng)均不為零，則需進(jìn)行 n次加法，缺一項(xiàng)就 減少一次加法運(yùn)算 f(x)中無常數(shù)項(xiàng)，故加法次數(shù)要減少一次， 為 5 1 4. 【 答案 】 D 3用更相減損之術(shù)求 81與 1

18、35的最大公約數(shù)時，要進(jìn)行 _次減法運(yùn)算 【 解析 】 135 81 54， 81 54 27， 54 27 27， 共進(jìn)行了 3次減法運(yùn)算 【 答案 】 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.