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

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

2、以大數(shù)減小數(shù)繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)(等數(shù))或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)(3)輾轉(zhuǎn)相除法和更相減損術的區(qū)別與聯(lián)系名稱輾轉(zhuǎn)相除法更相減損術區(qū)別(1)以除法為主；(2)兩個整數(shù)的差值較大時，運算次數(shù)較少；(3)相除，余數(shù)為0時得結果(1)以減法為主；(2)兩個整數(shù)的差值較大時，運算次數(shù)較多；(3)相減，減數(shù)與差相等時得結果；(4)相減前要進行是否都是偶數(shù)的判斷聯(lián)系(1)都是求兩個正整數(shù)最大公約數(shù)的方法；(2)二者的實質(zhì)都是遞推的過程；(3)二者都要用循環(huán)結構來實現(xiàn)2.秦九韶算法(1)秦九韶算法簡介秦九韶算法要解決的問題是求多項式的值秦九韶算法的特點通過一次式的反

3、復計算，逐步得到高次多項式的值，即將一個n次多項式的求值問題歸結為重復計算n個一次多項式的值的問題秦九韶算法的原理將f(x)anxnan1xn1a1xa0改寫為：f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0先計算最內(nèi)層括號內(nèi)一次多項式的值，即v1anxan1，再由內(nèi)向外逐層計算一次多項式vk的值(2)秦九韶算法的操作方法算法步驟如下第一步，輸入多項式次數(shù)n、最高次項的系數(shù)an和x的值第二步，將v的值初始化為an，將i的值初始化為n1.第三步，輸入i次項的系數(shù)ai.第四步，vvxai，ii1.第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸

4、出多項式的值v.程序框圖如圖所示程序如下1實際應用更相減損術時要做的第一步工作是什么？提示先判斷a，b是否為偶數(shù)，若是，都除以2再進行2判斷正誤(正確的打“”，錯誤的打“”)(1)輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)()(2)求最大公約數(shù)的方法除輾轉(zhuǎn)相除法之外，沒有其他方法()(3)編寫輾轉(zhuǎn)相除法的程序時，要用到循環(huán)語句()提示(1)(2)(3)題型一輾轉(zhuǎn)相除法和更相減損術的應用【典例1】用輾轉(zhuǎn)相除法求612與468的最大公約數(shù)，并用更相減損術檢驗所得結果思路導引將612作為大數(shù)，468作為小數(shù)，執(zhí)行輾轉(zhuǎn)相除法和更相減損術的步驟即可. 解用輾轉(zhuǎn)相除法：6124681144,468144

5、336,144364，即612和468的最大公約數(shù)是36.用更相減損術檢驗：612和468為偶數(shù)，兩次用2約簡得153和117,15311736,1173681,813645,45369,36927,27918,1899，所以612和468的最大公約數(shù)為92236.求最大公約數(shù)的兩種方法步驟(1)利用輾轉(zhuǎn)相除法求給定的兩個數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構成新的數(shù)對，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時的較小數(shù)就是原來兩個數(shù)的最大公約數(shù)(2)利用更相減損術求兩個正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個正整數(shù)是否都是偶數(shù)若是

6、，用2約簡，也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結果針對訓練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術檢驗你的結果解803628，36844,8420，即80與36的最大公約數(shù)是4.驗證：80240,36218；40220,1829；20911,1192；927,725；523,321；211,1224；所以80與36的最大公約數(shù)為4.題型二求三個正整數(shù)的最大公約數(shù)【典例2】求325,130,270三個數(shù)的最大公約數(shù)思路導引求三個數(shù)的最大公約數(shù)，可先求兩個數(shù)的最大公約數(shù)，再求這個最大公約數(shù)與第三個數(shù)的最大公約數(shù)解解法一(輾轉(zhuǎn)相除法)：因為325130265,130652

7、，所以325和130的最大公約數(shù)為65. 因為27065410,651065,1052, 所以65和270的最大公約數(shù)為5, 故325,130,270三個數(shù)的最大公約數(shù)為5. 解法二(更相減損術)：325130195,19513065,1306565. 所以325和130的最大公約數(shù)是65. 27065205,20565140,1406575,756510,651055,551045,451035,351025,251015,15105,1055. 所以65和270的最大公約數(shù)為5，故325,130,270三個數(shù)的最大公約數(shù)為5.理解輾轉(zhuǎn)相除法的實質(zhì)，從計算結果上看，輾轉(zhuǎn)相除法是以相除余數(shù)為零

8、而得到結果的. 針對訓練2求三個數(shù)175,100,75的最大公約數(shù). 解先求175與100的最大公約數(shù)：175100175,10075125,75253, 175與100的最大公約數(shù)是25. 再求25與75的最大公約數(shù)：752550,502525, 75和25的最大公約數(shù)是25. 175,100,75的最大公約數(shù)是25. 題型三秦九韶算法【典例3】已知一個5次多項式為f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求這個多項式當x5時的值. 思路導引可根據(jù)秦九韶算法的原理，將所給的多項式改寫，然后由內(nèi)到外逐次計算解將f(x)改寫為f(x)(4x2)x3.5)x2.6)x1.

9、7)x0.8，由內(nèi)向外依次計算一次多項式，當x5時的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72826.2；v52826.250.814130.2.所以當x5時，多項式的值等于14130.2.(1)用秦九韶算法求多項式f(x)當xx0的值的思路為：改寫計算結論f(x0)vn.(2)應用秦九韶算法計算多項式的值應注意的3個問題要正確將多項式的形式進行改寫計算應由內(nèi)向外依次計算當多項式函數(shù)中間出現(xiàn)空項時，要以系數(shù)為零的齊次項補充針對訓練3用秦九韶算法計算多項式f(x)1235x8x26x45x53x6在x4時的值時，v3的值為(

10、)A144 B136 C57 D34解析根據(jù)秦九韶算法多項式可化為f(x)(3x5)x6)x0)x8)x35)x12.由內(nèi)向外計算v03；v13(4)57；v27(4)634；v334(4)0136.答案B課堂歸納小結1.求兩個正整數(shù)的最大公約數(shù)的問題，可以用輾轉(zhuǎn)相除法，也可以用更相減損術用輾轉(zhuǎn)相除法，即根據(jù)anbr這個式子，反復相除，直到r0為止；用更相減損術，即根據(jù)r|ab|這個式子，反復相減，直到r0為止2.秦九韶算法的關鍵在于把n次多項式轉(zhuǎn)化為一次多項式，注意體會遞推的實現(xiàn)過程，實施運算時要由內(nèi)向外，一步一步執(zhí)行1輾轉(zhuǎn)相除法可解決的問題是()A求兩個正整數(shù)的最大公約數(shù)B多項式求值C求兩

11、個正整數(shù)的最小公倍數(shù)D排序問題解析輾轉(zhuǎn)相除法可以求兩個正整數(shù)的最大公約數(shù). 答案A2用輾轉(zhuǎn)相除法求72與120的最大公約數(shù)時，需要做除法次數(shù)為()A4 B3C5 D6解析12072148,7248124,48242.答案B3用更相減損術求36與134的最大公約數(shù)，第一步應為_解析36與134都是偶數(shù)，第一步應先除以2，得到18與67.答案先分別除以2，得到18與674用秦九韶算法求f(x)2x3x3當x3時的值v2_.解析f(x)(2x0)x1)x3，v02，v12306，v263119.答案195用秦九韶算法求多項式f(x)8x75x63x42x1，當x2時的值解根據(jù)秦九韶算法，把多項式改寫

12、成如下形式：f(x)8x75x60x53x40x30x22x1(8x5)x0)x3)x0)x0)x2)x1.而x2，所以有v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211397.所以當x2時，多項式的值為1397.算法案例在實際生活中的應用通過算法案例的學習，知道算法的核心是一般意義上的解決問題的策略的具體化對于一個實際問題，我們在分析、思考后可將之轉(zhuǎn)化為數(shù)學問題，從而獲得解決它的基本思路. 【典例】現(xiàn)有長度為2.4 m和5.6 m兩種規(guī)格的鋼筋若干，要焊接一批棱上無接點的正方體模型，問怎樣設計才能保證

13、正方體的體積最大且不浪費材料？思路導引要焊接正方體，就是將兩種規(guī)格的鋼筋截成長度相等的鋼筋條為了保證不浪費材料，應使得每種規(guī)格的鋼筋截取后沒有剩余，因此截取的長度應為2.4與5.6的公約數(shù)；為使得正方體的體積最大，因此截取的長度應為2.4與5.6的最大公約數(shù). 解用更相減損術來求2.4與5.6的最大公約數(shù)：562.43.2, 322.40.8, 240.81.6, 160.80.8, 因此2.4與5.6的最大公約數(shù)為0.8. 所以使得正方體的棱長為0.8 m時，正方體的體積最大且不浪費材料. 針對訓練甲，乙，丙三種溶液的質(zhì)量分別為147 g，343 g，133 g，現(xiàn)要將它們分別全部裝入小瓶中

14、，每個小瓶中裝入溶液的質(zhì)量相同，問每瓶最多裝多少？解由題意，每個小瓶中裝入的溶液的質(zhì)量應是三種溶液質(zhì)量的最大公約數(shù)先求147與343的最大公約數(shù)：343147196,19614749,1474998,984949，所以147與343的最大公約數(shù)是49.再求49與133的最大公約數(shù)：1334984,844935,493514,351421,21147,1477，所以147,343,133的最大公約數(shù)為7，即每瓶最多裝7 g.課后作業(yè)(八) (時間45分鐘)學業(yè)水平合格練(時間25分鐘)1秦九韶算法與直接計算相比較，下列說法錯誤的是()A秦九韶算法與直接計算相比，大大節(jié)省了做乘法的次數(shù)，使計算量減

15、少，并且邏輯結構簡單B秦九韶算法減少了做乘法的次數(shù)，在計算機上也就加快了計算的速度C秦九韶算法減少了做乘法的次數(shù)，在計算機上也就降低了計算的速度D秦九韶算法避免了對自變量x單獨做冪的計算，而且與系數(shù)一起逐次增長冪次，從而提高計算的精度解析秦九韶算法減少了做乘法的次數(shù)，在計算機上也就加快了計算的速度，故選項C錯誤答案C2下列說法中正確的個數(shù)為()輾轉(zhuǎn)相除法也叫歐幾里得算法；輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)；求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒有其他方法；編寫輾轉(zhuǎn)相除法的程序時，要用到循環(huán)語句A1 B2 C3 D4解析、正確，錯誤答案C3利用秦九韶算法求f(x)12x3x26x5當

16、x2時的值時，下列說法正確的是()A先求122B先求625，第二步求2(625)4Cf(2)122322423524625直接運算求解D以上都不對解析利用秦九韶算法應先算anxan1，再算(anxan1)xan2，故選B.答案B4中國古代有計算多項式值的秦九韶算法，下圖是實現(xiàn)該算法的程序框圖執(zhí)行該程序框圖，若輸入的x2，n2，依次輸入的a為2,2,5，則輸出的s()A7 B12 C17 D34解析該題考查程序框圖的運行及考生的識圖能力由程序框圖知，第一次循環(huán)：x2，n2，a2，s0222，k1；第二次循環(huán)：a2，s2226，k2；第三次循環(huán)：a5，s62517，k3.結束循環(huán)，輸出s的值為17

17、，故選C.答案C5用更相減損術求117和182的最大公約數(shù)時，需做減法的次數(shù)是()A8 B7 C6 D5解析18211765,1176552,655213,521339,391326,261313，13是117和182的最大公約數(shù)，需做減法的次數(shù)是6.答案C6用秦九韶算法求n次多項式f(x)anxnan1xn1a1xa0當xx0時的值，求f(x0)需要乘方、乘法、加法的次數(shù)分別為()A.，n，nBn,2n，nC0,2n，nD0，n，n解析因為f(x)(anxan1)xan2)xa1)xa0，所以乘方、乘法、加法的次數(shù)分別為0，n，n.答案D7用秦九韶算法求多項式f(x)1235x8x279x3

18、6x45x53x6當x4的值時，其中v1的值為_解析f(x)1235x8x279x36x45x53x6，v0a63，v1v0xa53(4)57.答案78378和90的最大公約數(shù)為_解析37890418,901850，378與90的最大公約數(shù)是18.答案189求1356和2400的最小公倍數(shù)解2400135611044，135610441312，10443123108，312108296，10896112，96128.所以1356與2400的最大公約數(shù)為12.則1356與2400的最小公倍數(shù)為(13562400)12271200.10用秦九韶算法求多項式f(x)7x76x65x54x43x32x

19、2x當x3時的值解f(x)(7x6)x5)x4)x3)x2)x1)x，所以v07，v173627，v2273586，v38634262，v426233789，v5789322369，v62369317108，v77108321324.故x3時，多項式f(x)7x76x65x54x43x32x2x的值為21324.應試能力等級練(時間20分鐘)11下列哪組的最大公約數(shù)與1855,1120的最大公約數(shù)不同()A1120,735 B385,350C385,735 D1855,325解析(1855,1120)(735,1120)(735,385)(350,385)(350,35)，1855與1120的

20、最大公約數(shù)是35，由以上計算過程可知選D.答案D12用秦九韶算法計算多項式f(x)3x64x55x46x37x28x1，當x0.4時的值時，需要做乘法和加法的次數(shù)分別是()A6,6B5,6C5,5D6,5解析根據(jù)秦九韶算法，把多項式改寫為f(x)(3x4)x5)x6)x7)x8)x1，需要做6次加法運算，6次乘法運算，故選A.答案A13已知a333，b24，則使得abqr(q，r均為自然數(shù)，且0rb)成立的q和r的值分別為_解析用333除以24，商即為q，余數(shù)就是r.33324的商為13，余數(shù)是21.q13，r21.答案13,2114用秦九韶算法求多項式f(x)15x8x210x36x412x

21、53x6當x4時的值時，v0，v1，v2，v3，v4中最大值與最小值的差是_解析多項式變形為f(x)3x612x56x410x38x25x1(3x12)x6)x10)x8)x5)x1，v03，v13(4)120，v20(4)66，v36(4)1014，v414(4)848，所以v4最大，v3最小，所以v4v3481462.答案6215用輾轉(zhuǎn)相除法和更相減損術兩種方法求三個數(shù)72,120,168的最大公約數(shù)解(輾轉(zhuǎn)相除法)：先求120,168的最大公約數(shù)因為168120148，12048224,48242，所以120,168的最大公約數(shù)是24.再求72,24的最大公約數(shù)因為72243，所以72,24的最大公約數(shù)為24，即72,120,168的最大公約數(shù)為24.(更相減損術)：先求120,168的最大公約數(shù)16812048,1204872，724824,482424，所以120,168的最大公約數(shù)為24.再求72,24的最大公約數(shù)722448,482424，所以72,24的最大公約數(shù)為24，即72,120,168的最大公約數(shù)為24.13