中國古代數(shù)學(xué)中的算法案例課件（人教b版必修3）

1．3中國古代數(shù)學(xué)中的算法案例

1．求兩個正整數(shù)最大公約數(shù)的算法(1)更相減損之術(shù)(等值算法)用兩數(shù)中較大的數(shù)減去較小的數(shù)，再用

和

構(gòu)成新的一對數(shù)，再用大數(shù)減小數(shù)，以同樣的操作一直做下去，直到產(chǎn)生

，這個數(shù)就是最大公約數(shù)．差數(shù)較小的數(shù)一對相等的數(shù)(2)用“等值算法〞求最大公約數(shù)的程序2．割圓術(shù)用圓內(nèi)接正多邊形面積逐漸逼近

的算法是計(jì)算圓周率的一種方法．圓的面積3．秦九韶算法(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，那么遞推公式為

，其中k＝1,2，…，n.(2)計(jì)算P(x0)的方法先計(jì)算

，然后

逐層計(jì)算，直到

，然后加上

．最內(nèi)層的括號由內(nèi)向外最外層括號常數(shù)項(xiàng)本節(jié)重點(diǎn)：秦九韶算法的原理、算法設(shè)計(jì)和無限逼近的思想．本節(jié)難點(diǎn)：理解算法案例的內(nèi)容及具體算法設(shè)計(jì)的關(guān)鍵步驟1．求兩個正整數(shù)最大公約數(shù)的算法(1)輾轉(zhuǎn)相除法①輾轉(zhuǎn)相除法的理論根底m，n，r為正整數(shù)，假設(shè)m＝nq＋r(0≤r<n)(即r＝mmodn)，那么(m，n)＝(n，r)．其中(m，n)表示m和n的最大公約數(shù)．事實(shí)上，由m＝nq＋r知n和r的公約數(shù)都是m和n的公約數(shù)；由r＝m－nq知m和n的公約數(shù)都是n和r的公約數(shù)．故m和n的公約數(shù)與n和r的公約數(shù)都相同，其最大公約數(shù)也相同．②輾轉(zhuǎn)相除法的步驟用輾轉(zhuǎn)相除法求兩個正整數(shù)的最大公約數(shù)，其算法可以用自然語言描述如下：第一步，給定兩個正整數(shù)m，n；第二步，計(jì)算m除以n所得的余數(shù)r；第三步，m＝n，n＝r；第四步，假設(shè)r＝0，那么m，n的最大公約數(shù)等于m；否那么，返回第二步．從其算法思想我們可以看出，輾轉(zhuǎn)相除法的根本步驟是用較大的數(shù)(用a表示)除以較小的數(shù)(用b表示)，得到除式：a＝nb＋r(0≤r<b)．由于這是一個反復(fù)執(zhí)行的步驟，且執(zhí)行的次數(shù)由余數(shù)r是否等于0決定，所以我們可以把它看作一個循環(huán)體，用循環(huán)結(jié)構(gòu)就可以來實(shí)現(xiàn)其算法．(2)更相減損術(shù)(“等值算法〞)步驟：我們以求119和85這兩個數(shù)的最大公約數(shù)為例加以說明：以兩數(shù)中較大的數(shù)減去較小的數(shù)，即119－85＝34，以差數(shù)34和較小的數(shù)85構(gòu)成新的一對數(shù)，對這一對數(shù)再用大數(shù)減去小數(shù)，即85－34＝51，再以差數(shù)51和34構(gòu)成新的一對數(shù)，大數(shù)減去小數(shù)，這樣的操作一直做下去，直到產(chǎn)生一對相等的數(shù)，這個數(shù)就是最大公約數(shù)．整個操作如下：(119,85)→(34,85)→(34,51)→(34,17)→(17,17)，∴119與85的最大公約數(shù)為17.從其算法思想我們可以看出，更相減損術(shù)的根本步驟是用較大的數(shù)(用a表示)減去較小的數(shù)(用b表示)，得到等式：r＝a－b(r為差數(shù))．由于這是一個反復(fù)執(zhí)行的步驟，且執(zhí)行的次數(shù)由差數(shù)與較小的數(shù)是否相等決定，所以我們可以把它看作一個循環(huán)體，用循環(huán)結(jié)構(gòu)就可以實(shí)現(xiàn)其算法．2．把一個n次多項(xiàng)式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫成如下形式：f(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求多項(xiàng)式的值時，首先計(jì)算最內(nèi)層括號內(nèi)一次多項(xiàng)式的值，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值．2．秦九韶算法的依據(jù)是加法對乘法的分配律，把多項(xiàng)式的運(yùn)算分解為一次因式的乘法和加法運(yùn)算．3．劉徽的割圓術(shù)是利用圓內(nèi)接正多邊形，隨著邊數(shù)的增多，正多邊形的面積無限逼近圓的面積的無限逼近思想，來求圓周率π的近似值．[例1]求80和36的最大公約數(shù)．[解析]

80－36＝44，44－36＝8，36－8＝28，28－8＝20，20－8＝12，12－8＝4，8－4＝4.∴80和36的最大公約數(shù)是4.[點(diǎn)評]當(dāng)大數(shù)減小數(shù)的差等于小數(shù)時停止減法，較小的數(shù)就是兩數(shù)的最大公約數(shù)．用更相減損術(shù)求57與93的最大公約數(shù)．[解析]

(93,57)―→(36,57)―→(36,21)―→(15,21)―→(15,6)―→(9,6)―→(3,6)―→(3,3)，∴93與57的最大公約數(shù)是3.[例2]求98和280的最大公約數(shù)．[解析]

280＝98×2＋84,98＝84×1＋14,84＝14×6＋0.∴最大公約數(shù)為14.[點(diǎn)評]用輾轉(zhuǎn)相除法求最大公約數(shù)步驟較少，而更相減損術(shù)雖然步驟較長，但運(yùn)算簡單．用輾轉(zhuǎn)相除法求72和168的最大公約數(shù)．[解析]

168＝72×2＋24,72＝24×3＋0.∴最大公約數(shù)為24.[例3]用秦九韶算法求多項(xiàng)式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x當(dāng)x＝3時的值．[解析]

x＝3a7＝7v0＝a7＝7；a6＝6v1＝v0x＋a6＝7×3＋6＝27；a5＝5v2＝v1x＋a5＝27×3＋5＝86；a4＝4v3＝v2x＋a4＝86×3＋4＝262；a3＝3v4＝v3x＋a3＝262×3＋3＝789；a2＝2v5＝v4x＋a2＝789×3＋2＝2369；a1＝1v6＝v5x＋a1＝2369×3＋1＝7108；a0＝0v7＝v6x＋a0＝7108×3＋0＝21324.所以f(3)＝21324.[點(diǎn)評]利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)鍵是能正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外逐次計(jì)算，由于后項(xiàng)計(jì)算需用到前項(xiàng)的結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保中間結(jié)果的準(zhǔn)確性．用秦九韶算法時，關(guān)鍵是理解在其中用到的遞推公式 ，其中k＝1,2，…，n.一個5次多項(xiàng)式函數(shù)f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求這個多項(xiàng)式當(dāng)x＝5時的值．[解析]

根據(jù)秦九韶算法原理，先將所給的多項(xiàng)式進(jìn)行改寫，然后由內(nèi)向外逐層計(jì)算即可．f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8＝((((5x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，v0＝5，v1＝5×5＋2＝27，v2＝27×5＋3.5＝138.5，v3＝138.5×5－2.6＝689.9，v4＝689.9×5＋1.7＝3451.2，v5＝3451.2×5－0.8＝17255.2.所以，當(dāng)x＝5時，多項(xiàng)式的值等于17255.2.[例4]求三個數(shù)324,243,270的最大公約數(shù)．[解析]324＝243×1＋81,243＝81×3＋0，那么324與243的最大公約數(shù)為a＝81.又270＝81×3＋27,81＝27×3＋0，那么324,243,270的最大公約數(shù)為27.[點(diǎn)評]求三個數(shù)的最大公約數(shù)，可先求兩數(shù)的最大公約數(shù)a，然后求a與第三個數(shù)的最大公約數(shù)b，那么b為所求的三數(shù)的最大公約數(shù)．該題解法可推廣到求多個數(shù)的最大公約數(shù)．求324,243和135的最大公約數(shù)．[解析](324,243)―→(81,243)―→(81,162)―→(81,81)那么324與243最大公約數(shù)為81.又(81,135)―→(81,54)―→(27,54)―→(27,27)，那么81與135的最大公約數(shù)為27，∴324、243、135的最大公約數(shù)為27.[例5]求375,85的最小公倍數(shù)[解析]先求最大公約數(shù)，375＝85×4＋35,85＝35×2＋15,35＝15×2＋5,15＝5×3＋0.∴375與85的最大公約數(shù)是5，∴375與85的最小公倍數(shù)是(375×85)÷5＝6375.[點(diǎn)評]求兩個正整數(shù)的最小公倍數(shù)，即利用它們的積除以它們的最大公約數(shù)．此題求法可推廣到求多個數(shù)的情況．求80與36的最小公倍數(shù)．[解析]

先求最大公約數(shù)．80＝36×2＋836＝8×4＋4＝8＝4×2＋0∴80與36的最大公約數(shù)為4.∴80與36的最小公倍數(shù)是(80×36)÷4＝720.[例6]f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求這個多項(xiàng)式當(dāng)x＝2時的值時，做了幾次乘法？幾次加法？[誤解]根據(jù)秦九韶算法，把多項(xiàng)式改寫成如下形式f(x)＝((((x＋2)x＋3)x＋4)x＋5)x＋6.按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x＝2時的值：v1＝2＋2＝4，v2＝2v1＋3＝11，v3＝2v2＋4＝26，v4＝2v3＋5＝57，v5＝2v4＋6＝120.顯然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．[辨析]在v1中雖然“v1＝2＋2＝4〞，而計(jì)算機(jī)還是做了1次乘法“v1＝2×1＋2＝4〞．因?yàn)橛们鼐派厮惴ㄓ?jì)算多項(xiàng)式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0當(dāng)x＝x0時的值時，首先將多項(xiàng)式改寫成f(x)＝(…(anx＋an－1)x＋…＋a1)x＋a0，然后再計(jì)算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0無論an是不是1，這次的乘法都是要進(jìn)行的．[正解]由以上分析可知，做了5次乘法，5次加法．一、選擇題1．用更相減損之術(shù)求88與24的最大公約數(shù)為()A．2 B．7C．8 D．12[答案]C[解析]

(88,24)→(64,24)→(40,24)→(24,16)→(16,8)→(8,8)，故88與24的最大公約數(shù)為8.2．用秦九韶算法求多項(xiàng)式f(x)＝x3－3x2＋2x－11的值時，應(yīng)把f(x)變形為()A．x3－(3x＋2)x－11B．(x－3)x2＋(2x－11)C．(x－1)(x－2)x－11D．((x－3)x＋2)x－11[答案]

D3．用程序框圖表示“割圓術(shù)〞，將用到()A．順序結(jié)構(gòu)B．條件分支結(jié)構(gòu)C．順序結(jié)構(gòu)和循環(huán)結(jié)構(gòu)D．三種根本邏輯結(jié)構(gòu)[答案]D二、填空題4．三個數(shù)72,120,168的最大公約數(shù)是________．[答案]24[解析]

(72,120,168)→(72,120,168－120)→(72,120,48)→(72,120－72,48)→(72,48,48)→(72－48,48,48)→(24,48,48)→(24,48－24,48)→(24,24,48)→(24,24,48－24)→(24,24,24)．5．用秦九韶算法計(jì)算f(x)＝9x6＋3x5＋4x4＋6x3＋x2＋8x＋1，當(dāng)x＝3時的值，需要進(jìn)行________次乘法和_____