成才之路 數(shù)學(xué),路漫漫其修遠(yuǎn)兮 吾將上下而求索,人教A版 必修3,算法初步,第一章,1.3 算法案例,第一章,第1課時(shí) 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法,雞兔同籠問題是中國古代數(shù)學(xué)名著孫子算法中的一道名題，題目是這樣的：“今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？”書中給出的解法是：雞有兩只腳，兔有四只腳，把腳數(shù)除以2，共有47對腳由于雞有1對腳，兔有2對腳，所以從47中減去25，得12即為兔子數(shù)因?yàn)槿缫\子里的動(dòng)物每只都只有1對腳，就會(huì)多出12對腳來，把這12對腳分別加到有2對腳的動(dòng)物身上，就有12只腳動(dòng)物，即兔子數(shù)整個(gè)解題過程可以簡單地寫作：,知識(shí)銜接,1輾轉(zhuǎn)相除法與更相減損術(shù) (1)輾轉(zhuǎn)相除法 算法步驟： 第一步，給定兩個(gè)正整數(shù)m，n. 第二步，計(jì)算m除以n所得的余數(shù)r. 第三步，mn，nr. 第四步，若r_，則m，n的最大公約數(shù)等于m；否則返回 第_步,自主預(yù)習(xí),0,二,程序框圖如圖所示,程序： INPUT m，n DO rm MOD n mn nr LOOP UNTIL _ PRINT _ END,r0,m,(2)更相減損術(shù) 算法步驟： 第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是_若是，用_約簡；若不是，執(zhí)行第二步 第二步，以較大的數(shù)_去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以_數(shù)減_數(shù)繼續(xù)這個(gè)操作，直到所得的差與減數(shù)相等為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù),偶數(shù),2,減,大,小,2秦九韶算法 (1)概念：求多項(xiàng)式f(x)anxnan1xn1a1xa0的值時(shí)，常用秦九韶算法，這種算法的運(yùn)算次數(shù)較少，是多項(xiàng)式求值比較先進(jìn)的算法，其實(shí)質(zhì)是轉(zhuǎn)化為求n個(gè)_多項(xiàng)式的值，共進(jìn)行_次乘法運(yùn)算和_次加法運(yùn)算其過程是： 改寫多項(xiàng)式為： f(x)anxnan1xn1a1xa0 (anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0. 設(shè)v1_，,一次,n,n,anxan1,v2v1xan2， v3v2xan3， ， vn_.,vn1xa0,(2)算法步驟： 第一步，輸入多項(xiàng)式的次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值 第二步，將v的值初始化為an，將i的值初始化為n1. 第三步，輸入i次項(xiàng)的系數(shù)ai. 第四步，vvxai，i_. 第五步，判斷i是否大于或等于_.若是，則返回第三步；否則，輸出多項(xiàng)式的值_.,i1,0,v,(3)程序框圖如圖所示,(4)程序： INPUT “n”；n INPUT “an”；a INPUT “x”；x va in1 WHILE _ PRINT “i”；i INPUT “ai”；a,i0,v_ ii1 WEND PRINT _ END,v*xa,v,1用輾轉(zhuǎn)相除法求36與134的最大公約數(shù)，第一步是( ) A1343698 B13436326 C先除以2，得到18與67 D3626110 答案 B 解析 求36與134的最大公約數(shù)，第一步是13436326，第二步是3626110，故選D.,預(yù)習(xí)自測,2(2015河北省廊坊一中月考)用輾轉(zhuǎn)相除法求294和84的最大公約數(shù)時(shí)，需要做除法的次數(shù)是( ) A1 B2 C3 D4 答案 B 解析 本題考查輾轉(zhuǎn)相除法的過程.29484342,84422，故選B.,3設(shè)計(jì)程序框圖，用秦九韶算法求多項(xiàng)式的值，所選用的結(jié)構(gòu)是( ) A順序結(jié)構(gòu) B條件結(jié)構(gòu) C循環(huán)結(jié)構(gòu) D以上都有 答案 D 4用更相減損術(shù)求294和84的最大公約數(shù)時(shí)，第一步是_ 答案 用2約簡 解析 由于294和84都是偶數(shù)，先用2約簡,5(2015云南省景洪一中月考)用秦九韶算法計(jì)算多項(xiàng)式f(x)3x62x54x45x37x28x1在x0.5時(shí)的值，需做乘法和加法的次數(shù)分別是_ 答案 6次乘法，6次加法 解析 將多項(xiàng)式改寫為f(x)(3x2)x4)x5)x7)x8)x1，化為6個(gè)一次因式求解，故只做了6次乘法和6次加法,用輾轉(zhuǎn)相除法求80和36的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)所得結(jié)果 探究 1.輾轉(zhuǎn)相除法與更相減損術(shù)的主要區(qū)別是什么？ 2將80作為大數(shù)，36作為小數(shù)，執(zhí)行輾轉(zhuǎn)相除法和更相減損術(shù)的步驟即可,輾轉(zhuǎn)相除法和更相減損術(shù)的應(yīng)用,互動(dòng)探究,解析 用輾轉(zhuǎn)相除法： 803628， 36844， 8420. 故80和36的最大公約數(shù)是4.,用更相減損術(shù)檢驗(yàn)： 803644， 44368， 36828， 28820， 20812， 1284， 844. 故80和36的最大公約數(shù)是4.,規(guī)律總結(jié) 更相減損術(shù)與輾轉(zhuǎn)相除法都能求兩個(gè)數(shù)的最大公約數(shù)，二者的區(qū)別與聯(lián)系如下表.,(1)用輾轉(zhuǎn)相除法求288與123的最大公約數(shù) (2)用更相減損術(shù)求57與93的最大公約數(shù) (3)求567與405的最小公倍數(shù) 解析 (1)288123242,12342239， 423913,39313， 288和123的最大公約數(shù)是3. (2)(93,57)(36,57)(36,21)(15,21)(15,6)(9,6)(3,6)(3,3)， 93與57的最大公約數(shù)是3.,(3)5674051162 405162281 1628120 81是567與405的最大公約數(shù)，從而567與405的最小公倍數(shù)為567405812835.,(1)(2015三明高一檢測)用秦九韶算法計(jì)算多項(xiàng)式f(x)3x64x55x46x37x28x1，當(dāng)x0.4時(shí)的值時(shí)，需要做乘法和加法的次數(shù)分別是( ) A6,6 B5,6 C5,5 D6,5 (2)已知一個(gè)五次多項(xiàng)式f(x)2x54x33x25x1，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x3是的值,用秦九韶算法求多項(xiàng)式的值,探究 1.用秦九韶算法求多項(xiàng)式的值時(shí)，幾次多項(xiàng)式就做幾次乘法運(yùn)算，對嗎？ 2用秦九韶算法求多項(xiàng)式f(x)anxnan1xn1a1xa0在xx0時(shí)的值時(shí)，v0是什么？v1呢？ 解析 (1)將多項(xiàng)式改寫成如下形式f(x)(3x4)x5)x6)x7)x8)x1，顯然，把x0.4代入計(jì)算其值時(shí)，共做了6次乘法，6次加法,(2)因?yàn)閒(x)(2x0)x4)x3)x5)x1， v02， v12306， v263414， v3143345， v44535130， v513031391， 所以f(3)391. 答案 (1)A (2)391,規(guī)律總結(jié) 用秦九韶算法時(shí)要正確將多項(xiàng)式的形式進(jìn)行改寫，然后由內(nèi)向外依次計(jì)算當(dāng)多項(xiàng)式函數(shù)中間出現(xiàn)空項(xiàng)時(shí)，要以系數(shù)為零的齊次項(xiàng)補(bǔ)充,用秦九韶算法求多項(xiàng)式f(x)7x76x65x54x43x32x2x當(dāng)x3時(shí)的值 探究 解決本題首先需要將原多項(xiàng)式化成f(x)(7x6)x5)x4)x3)x2)x1)x的形式，其次再弄清v0，v1，v2，v7分別是多少，再針對這些式子進(jìn)行計(jì)算,解析 f(x)(7x6)x5)x4)x3)x2)x1)x，所以有 v07； v173627； v2273586； v38634262； v426233789； v5789322369； v62369317108； v77108321324. 故當(dāng)x3時(shí)，多項(xiàng)式f(x)7x76x65x54x43x32x2x的值為21324.,試用輾轉(zhuǎn)相除法求325、130、270的最大公約數(shù) 探究 應(yīng)用輾轉(zhuǎn)相除法去除，即依據(jù)mnqr反復(fù)執(zhí)行，直到r0為止,求多個(gè)數(shù)的最大公約數(shù),探索延拓,解析 325130265,130652， 325與130的最大公約數(shù)是65. 27065410,651065,10652， 65與270的最大公約數(shù)是5， 故325、130、270三個(gè)數(shù)的最大公約數(shù)為5. 規(guī)律總結(jié) 理解輾轉(zhuǎn)相除法的實(shí)質(zhì)，從計(jì)算結(jié)果上看，輾轉(zhuǎn)相除法是以相除余數(shù)為零而得到結(jié)果的,求三個(gè)數(shù)175,100,75的最大公約數(shù) 探究 求三個(gè)數(shù)的最大公約數(shù)時(shí)，可以先求出其中兩個(gè)數(shù)的最大公約數(shù)，再求這個(gè)最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù)，所得的結(jié)果就是這三個(gè)數(shù)的最大公約數(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. 點(diǎn)評(píng) 本題的解法可以推廣到求多個(gè)數(shù)的最大公約數(shù)，只需依次計(jì)算即可,已知f(x)3x42x24x2，利用秦九韶算法求f(2)的值 錯(cuò)解 f(x)(3x22)x4)x2， v13(2)2214； v214(2)424； v324(2)250. 故f(2)50. 錯(cuò)因分析 所求f(2)的值是正確的，但是錯(cuò)解中沒有抓住秦九韶算法原理的關(guān)鍵，正確改寫多項(xiàng)式，并使每一次計(jì)算只含有一次項(xiàng),誤區(qū)警示,正解 f(x)3x40x32x24x2(3x0)x2)x4)x2， v03， v13(2)06； v26(2)214； v314(2)424； v424(2)250. 故f(2)50.,(2015貴陽高一檢測)用秦九韶算法計(jì)算多項(xiàng)式f(x)1235x8x279x36x45x53x6在x4的值時(shí)，v3的值為_ 答案 57,解析 多項(xiàng)式變形為f(x)3x65x56x479x38x235x12(3x5)x6)x79)x8)x35)x12， 當(dāng)x4時(shí)， v03， v13(4)57， v27(4)634， v334(4)7957， v457(4)8220， v5220(4)35845， v6845(4)123392.,1下列有關(guān)輾轉(zhuǎn)相除法的說法正確的是( ) A它和更相減損術(shù)一樣是求多項(xiàng)式值的一種方法 B基本步驟是用較大的數(shù)m除以較小的數(shù)n得到除式mnqr，直至rn為止 C基本步驟是用較大的數(shù)m除以較小的數(shù)n得到除式mqnr(0rn)反復(fù)進(jìn)行，直到r0為止 D以上說法均不正確 答案 C,2更相減損術(shù)的理論依據(jù)是( ) A每次操作所得的兩數(shù)和前兩數(shù)具有相同的最小公倍數(shù) B每次操作所得的兩數(shù)和前兩數(shù)具有相同的最大公約數(shù) C每次操作所得的兩數(shù)和前兩數(shù)的最小公倍數(shù)不同 D每次操作所得的兩數(shù)和前兩數(shù)的最大公約數(shù)不同 答案 B,3用更相減損術(shù)求123與51的最大公約數(shù)時(shí)，需做減法的次數(shù)是( ) A3 B5 C6 D8 答案 D,解析 1235172， 725121， 512130， 30219， 21912， 1293， 936， 633， 所以共做了8次減法,4(2015山西省太原五中月考)用秦九韶算法求多項(xiàng)式f(x)7x66x53x22當(dāng)x4時(shí)的值時(shí)，先算的是( ) A4416 B7428 C44464 D74634 答案 D 解析 本題考查秦九韶算法的計(jì)算原理因?yàn)閒(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0，所以用秦九韶算法求多項(xiàng)式f(x)7x66x53x22當(dāng)x4時(shí)的值時(shí)，先算的是74634，故選D.,5分別用輾轉(zhuǎn)相除法和更相減損術(shù)求357和105的最大公約數(shù)，并求最小公倍數(shù) 解析 輾轉(zhuǎn)相除法：357105342,10542221,42212. 故105與357的最大公約數(shù)為21. 更相減損術(shù)：357105252,252105147,14710542,1054263， 634221,422121. 故105與357的最大公約數(shù)為21.最小公倍數(shù)為105357211785.,