《高中數(shù)學(xué)必修3同步練習(xí)與單元檢測(cè)第一章 算法初步 §1.3》由會(huì)員分享，可在線閱讀，更多相關(guān)《高中數(shù)學(xué)必修3同步練習(xí)與單元檢測(cè)第一章 算法初步 §1.3（7頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

§1.3　算法案例 課時(shí)目標(biāo)　通過(guò)三種算法案例：輾轉(zhuǎn)相除法與更相減損術(shù)，秦九韶算法，進(jìn)位制，進(jìn)一步體會(huì)算法的思想，提高算法設(shè)計(jì)水平，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界的貢獻(xiàn)． 1．輾轉(zhuǎn)相除法 (1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個(gè)正整數(shù)的最大公約數(shù)的古老而有效的算法． (2)輾轉(zhuǎn)相除法的算法步驟 第一步，給定兩個(gè)正整數(shù)m，n. 第二步，計(jì)算m除以n所得的余數(shù)r. 第三步，m＝n，n＝r. 第四步，若r＝0，則m、n的最大公約數(shù)等于m；否則，返回第二步． 2．更相減損術(shù) 第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)．若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步． 第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)． 3．秦九韶算法 把一個(gè)n次多項(xiàng)式f(x)＝anxn＋an－1xn－1＋…＋a1x＋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)式的值，即 v2＝v1x＋an－2， v3＝v2x＋an－3， … vn＝vn－1x＋a0 這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值． 4．進(jìn)位制 進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，“滿k進(jìn)一”就是k進(jìn)制，k進(jìn)制的基數(shù)是k. 把十進(jìn)制轉(zhuǎn)化為k進(jìn)制數(shù)時(shí)，通常用除k取余法． 一、選擇題 1．下列說(shuō)法中正確的個(gè)數(shù)為(　　) (1)輾轉(zhuǎn)相除法也叫歐幾里得算法； (2)輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)； (3)求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒(méi)有其他方法； (4)編寫輾轉(zhuǎn)相除法的程序時(shí)，要用到循環(huán)語(yǔ)句． A．1 B．2 C．3 D．4 答案　C 解析　(1)、(2)、(4)正確，(3)錯(cuò)誤． 2．用更相減損術(shù)求294和84的最大公約數(shù)時(shí)，需做減法的次數(shù)是(　　) A．2 B．3 C．4 D．5 答案　C 解析　由于294和84都是偶數(shù)， 所以用2約簡(jiǎn)： 294÷2＝147， 84÷2＝42， 又由于147不是偶數(shù)， 所以147－42＝105， 105－42＝63， 63－42＝21， 42－21＝21， 故需做4次減法，故選C. 3．1 037和425的最大公約數(shù)是(　　) A．51 B．17 C．9 D．3 答案　B 解析　∵1 037＝425×2＋187， 425＝187×2＋51， 187＝51×3＋34， 51＝34×1＋17， 34＝17×2， 即1 037和425的最大公約數(shù)是17. 4．用秦九韶算法計(jì)算多項(xiàng)式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4時(shí)的值時(shí)，需做加法和乘法的次數(shù)的和為(　　) A．10 B．9 C．12 D．8 答案　C 解析　f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7 ∴加法6次，乘法6次， ∴6＋6＝12(次)，故選C. 5．已知f(x)＝x5＋2x3＋3x2＋x＋1，應(yīng)用秦九韶算法計(jì)算x＝3時(shí)的值時(shí)，v3的值為(　　) A．27 B．11 C．109 D．36 答案　D 解析　將函數(shù)式化成如下形式． f(x)＝(((x＋0)x＋2)x＋3)x＋1)x＋1 由內(nèi)向外依次計(jì)算： v0＝1， v1＝1×3＋0＝3， v2＝3×3＋2＝11， v3＝11×3＋3＝36， v4＝36×3＋1＝109， v5＝109×3＋1＝328. 6．下列有可能是4進(jìn)制數(shù)的是(　　) A．5 123 B．6 542 C．3 103 D．4 312 答案　C 解析　4進(jìn)制數(shù)每位上的數(shù)字一定小于4，故選C. 二、填空題 7．輾轉(zhuǎn)相除法程序中有一空請(qǐng)?zhí)钌希? 答案　a MOD b 解析　MOD用來(lái)表示a除以b的余數(shù)． 8．更相減損術(shù)程序中有兩空請(qǐng)?zhí)钌希? 答案　a＝b　b＝r 9．已知三個(gè)數(shù)12(16)，25(7)，33(4)，將它們按由小到大的順序排列為_(kāi)_______． 答案　33(4)<12(16)<25(7) 解析　將三個(gè)數(shù)都化為十進(jìn)制數(shù)． 12(16)＝1×16＋2＝18， 25(7)＝2×7＋5＝19， 33(4)＝3×4＋3＝15， ∴33(4)<12(16)<25(7)． 三、解答題 10．用兩種方法求210與98的最大公約數(shù)． 解　用輾轉(zhuǎn)相除法： 210＝98×2＋14， 98＝14×7. ∴210與98的最大公約數(shù)為14. 用更相減損術(shù)： ∵210與98都是偶數(shù)，用2約簡(jiǎn)得 105和49， 105－49＝56,56－49＝7， 49－7＝42,42－7＝35， 35－7＝28,28－7＝21， 21－7＝14,14－7＝7. ∴210與98的最大公約數(shù)為2×7＝14. 11．用秦九韶算法計(jì)算多項(xiàng)式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64當(dāng)x＝2時(shí)的值． 解　將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. 能力提升 12．把111化為五進(jìn)制數(shù)． 解　 ∴111化為五進(jìn)制數(shù)為421(5)． 13．把10 231(5)化為四進(jìn)制數(shù)． 解　先化成十進(jìn)制數(shù)． 10 231(5)＝1×54＋0×53＋2×52＋3×51＋1 ＝625＋50＋15＋1 ＝691 再化為四進(jìn)制數(shù) ∴10 231(5)＝22 303(4). 1．輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別和聯(lián)系 (1)都是求最大公約數(shù)的方法． (2)二者的實(shí)質(zhì)都是遞歸的過(guò)程． (3)二者都要用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)． 2．秦九韶算法的特點(diǎn) 秦九韶算法的特點(diǎn)在于把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值，即把求f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值轉(zhuǎn)化為求遞推公式： 這樣可以最多計(jì)算n次乘法和n次加法即可得多項(xiàng)式的值，和直接代入多項(xiàng)式相比減少了乘法的運(yùn)算次數(shù)，提高了運(yùn)算效率． 3．十進(jìn)制與其他進(jìn)制的轉(zhuǎn)化 (1)將k進(jìn)制轉(zhuǎn)化為十進(jìn)制的方法：先把k進(jìn)制數(shù)寫成各位上的數(shù)字與k的冪的乘積的形 式，再按十進(jìn)制的運(yùn)算規(guī)則計(jì)算． (2)將十進(jìn)制化成k進(jìn)制的方法：用除k取余法，用k連續(xù)去除十進(jìn)制數(shù)所得的商，直到商為零為止，然后將各步所得的余數(shù)倒序?qū)懗?，即為相?yīng)的k進(jìn)制數(shù)．