1.4.1 算法案例(1)—輾轉(zhuǎn)相除法、更相減損術(shù)與秦九韶算法doc.doc

1.4.1 算法案例（1）輾轉(zhuǎn)相除法、更相減損術(shù)與秦九韶算法目標(biāo)：理解并掌握輾轉(zhuǎn)相除法、更相減損術(shù)與秦九韶算法一.輾轉(zhuǎn)相除法實(shí)例1.求8251與6105的最大公約數(shù).（輾轉(zhuǎn)相除法思想的應(yīng)用） 第一步：用較大的數(shù)除以較小的數(shù)，得. 分析：6105與2146的公約數(shù)一定是8251與6105的公約數(shù)；反之8251與6105的公約數(shù)也一定是6105與2146的公約數(shù)。因此， 求8251與6105的最大公約數(shù)等同于求6105與2146的最大公約數(shù). 第二步：用較大的數(shù)除以較小的數(shù)，得. 分析：同理6105與2146的最大公約數(shù)等同于2146與1813的最大公約數(shù). 第三步：用較大的數(shù)除以較小的數(shù)，得. 分析：同理2146與1813的最大公約數(shù)等同于1813與333的最大公約數(shù). 第四步：用較大的數(shù)除以較小的數(shù)，得. 分析：. 第五步：用較大的數(shù)除以較小的數(shù)，得. 分析：. 第六步：用較大的數(shù)除以較小的數(shù)，得. 分析：148與37的最大公約數(shù)是37，所以，8251與6105的最大公約數(shù)就是37. 這個(gè)問題的解決，應(yīng)用的就是輾轉(zhuǎn)相除法，反復(fù)進(jìn)行除法運(yùn)算，直到余數(shù)為0，最大公約數(shù)也就出來了，反復(fù)相除的運(yùn)算在計(jì)算機(jī)里我們可以應(yīng)用循環(huán)語句來實(shí)現(xiàn).實(shí)例2.設(shè)計(jì)一個(gè)算法，求兩個(gè)正整數(shù)的最大公約數(shù).解：問題的算法如下： 第一步：輸入. 第二步：計(jì)算除以的余數(shù). 第三步：.第四步：如果，則與的最大公約數(shù)為，否則返回第二步. 其相應(yīng)的程序框圖如下： 相應(yīng)的計(jì)算機(jī)程序如下：INPUT m, nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND 二.更相減損術(shù) 九章算術(shù)是我們中國古代的數(shù)學(xué)專著，其中介紹了另一種求兩個(gè)數(shù)的最大公約數(shù)的有效方法，即更相減損術(shù).其具體算法如下： 第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)。如果是，用2約簡；如果不是，執(zhí)行第二步. 第二步：用較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到某一步減數(shù)與差相等為止，則這個(gè)數(shù)或這個(gè)數(shù)與約簡的數(shù)的積就是所求的最大公約數(shù).實(shí)例3.用更相減損術(shù)求98與63的最大公約數(shù).9863=356335=283528=7287=21217=14147=7所以98與63的最大公約數(shù)是7.三.秦九韶算法問題的引入：如何求多項(xiàng)式當(dāng)時(shí)的值.方法一：一個(gè)自然的做法是把5帶入多項(xiàng)式，計(jì)算各項(xiàng)的值，然后把它們加起來，這時(shí)，我們一共做了次乘法運(yùn)算，次加法運(yùn)算.方法二：先計(jì)算的值，然后依次計(jì)算，的值，每次都應(yīng)用上一次的計(jì)算結(jié)果。這時(shí)我們一共做了4次乘法運(yùn)算，5次加法運(yùn)算。 把第二種算法與第一種算法相比較，很顯然，乘法的次數(shù)減少了，因而能夠提高運(yùn)算效率。計(jì)算機(jī)做一次乘法所用的時(shí)間比做一次加法所用的時(shí)間要長得多，所以應(yīng)用第二種方法，計(jì)算機(jī)能更快地得到結(jié)果。 第三種算法：我國南宋時(shí)期數(shù)學(xué)家秦九韶在他所著的數(shù)書九章中提出如下算法：求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號內(nèi)一次多項(xiàng)式的值，即然后由內(nèi)向外逐次計(jì)算一次多項(xiàng)式的值，即： 這樣，求次多項(xiàng)式的值的問題就轉(zhuǎn)化為求個(gè)一次因式的值的問題了，而且，從算法步驟上來看，一共只用了個(gè)乘法、個(gè)加法.實(shí)例4.已知一個(gè)多項(xiàng)式為，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)時(shí)的值.解：根據(jù)秦九韶算法，我們把改寫為：按從內(nèi)到外的順序依次計(jì)算每一個(gè)一次多項(xiàng)式當(dāng)時(shí)的值：所以當(dāng)時(shí)，的值為.秦九韶算法的程序框圖與計(jì)算機(jī)語言：設(shè)計(jì)算法計(jì)算多項(xiàng)式的值.分析秦九韶算法，我們看到，用秦九韶算法計(jì)算一個(gè)次多項(xiàng)式時(shí)，若令，則有：，其中是一個(gè)要反復(fù)執(zhí)行的步驟，因此可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn). 算法如下：第一步：輸入多項(xiàng)式的次數(shù)、最高次項(xiàng)的系數(shù)和的值.第二步：將的值初始化為，將的值初始化為.第三步：輸入次項(xiàng)的系數(shù).第四步：.第五步：判斷是否大于或等于0，若是，則返回第三步，否則，輸出多項(xiàng)式的值.其程序框圖如圖：根據(jù)程序框圖，可以寫出計(jì)算機(jī)程序如下：INPUT “n=”; nINPUT “an=”; aINPUT “x=”, xv=ai=n-1WHILE i=0PRINT iINPUT “ai”; av=v*x+ai=i-1WENDPRINT vEND四.課外練習(xí)：優(yōu)化設(shè)計(jì).五.補(bǔ)充練習(xí)1.用輾轉(zhuǎn)相除法求294與84的最大公約數(shù)時(shí)，需要做除法的次數(shù)是 （ ） A.1 B.2 C.3 D.42.用更相減損術(shù)求459與357的最大公約數(shù)時(shí)，需要做減法的次數(shù)是 （ ） A.4 B.5 C.6 D.73.利用秦九韶算法求當(dāng)時(shí)，的值， 下列說法中正確的是 （ ）A.先求B.先求，第二步求C.直接運(yùn)算求解D.以上都不對4.求117與182的最大公