第一章 算法初步 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)相除法的算法步驟 第一步，給定兩個(gè)正整數(shù) m， n(mn). 第二步，計(jì)算 _除以 _所得的 _數(shù) r. 第三步， m n， n r. 第四步，若 r 0，則 m， n 的最大公約數(shù)等于 _；否 則，返回第二步 . m n 余 n 2.更相減損術(shù)的算法步驟 第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù) .若 是用 2 約簡；若不是，執(zhí)行第二步 . 第二步，以較大的數(shù)減去較 小的數(shù)，接著把所得的差與 _比較，并以大數(shù)減小數(shù) .繼續(xù)這個(gè)操作，直到所得的數(shù) _為止，則這個(gè)數(shù) (等數(shù) )或這個(gè)數(shù)與約簡的數(shù)的乘積就 是所求的最大公約數(shù) . 較小的數(shù) 相等 3.秦九韶算法 把一個(gè) 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)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)的一次多項(xiàng)式的 值，即 v1 anx an 1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值， 即： n 這樣，求 n 次多項(xiàng)式 f(x)的值就轉(zhuǎn)化為求 _個(gè)一次多項(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 1 a1k a0 【 問題導(dǎo)思 】 1如何求 18與 54的最大公約數(shù)？ 【 提示 】 短除法 2 要求 6 750與 3 492的最大公約數(shù)，上述法還好用嗎？ 【 提示 】 數(shù)值太大，短除法不方便用 知識(shí) 1 求兩個(gè)正整數(shù)最大公約數(shù)的算法 (1)更相減損之術(shù) (等值算法 ) 用兩個(gè)數(shù)中較大的數(shù)減去較小的數(shù)，再用 和 構(gòu)成新的一對(duì)數(shù)，對(duì)這一對(duì)數(shù)再用 減 ，以同樣的操作一直做下去，直 到產(chǎn)生 ，這個(gè)數(shù)就是最大公約數(shù) (2)輾轉(zhuǎn)相除法 (歐幾里得算法 ) 用較大的數(shù)除以較小的數(shù)所得的 和 _構(gòu)成新的一對(duì)數(shù)，繼續(xù)做上面的除法，直到 ，這個(gè)較小的數(shù)就是最大公約數(shù) . 差數(shù) 較小的數(shù) 大 數(shù) 小數(shù) 一對(duì)相等的數(shù) 余數(shù) 較小的數(shù) 大數(shù)被小數(shù)除盡 【 問題導(dǎo)思 】 1怎樣計(jì)算多項(xiàng)式 f(x) x5 x4 x3 x2 x 1當(dāng) x 5時(shí) 的值呢？統(tǒng)計(jì)所做的計(jì)算的種類及計(jì)算次數(shù)分別是什么？ 【 提示 】 f(5) 55 54 53 52 5 1 3 906.根據(jù)我 們的計(jì)算統(tǒng)計(jì)可以得出我們共需要 10次乘法運(yùn)算， 5次加法 運(yùn)算 知識(shí) 2 秦九韶算法 2我們把多項(xiàng)式變形為 f(x) x2(1 x(1 x(1 x) x 1， 再統(tǒng)計(jì)一下計(jì)算當(dāng) x 5時(shí)的計(jì)算的種類及計(jì)算次數(shù)分別是什 么？ 【 提示 】 從里往外計(jì)算僅需 4次乘法和 5次加法運(yùn)算即 可得出結(jié)果 (1)把一元 n次多項(xiàng)式 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 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)計(jì)算 P(x0)的方法 先計(jì)算 ，然后 逐層計(jì)算， 直到 ，然后加上 最內(nèi)層括號(hào) 由內(nèi)向外 最外層括號(hào) 常數(shù)項(xiàng) 知識(shí) 3 進(jìn)位制 進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示 不同的數(shù)值 .使用數(shù)字符號(hào)的個(gè)數(shù)稱為基數(shù)，基數(shù)為 n，即稱為 n 進(jìn)位制，簡稱 n 進(jìn)制 .現(xiàn)在最常用的是十進(jìn)制，通常使用 10 個(gè) 阿拉伯?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， 261 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利用 “ 等值算法 ” 求給定的兩個(gè)數(shù)的最大公約數(shù)， 即多次利用減法，用數(shù)對(duì)中較大的數(shù)減去較小的數(shù)，直到相 減的差與數(shù)對(duì)中較小的數(shù)相等為止 2更相減損之術(shù)的步驟： (1)判斷兩數(shù)是否都為偶數(shù)，若是，則都除以 2直到所得 兩數(shù)不全為偶數(shù) (2)用較大的數(shù)減去較小的數(shù)，將差和較小的數(shù)構(gòu)成一對(duì) 新數(shù)，繼續(xù)用較大數(shù)減去較小數(shù)，重復(fù)執(zhí)行 (3)當(dāng)差和較小數(shù)相等時(shí)，結(jié)束執(zhí)行，此時(shí)差 (或較小數(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. 用秦九韶算法計(jì)算多項(xiàng)式 f(x) x6 12x5 60 x4 160 x3 240 x2 192x 64當(dāng) x 2時(shí)的值 【 分析 】 改寫多項(xiàng)式 確定 v 0 依次計(jì)算 v i 求 f （ 2 ） 【 解析 】 將 f(x)改寫為 f(x) (x 12)x 60)x 160)x 240)x 192)x 64， 由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng) x 2時(shí)的值 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時(shí)，原多項(xiàng)式的值為 0. 1用秦九韶算法計(jì)算多項(xiàng)式的值時(shí)，要正確將多項(xiàng)式 的形式進(jìn)行改寫，然后由內(nèi)向外依次計(jì)算當(dāng)多項(xiàng)式函數(shù)中 間出現(xiàn)空項(xiàng)式，要以系數(shù)為零的齊次項(xiàng)補(bǔ)充 2秦九韶算法的步驟： 【 變式訓(xùn)練 】 利用秦九韶算法計(jì)算多項(xiàng)式 f(x) 11 5x 3x2 7x3 在 x 23 的值時(shí)，不會(huì)用到下列哪個(gè)值 ( ) 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時(shí)， 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ù)，再求這個(gè)數(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. 求三個(gè)數(shù)的最大公約數(shù)，可先求兩個(gè)數(shù)的最大公約數(shù) a， 再求 a與第三個(gè)數(shù)的最大公約數(shù) b，則 b為所求的三個(gè)數(shù)的最 大公約數(shù)該題的解法可推廣到求 n個(gè)數(shù)的最大公約數(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 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 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 000(2) _(10)； (2)154(6) _(7). 名稱 輾轉(zhuǎn)相除法 更相減損術(shù) 區(qū)別 以除法為主 兩個(gè)整數(shù)的差較大 時(shí)，運(yùn)算次數(shù)減少 余數(shù)為 0 時(shí)結(jié)束 以減法為主 兩個(gè)整數(shù)的差較大時(shí)， 運(yùn)算次數(shù)多 兩數(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ī)律性強(qiáng)，便于利用循環(huán)語句實(shí)現(xiàn) . (3)不用對(duì) x 做冪的運(yùn)算，每 次都是計(jì)算一個(gè)一次多項(xiàng)式的 值，提高了計(jì)算精度 . 3.進(jìn)位制 對(duì)于任何一個(gè)數(shù)，我們可以用不同的進(jìn)位制來表示 .比如： 十進(jìn)數(shù) 57，可以用二進(jìn)制表示為 111 001，也可以用八進(jìn)制表 示為 71，用十六進(jìn)制表示為 39，它們所代表的數(shù)值都是一樣的 . 表示各種進(jìn)制數(shù)時(shí)，一般要在數(shù)字右下角加注來表示 .如 111 001(2)表示二進(jìn)制數(shù)， 34(5)表示五進(jìn)制數(shù) .電子計(jì)算機(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ù) 【 答案 】 D 2用秦九韶算法計(jì)算 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時(shí)，需進(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與 135的最大公約數(shù)時(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時(shí)， 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.