2019-2020學(xué)年高中數(shù)學(xué) 第1章 算法初步 1-3-1 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法學(xué)案 新人教A版必修3

《2019-2020學(xué)年高中數(shù)學(xué) 第1章 算法初步 1-3-1 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法學(xué)案 新人教A版必修3》由會員分享，可在線閱讀，更多相關(guān)《2019-2020學(xué)年高中數(shù)學(xué) 第1章 算法初步 1-3-1 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法學(xué)案 新人教A版必修3（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第1課時　輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法 1．理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過程． 2．理解秦九韶算法的計算過程，并了解它提高計算效率的實質(zhì)． 1．輾轉(zhuǎn)相除法與更相減損術(shù) (1)輾轉(zhuǎn)相除法 ①輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個正整數(shù)的最大公約數(shù)的古老而有效的算法． ②輾轉(zhuǎn)相除法的算法步驟 第一步，給定兩個正整數(shù)m，n. 第二步，計算m除以n所得的余數(shù)r. 第三步，m＝n，n＝r. 第四步，若r＝0，則m，n的最大公約數(shù)等于m；否則，返回第二步． (2)更相減損術(shù)的算法步驟 第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)．若是，用2

2、約簡；若不是，執(zhí)行第二步． 第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)．繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)(等數(shù))或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)． (3)輾轉(zhuǎn)相除法和更相減損術(shù)的區(qū)別與聯(lián)系 名稱 輾轉(zhuǎn)相除法 更相減損術(shù) 區(qū)別 (1)以除法為主； (2)兩個整數(shù)的差值較大時，運算次數(shù)較少； (3)相除，余數(shù)為0時得結(jié)果 (1)以減法為主； (2)兩個整數(shù)的差值較大時，運算次數(shù)較多； (3)相減，減數(shù)與差相等時得結(jié)果； (4)相減前要進行是否都是偶數(shù)的判斷 聯(lián)系 (1)都是求兩個正整數(shù)最大公約數(shù)的方法；

3、(2)二者的實質(zhì)都是遞推的過程； (3)二者都要用循環(huán)結(jié)構(gòu)來實現(xiàn) 2.秦九韶算法 (1)秦九韶算法簡介 ①秦九韶算法要解決的問題是求多項式的值． ②秦九韶算法的特點 通過一次式的反復(fù)計算，逐步得到高次多項式的值，即將一個n次多項式的求值問題歸結(jié)為重復(fù)計算n個一次多項式的值的問題． ③秦九韶算法的原理 將f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫為： f(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0 ＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0 ＝… 先計算最內(nèi)層括號內(nèi)一次多項式的值，即v1＝anx＋an－1，再由內(nèi)

4、向外逐層計算一次多項式vk的值． (2)秦九韶算法的操作方法 ①算法步驟如下 第一步，輸入多項式次數(shù)n、最高次項的系數(shù)an和x的值． 第二步，將v的值初始化為an，將i的值初始化為n－1. 第三步，輸入i次項的系數(shù)ai. 第四步，v＝vx＋ai，i＝i－1. 第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項式的值v. ②程序框圖如圖所示 ③程序如下 1．實際應(yīng)用更相減損術(shù)時要做的第一步工作是什么？ [提示]　先判斷a，b是否為偶數(shù)，若是，都除以2再進行． 2．判斷正誤．(正確的打“√”，錯誤的打“×”) (1)輾轉(zhuǎn)相除法的基本步驟是用較大

5、的數(shù)除以較小的數(shù)．(　　) (2)求最大公約數(shù)的方法除輾轉(zhuǎn)相除法之外，沒有其他方法．(　　) (3)編寫輾轉(zhuǎn)相除法的程序時，要用到循環(huán)語句．(　　) [提示]　(1)√　(2)×　(3)√ 題型一輾轉(zhuǎn)相除法和更相減損術(shù)的應(yīng)用 【典例1】　用輾轉(zhuǎn)相除法求612與468的最大公約數(shù)，并用更相減損術(shù)檢驗所得結(jié)果． [思路導(dǎo)引]　將612作為大數(shù)，468作為小數(shù)，執(zhí)行輾轉(zhuǎn)相除法和更相減損術(shù)的步驟即可. [解]　用輾轉(zhuǎn)相除法： 612＝468×1＋144,468＝144×3＋36,144＝36×4， 即612和468的最大公約數(shù)是36. 用更相減損術(shù)檢驗： 612和468為偶

6、數(shù)，兩次用2約簡得153和117,153－117＝36,117－36＝81,81－36＝45,45－36＝9,36－9＝27,27－9＝18,18－9＝9， 所以612和468的最大公約數(shù)為9×2×2＝36. 　求最大公約數(shù)的兩種方法步驟 (1)利用輾轉(zhuǎn)相除法求給定的兩個數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是原來兩個數(shù)的最大公約數(shù)． (2)利用更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個正整數(shù)是否都是偶數(shù)．若是，用2約簡，也可以不除以2

7、，直接求最大公約數(shù)，這樣不影響最后結(jié)果． [針對訓(xùn)練1]　用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術(shù)檢驗?zāi)愕慕Y(jié)果． [解]　80＝36×2＋8， 36＝8×4＋4,8＝4×2＋0， 即80與36的最大公約數(shù)是4. 驗證： 80÷2＝40,36÷2＝18； 40÷2＝20,18÷2＝9； 20－9＝11,11－9＝2； 9－2＝7,7－2＝5； 5－2＝3,3－2＝1； 2－1＝1,1×2×2＝4； 所以80與36的最大公約數(shù)為4. 題型二求三個正整數(shù)的最大公約數(shù) 【典例2】　求325,130,270三個數(shù)的最大公約數(shù) [思路導(dǎo)引]　求三個數(shù)的最大公約

8、數(shù)，可先求兩個數(shù)的最大公約數(shù)，再求這個最大公約數(shù)與第三個數(shù)的最大公約數(shù)． [解]　解法一(輾轉(zhuǎn)相除法)：因為325＝130×2＋65,130＝65×2，所以325和130的最大公約數(shù)為65. 因為270＝65×4＋10,65＝10×6＋5,10＝5×2, 所以65和270的最大公約數(shù)為5, 故325,130,270三個數(shù)的最大公約數(shù)為5. 解法二(更相減損術(shù))：325－130＝195,195－130＝65,130－65＝65. 所以325和130的最大公約數(shù)是65. 270－65＝205,205－65＝140,140－65＝75,75－65＝10,65－10＝55,5

9、5－10＝45,45－10＝35,35－10＝25,25－10＝15,15－10＝5,10－5＝5. 所以65和270的最大公約數(shù)為5，故325,130,270三個數(shù)的最大公約數(shù)為5. 理解輾轉(zhuǎn)相除法的實質(zhì)，從計算結(jié)果上看，輾轉(zhuǎn)相除法是以相除余數(shù)為零而得到結(jié)果的. [針對訓(xùn)練2]　求三個數(shù)175,100,75的最大公約數(shù). [解]　先求175與100的最大公約數(shù)： 175＝100×1＋75,100＝75×1＋25,75＝25×3, ∴175與100的最大公約數(shù)是25. 再求25與75的最大公約數(shù)： 75－25＝50,50－25＝25, ∴75和25

10、的最大公約數(shù)是25. ∴175,100,75的最大公約數(shù)是25. 題型三秦九韶算法 【典例3】　已知一個5次多項式為f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求這個多項式當x＝5時的值. [思路導(dǎo)引]　可根據(jù)秦九韶算法的原理，將所給的多項式改寫，然后由內(nèi)到外逐次計算． [解]　將f(x)改寫為f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8， 由內(nèi)向外依次計算一次多項式，當x＝5時的值： v0＝4； v1＝4×5＋2＝22； v2＝22×5＋3.5＝113.5； v3＝113.5×5－2.6＝564.9；

11、 v4＝564.9×5＋1.7＝2826.2； v5＝2826.2×5－0.8＝14130.2. 所以當x＝5時，多項式的值等于14130.2. (1)用秦九韶算法求多項式f(x)當x＝x0的值的思路為： ①改寫． ②計算 ③結(jié)論f(x0)＝vn. (2)應(yīng)用秦九韶算法計算多項式的值應(yīng)注意的3個問題 ①要正確將多項式的形式進行改寫． ②計算應(yīng)由內(nèi)向外依次計算． ③當多項式函數(shù)中間出現(xiàn)空項時，要以系數(shù)為零的齊次項補充． [針對訓(xùn)練3]　用秦九韶算法計算多項式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4時的值時，v3的值為(　　) A．

12、－144 B．－136 C．－57 D．34 [解析]　根據(jù)秦九韶算法多項式可化為f(x)＝(((((3x＋5)x＋6)x＋0)x－8)x＋35)x＋12. 由內(nèi)向外計算v0＝3； v1＝3×(－4)＋5＝－7； v2＝－7×(－4)＋6＝34； v3＝34×(－4)＋0＝－136. [答案]　B 課堂歸納小結(jié) 1.求兩個正整數(shù)的最大公約數(shù)的問題，可以用輾轉(zhuǎn)相除法，也可以用更相減損術(shù)．用輾轉(zhuǎn)相除法，即根據(jù)a＝nb＋r這個式子，反復(fù)相除，直到r＝0為止；用更相減損術(shù)，即根據(jù)r＝|a－b|這個式子，反復(fù)相減，直到r＝0為止． 2.秦九韶算法的關(guān)鍵在于把n次多項式

13、轉(zhuǎn)化為一次多項式，注意體會遞推的實現(xiàn)過程，實施運算時要由內(nèi)向外，一步一步執(zhí)行． 1．輾轉(zhuǎn)相除法可解決的問題是(　　) A．求兩個正整數(shù)的最大公約數(shù) B．多項式求值 C．求兩個正整數(shù)的最小公倍數(shù) D．排序問題 [解析]　輾轉(zhuǎn)相除法可以求兩個正整數(shù)的最大公約數(shù). [答案]　A 2．用輾轉(zhuǎn)相除法求72與120的最大公約數(shù)時，需要做除法次數(shù)為(　　) A．4 B．3 C．5 D．6 [解析]　120＝72×1＋48,72＝48×1＋24,48＝24×2. [答案]　B 3．用更相減損術(shù)求36與134的最大公約數(shù)，第一步應(yīng)為________． [解析]　∵3

14、6與134都是偶數(shù)，∴第一步應(yīng)先除以2，得到18與67. [答案]　先分別除以2，得到18與67 4．用秦九韶算法求f(x)＝2x3＋x－3當x＝3時的值v2＝________. [解析]　f(x)＝((2x＋0)x＋1)x－3，v0＝2，v1＝2×3＋0＝6，v2＝6×3＋1＝19. [答案]　19 5．用秦九韶算法求多項式f(x)＝8x7＋5x6＋3x4＋2x＋1，當x＝2時的值． [解]　根據(jù)秦九韶算法，把多項式改寫成如下形式： f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.

15、 而x＝2，所以有v0＝8， v1＝8×2＋5＝21， v2＝21×2＋0＝42， v3＝42×2＋3＝87， v4＝87×2＋0＝174， v5＝174×2＋0＝348， v6＝348×2＋2＝698， v7＝698×2＋1＝1397. 所以當x＝2時，多項式的值為1397. 算法案例在實際生活中的應(yīng)用 通過算法案例的學(xué)習，知道算法的核心是一般意義上的解決問題的策略的具體化．對于一個實際問題，我們在分析、思考后可將之轉(zhuǎn)化為數(shù)學(xué)問題，從而獲得解決它的基本思路. 【典例】　現(xiàn)有長度為2.4 m和5.6 m兩種規(guī)格的鋼筋若干，要焊接一批棱上無接點的正方體模型，問怎樣設(shè)

16、計才能保證正方體的體積最大且不浪費材料？ [思路導(dǎo)引]　要焊接正方體，就是將兩種規(guī)格的鋼筋截成長度相等的鋼筋條．為了保證不浪費材料，應(yīng)使得每種規(guī)格的鋼筋截取后沒有剩余，因此截取的長度應(yīng)為2.4與5.6的公約數(shù)；為使得正方體的體積最大，因此截取的長度應(yīng)為2.4與5.6的最大公約數(shù). [解]　用更相減損術(shù)來求2.4與5.6的最大公約數(shù)： 5．6－2.4＝3.2, 3．2－2.4＝0.8, 2．4－0.8＝1.6, 1．6－0.8＝0.8, 因此2.4與5.6的最大公約數(shù)為0.8. 所以使得正方體的棱長為0.8 m時，正方體的體積最大且不浪費材料. [針對訓(xùn)練]　甲，

17、乙，丙三種溶液的質(zhì)量分別為147 g，343 g，133 g，現(xiàn)要將它們分別全部裝入小瓶中，每個小瓶中裝入溶液的質(zhì)量相同，問每瓶最多裝多少？ [解]　由題意，每個小瓶中裝入的溶液的質(zhì)量應(yīng)是三種溶液質(zhì)量的最大公約數(shù)． 先求147與343的最大公約數(shù)： 343－147＝196,196－147＝49,147－49＝98,98－49＝49， 所以147與343的最大公約數(shù)是49. 再求49與133的最大公約數(shù)： 133－49＝84,84－49＝35,49－35＝14,35－14＝21,21－14＝7,14－7＝7， 所以147,343,133的最大公約數(shù)為7，即每瓶最多裝7 g. 課后

18、作業(yè)(八) (時間45分鐘) 學(xué)業(yè)水平合格練(時間25分鐘) 1．秦九韶算法與直接計算相比較，下列說法錯誤的是(　　) A．秦九韶算法與直接計算相比，大大節(jié)省了做乘法的次數(shù)，使計算量減少，并且邏輯結(jié)構(gòu)簡單 B．秦九韶算法減少了做乘法的次數(shù)，在計算機上也就加快了計算的速度 C．秦九韶算法減少了做乘法的次數(shù)，在計算機上也就降低了計算的速度 D．秦九韶算法避免了對自變量x單獨做冪的計算，而且與系數(shù)一起逐次增長冪次，從而提高計算的精度 [解析]　秦九韶算法減少了做乘法的次數(shù)，在計算機上也就加快了計算的速度，故選項C錯誤． [答案]　C 2．下列說法中正確的個數(shù)為(　　) ①輾轉(zhuǎn)

19、相除法也叫歐幾里得算法； ②輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)； ③求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒有其他方法； ④編寫輾轉(zhuǎn)相除法的程序時，要用到循環(huán)語句． A．1 B．2 C．3 D．4 [解析]?、?、②、④正確，③錯誤． [答案]　C 3．利用秦九韶算法求f(x)＝1＋2x＋3x2＋…＋6x5當x＝2時的值時，下列說法正確的是(　　) A．先求1＋2×2 B．先求6×2＋5，第二步求2×(6×2＋5)＋4 C．f(2)＝1＋2×2＋3×22＋4×23＋5×24＋6×25直接運算求解 D．以上都不對 [解析]　利用秦九韶算法應(yīng)先算anx

20、＋an－1，再算(anx＋an－1)x＋an－2，故選B. [答案]　B 4．中國古代有計算多項式值的秦九韶算法，下圖是實現(xiàn)該算法的程序框圖．執(zhí)行該程序框圖，若輸入的x＝2，n＝2，依次輸入的a為2,2,5，則輸出的s＝(　　) A．7 B．12 C．17 D．34 [解析]　該題考查程序框圖的運行及考生的識圖能力． 由程序框圖知， 第一次循環(huán)：x＝2，n＝2，a＝2，s＝0×2＋2＝2，k＝1； 第二次循環(huán)：a＝2，s＝2×2＋2＝6，k＝2； 第三次循環(huán)：a＝5，s＝6×2＋5＝17，k＝3.結(jié)束循環(huán)，輸出s的值為17，故選C. [答案]　C 5．用更

21、相減損術(shù)求117和182的最大公約數(shù)時，需做減法的次數(shù)是(　　) A．8 B．7 C．6 D．5 [解析]　∵182－117＝65,117－65＝52,65－52＝13,52－13＝39,39－13＝26,26－13＝13，∴13是117和182的最大公約數(shù)，需做減法的次數(shù)是6. [答案]　C 6．用秦九韶算法求n次多項式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0當x＝x0時的值，求f(x0)需要乘方、乘法、加法的次數(shù)分別為(　　) A.，n，n B．n,2n，n C．0,2n，n D．0，n，n [解析]　因為f(x)＝(…((anx＋an－1)x＋a

22、n－2)x＋…＋a1)x＋a0，所以乘方、乘法、加法的次數(shù)分別為0，n，n. [答案]　D 7．用秦九韶算法求多項式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6當x＝－4的值時，其中v1的值為________． [解析]　∵f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6，∴v0＝a6＝3，v1＝v0x＋a5＝3×(－4)＋5＝－7. [答案]?。? 8．378和90的最大公約數(shù)為________． [解析]　378＝90×4＋18,90＝18×5＋0， ∴378與90的最大公約數(shù)是18. [答案]　18 9．求1356和2400的最小公倍

23、數(shù)． [解]　2400＝1356×1＋1044， 1356＝1044×1＋312， 1044＝312×3＋108， 312＝108×2＋96， 108＝96×1＋12， 96＝12×8. 所以1356與2400的最大公約數(shù)為12. 則1356與2400的最小公倍數(shù)為(1356×2400)÷12＝271200. 10．用秦九韶算法求多項式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x當x＝3時的值． [解]　f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)·x，所以v0＝7， v1＝7×3＋6＝27， v2＝27×3＋5＝86， v

24、3＝86×3＋4＝262， v4＝262×3＋3＝789， v5＝789×3＋2＝2369， v6＝2369×3＋1＝7108， v7＝7108×3＝21324. 故x＝3時，多項式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值為21324. 應(yīng)試能力等級練(時間20分鐘) 11．下列哪組的最大公約數(shù)與1855,1120的最大公約數(shù)不同(　　) A．1120,735 B．385,350 C．385,735 D．1855,325 [解析]　∵(1855,1120)→(735,1120)→(735,385)→(350,385)→(350,35)，

25、 ∴1855與1120的最大公約數(shù)是35， 由以上計算過程可知選D. [答案]　D 12．用秦九韶算法計算多項式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1，當x＝0.4時的值時，需要做乘法和加法的次數(shù)分別是(　　) A．6,6 B．5,6 C．5,5 D．6,5 [解析]　根據(jù)秦九韶算法，把多項式改寫為f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，∴需要做6次加法運算，6次乘法運算，故選A. [答案]　A 13．已知a＝333，b＝24，則使得a＝bq＋r(q，r均為自然數(shù)，且0≤r≤b)成立的q和r的值分別為________． [

26、解析]　用333除以24，商即為q，余數(shù)就是r.333÷24的商為13，余數(shù)是21. ∴q＝13，r＝21. [答案]　13,21 14．用秦九韶算法求多項式f(x)＝1－5x－8x2＋10x3＋6x4＋12x5＋3x6當x＝－4時的值時，v0，v1，v2，v3，v4中最大值與最小值的差是________． [解析]　多項式變形為 f(x)＝3x6＋12x5＋6x4＋10x3－8x2－5x＋1 ＝(((((3x＋12)x＋6)x＋10)x－8)x－5)x＋1， v0＝3， v1＝3×(－4)＋12＝0， v2＝0×(－4)＋6＝6， v3＝6×(－4)＋10＝－14， v

27、4＝－14×(－4)－8＝48， 所以v4最大，v3最小，所以v4－v3＝48＋14＝62. [答案]　62 15．用輾轉(zhuǎn)相除法和更相減損術(shù)兩種方法求三個數(shù)72,120,168的最大公約數(shù)． [解]　(輾轉(zhuǎn)相除法)： 先求120,168的最大公約數(shù)． 因為168＝120×1＋48， 120＝48×2＋24,48＝24×2， 所以120,168的最大公約數(shù)是24. 再求72,24的最大公約數(shù)． 因為72＝24×3，所以72,24的最大公約數(shù)為24， 即72,120,168的最大公約數(shù)為24. (更相減損術(shù))： 先求120,168的最大公約數(shù)． 168－120＝48,120－48＝72， 72－48＝24,48－24＝24， 所以120,168的最大公約數(shù)為24. 再求72,24的最大公約數(shù)． 72－24＝48,48－24＝24， 所以72,24的最大公約數(shù)為24， 即72,120,168的最大公約數(shù)為24. 13