1.3算法案例-【精品課件】

1、算法案例33 59 15如：18 30 2則18、30的最大公約數(shù)是23=6問(wèn)題1：在小學(xué)我們學(xué)過(guò)求兩個(gè)正數(shù)的最大公約數(shù)的方法：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所有的商是互質(zhì)為止，然后把所有的除數(shù)連乘起來(lái)。 但是，當(dāng)兩個(gè)數(shù)公有的質(zhì)因數(shù)較大時(shí)（如8251和6150）用上面的方法行嗎？一、案例1： 輾轉(zhuǎn)相除法與更相減損術(shù)1、輾轉(zhuǎn)相除法例：求8251與6105的最大公約數(shù)。解： 8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374所以8251與6105的最大公約數(shù)是37思考2：你能把輾轉(zhuǎn)相除法編

2、成一個(gè)計(jì)算機(jī)程序嗎？思考1：輾轉(zhuǎn)相除法的原理是什么？算法分析：第一步，給定兩個(gè)正數(shù)m,n（設(shè)mn）。第二步，計(jì)算m除以n的余數(shù)r。第三步，m=n,n=r第四步，若r=0，則m、n的最大公約數(shù)為m。否則返回第二步。程序框圖如下圖所示：求m除以n的余數(shù)是輸入m,nm=n輸出m開(kāi)始結(jié)束n=rr=0?否程序如下所示：INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND 思考1：你能用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個(gè)正數(shù)的最大公約數(shù)嗎？試寫(xiě)出算法步驟、程序框圖和程序。算法分析：第一步，給定兩個(gè)正數(shù)m,n（設(shè)mn）。第二步，r=1。第三步，若r0，則執(zhí)行第四步。

3、否則執(zhí)行第七步。第四步，求m除以n的余數(shù)r。第五步，m=n。第六步，n=r，返回第三步。第七步，輸出m。程序框圖和程序如下：思考2：怎么求兩個(gè)正數(shù)的最小公倍數(shù)？程序框圖輸入m,n開(kāi)始n=rm=n輸出m是否結(jié)束求m除以n的余數(shù)rr=1r0?程序INPUT m,nr =1WHILE r0r =m MOD nm=nn=rWENDPRINT mEND2、更相減損術(shù)原理：第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。這個(gè)數(shù)（等數(shù)）或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)。第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作

4、，直到所得的數(shù)相等為止。則例1：用更相減損術(shù)求98與63的最大公約數(shù)。 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減得，如圖所示：9863=356335=28287=213528=7217=14147=7所以，98和63的最大公約數(shù)等于7。 思考：把更相減損術(shù)與輾轉(zhuǎn)相除法比較，你有什么發(fā)現(xiàn)？你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正數(shù)的最大公約數(shù)嗎？ 答：輾轉(zhuǎn)相除法與更相減損術(shù)的基本原理是相似的，主要區(qū)別在于輾轉(zhuǎn)相除法用的是除法運(yùn)算，即輾轉(zhuǎn)相除，而更相減損術(shù)用的是減法運(yùn)算，即輾轉(zhuǎn)相減，但實(shí)質(zhì)都是一個(gè)不斷的遞歸過(guò)程。更相減損術(shù)的程序框圖如右圖所示：m=d輸出2kdk=k+1n=n/2m=

5、m/2d=mnd=mn開(kāi)始輸入m,n（mn）k=0m,n均為偶數(shù)？是dn？m=nn=d是否否否是結(jié)束dn?INPUT “m,n=”;m,nIF mn THENa=mm=nWEND k=0WHILE m MOD 2=0 AND n MOD 2=0m=m/2k=k+1n=n/2d=mnWHILE dnIF dn THEN ELSEm=nEND IFd=mnd=2k*d PRINT dEND n=aEND IFn=dWEND m=d問(wèn)題2：怎樣求多項(xiàng)式 當(dāng)x=5的值呢？方法1：把5代入多項(xiàng)式，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。這時(shí)共做了1+2+3+4=10次乘法運(yùn)算，5次加法運(yùn)算。方法2：先計(jì)算x2,

6、再依次計(jì)算x2x, (x2x) x ,(x2x) x) x的值,這樣每次都可以利用上一次計(jì)算的結(jié)果。這時(shí)，我們一共做了4次乘法運(yùn)算，5次加法運(yùn)算。思考：有沒(méi)有更有效的算法呢？二、案例2： 秦九韶算法把一個(gè)多項(xiàng)式 改寫(xiě)成如下形式： 求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)的值，即然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即 這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值。 上述方法稱(chēng)為秦九韶算法。直到今天， 這種算法仍是多項(xiàng)式求值比較先進(jìn)的算法。 例2、已知一個(gè)5次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5時(shí)的值。 解：根據(jù)秦九韶算法，把多項(xiàng)式改寫(xiě)成如下形式： 按照從內(nèi)到外的順序，依次計(jì)

7、算一次多項(xiàng)式當(dāng)x=5時(shí)的值：所以，當(dāng)x=5時(shí)，多項(xiàng)式的值等于14130.2。思考：用秦九韶算法求n次多項(xiàng)式當(dāng)x= x0（ x0是任意實(shí)數(shù)）時(shí)的值，需要多少次乘法運(yùn)算，多少次加法運(yùn)算？秦九韶算法的算法分析： 觀察上述秦九韶算法中的n個(gè)一次式，可見(jiàn)vk的計(jì)算要用到vk-1的值，若令v0 = an ，我們可以得到下面的公式： 這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。算法如下：第一步，輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值。第二步，將v的值初始化為an ，將i的值初始化為n-1。第三步，輸入i次項(xiàng)的系數(shù)ai 。第四步，v=vx+ ai ，i=i-1。第五步，判斷i 是否大于

8、或等于0，若是，則返回第三步，否則輸出多項(xiàng)式的值v 。程序框圖如右圖所示：開(kāi)始v=vx+ aii=n1v= an 結(jié)束是否輸入ai 輸入n, an , x的值輸出v i0?i=i1三、案例3：進(jìn)位制1、進(jìn)位制：進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，約定滿(mǎn)二進(jìn)一，就是二進(jìn)制；滿(mǎn)十進(jìn)一，就是十進(jìn)制；滿(mǎn)十二進(jìn)一，就是十二進(jìn)制，滿(mǎn)六十進(jìn)一，就是六十進(jìn)制；等等。也就是說(shuō)，“滿(mǎn)幾進(jìn)一”就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾。2、十進(jìn)制：十位制使用09十個(gè)數(shù)字，計(jì)數(shù)時(shí)，幾個(gè)數(shù)字排成一行，從右起，第一位是個(gè)位，個(gè)位上的數(shù)字是幾，就表示幾個(gè)一；第二位是十位，十位上的數(shù)字是幾，就表示幾個(gè)十；接著依次是百位、千位

9、、萬(wàn)位如：十進(jìn)制3721中的3表示3 個(gè)千，7表示7個(gè)百，2表示2個(gè)十，1表示1個(gè)一，從而：3721= 3103+7102+2101+21003、k進(jìn)制：與十進(jìn)制類(lèi)似，其他的進(jìn)位制也可以按照位置原則計(jì)數(shù)，由于每一種進(jìn)位制的基數(shù)不同，所用的數(shù)字個(gè)數(shù)也不同，如二進(jìn)制用0和1兩個(gè)數(shù)字，七進(jìn)制用數(shù)字06七個(gè)數(shù)字。一般地，若k是一個(gè)大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫(xiě)在一起的形式： an an-1 a1 a0(k) (an , an-1 , , a1 , a0 N , 0 an k ,0 an-1 , , a1 , a0 n 是否成立，若是，則執(zhí)行第五步；否則，返回第三步。第五步

10、，輸出b的值。程序框圖否開(kāi)始結(jié)束輸入a, k, n的值b= 0i= 1把a(bǔ)的右邊第i位數(shù)字賦給tb = b + t ki-1i=i+1in?輸出b 是程序INPUT “a,k,n=”;a,k,n b=0i=i+1i=1t=a MOD 10DOb=b+t*k(i-1)a=a10t=a MOD 10LOOP UNTIL inPRINT bEND例5、把89化為二進(jìn)制數(shù)。解法1：因?yàn)?9=244+144=222+022=211+011=25+15=22+12=21+01=20+1所以89=244+1=2（ 222+0 ）+1=2 222+2 0 +1=2 2 （ 211+0） +2 0 +1十進(jìn)制化

11、k進(jìn)制=2 311+2 20 +2 0 +1=2 3 （ 25+1） +2 20 +2 0 +1=2 45+2 31+ 2 20 +2 0 +1=2 4 （ 22+1）+231+ 2 20 +2 0 +1=2 5 2+2 41 +231+ 2 20 +2 0 +1=2 5 （12+0）+2 41 +231+ 2 20+2 0 +1=12 6+ 0 2 5 +12 4 +123+0 2 2+ 0 21 +1 2 0=1011001 (2) 這種算法叫做除2取余法，還可以用下面的除法算式表示：1222解法2：8924422212211520余數(shù)011100 把上式中各步的余數(shù)從下到上排列，得到89

12、= 1011001 (2) 。 上述方法也可以推廣為把十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法，稱(chēng)為除k取余法。 例6、設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)“除k取余法”（kN ，2 k 9 ）。算法分析：從例5可知： 若十進(jìn)制數(shù)a除以k所得商是q0 ，余數(shù)是r0 ，即a= k q0 + r0 ，則r0是a的k進(jìn)制數(shù)的右邊第1位數(shù)； 若q0除以k所得商是q1 ，余數(shù)是r1 ，即q0 = k q1 + r1 ，則r1是a的k進(jìn)制數(shù)的右邊第2位數(shù)； 若qn-1除以k所得商是0 ，余數(shù)是rn ，則rn是a的k進(jìn)制數(shù)的左邊第1位數(shù)；算法步驟：第一步，給定十進(jìn)制正整數(shù)a和轉(zhuǎn)化后的數(shù)的基數(shù)k 。第二步，求出a除以k所得的商q ，余數(shù)r。

13、第三步，把所得的余數(shù)依次從右到左排列。第四步，若q 0，則a= q ，返回第二步；否則，輸出全部余數(shù)r排列得到的k進(jìn)制數(shù)。程序框圖如右圖所示：否是把所得的余數(shù)依次從右到左排列 輸入a,k開(kāi)始結(jié)束求a除以k的余數(shù)r q=0?求a除以k的商q 輸出全部余數(shù)r排列得到的k進(jìn)制數(shù)a=q程序如下：INPUT “a,k=”;a,kb=0i=0DOq=akr=a MOD kb=b+r*10ii=i+1a=qLOOP UNTIL q=0PRINT bEND四、小結(jié)：1、輾轉(zhuǎn)相除法2、更相減損術(shù)3、秦九韶算法4、進(jìn)位制五、練習(xí)：1、用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)。（1）225，135（2）98，196（3）72，168（4）153，1192、按照?qǐng)D1.33中的程序框圖給出的步驟，求f(x)=0.83 x5+0.41x4+0.16x3+0.33x2+0.5x+1當(dāng)x=5時(shí)的值。3、用“除k取余法”將十進(jìn)制數(shù)2008轉(zhuǎn)化為二進(jìn)制數(shù)和八進(jìn)制數(shù)。六、解答：1、（1）45（2）98（3）24（4）172、2881.753、2008=3730（8） 2008=11111011000（2）七、作業(yè)：習(xí)題1.