13算法案例.ppt

1、一位美國的幼兒園老師為了教育孩子火海逃生，引導(dǎo)學(xué)生做了一個非 非常有趣的游戲“火海逃生”。老師將許多乒乓球放進瓶子，只露出 系著的棉線?；ㄆ看泶髽牵毤毜钠款i是惟一的出口，七只乒乓球則 是樓里的居民，要求當(dāng)大樓突然起火時，全體居民能在短時間里安全逃 離。七名學(xué)生興奮地上場了，他們各執(zhí)一根棉線，報警器一響，都以最 快的反應(yīng)拉扯繩子，可一個“人”也沒能脫離火海，原來，七只乒乓球都 卡在了瓶口。又開始了第二次實驗？,火海逃生,這幾個學(xué)生面面相覷，只見其中一個小聲跟同伴們商量了幾句，這 回大家沒有各顧各地拉繩子，而是由左到右依次地拉。果然，報警 器的尾音還沒結(jié)束，七位“居民”已離開了出口，轉(zhuǎn)移到了安

2、全地帶。,運籌帷幄，決勝千里,算法案例之求最大公約數(shù),求以下幾組正整數(shù)的最大公約數(shù)。 (注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來表示 m和n的最大公約數(shù)。) （1）（18，30） （2）（24，16） （3）（63，63） （4）（72，8） （5）（301，133 ）,想一想，如何求8251與6105的最大公約數(shù)？,例、求18與24的最大公約數(shù)：,6；,8；,63；,8；,7；,短除法,窮舉法（也叫枚舉法） 步驟： 從兩個數(shù)中較小數(shù)開始 由大到小列舉，直到找到公 約數(shù)立即中斷列舉，得到的 公約數(shù)便是最大公約數(shù) 。,窮舉法,定理： 已知m,n,r為正整數(shù)，若m=nq+r（

3、0rn）（即r=m MOD n）,則（m,n）=(n,r)。,輾轉(zhuǎn)相除法,分析：m=nq+r r=m-nq ,例1、求8251和6105的最大公約數(shù)。,148=37 4,=37,8251=61051+2146,（8251，6105） =（6105，2146）,6105=2146 2+1813,=（2146，1813）,2146=1813 1+333,=（1813，333）,1813=333 5+148,=（333，148）,333=148 2+37,=（148，37）,解：,練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)： （1）（225，135） （2）（98，196） （3）（72，168） （

4、4）（153，119）,45,98,24,17,8251和6105的最大公約數(shù),解： 8251=61051+2146 6105=2146 2+1813 2146=1813 1+333 1813=333 5+148 333=148 2+37 148=37 4,（8251，6105） =（6105，2146） =（2146，1813） =（1813，333） =（333，148） =（148，37） =37,關(guān)系式m=np+r中m,n,r得取值變化情況,8251,6105,2146,6105,2146,2146,1813,1813,333,1813,333,148,148,333,37,148,3

5、7,0,輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：,輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟， 這實際上是一個循環(huán)結(jié)構(gòu),思考：輾轉(zhuǎn)相除直到何時結(jié)束？主要運用的是哪種算法結(jié)構(gòu)？,如此循環(huán)，直到得到結(jié)果。, 輸入兩個正整數(shù)m和n；, 求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中；,更新被除數(shù)和余數(shù)：m=n，n=r。,判斷余數(shù)r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn) 向第步繼續(xù)循環(huán)執(zhí)行。,程序：INPUT “m，n=”;m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND,更相減損術(shù),同理：a,b,c為正整數(shù)，若a-b=c，則（a,b）=(

6、b,c)。,“更相減損術(shù)”（也是求兩個正整數(shù)的最大公約數(shù)的算法） 步驟：,第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。 若是，則用2約簡；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較 小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所 得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公 約數(shù)。,例、用更相減損術(shù)求98與63的最大公約數(shù) （自己按照步驟求解）,解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。,= 7,所以，98和63的最大公約數(shù)等于7。,（98，63） =（63，35）,98-63=35,63-35=28,=（35，28）,35-28=7,

7、=（28，7）,28-7=21,=（21，7）,21-7=14,=（14，7）,14-7=7,=（7，7）,練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)： （1）（225，135） （2）（98，196） （3）（72，168） （4）（153，119）,45,98,24,17,例 用更相減損術(shù)求98與63的最大公約數(shù),解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)， 并輾轉(zhuǎn)相減 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7所以，98和63的最大公約數(shù)等于7。,（98，63） =（63，35） =（35，28） =（28，7） =（21，7） =

8、（14，7） =（7，7） =7,關(guān)系式a-b=c中a,b,c得取值變化情況,更相減損是一個反復(fù)執(zhí)行直到減數(shù)等于差時停止的步驟， 這實際也是一個循環(huán)結(jié)構(gòu),思考：更相減損直到何時結(jié)束？運用的是哪種算法結(jié)構(gòu)？,程序： INPUT “a,b”;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF ba THEN t=a a=b b=t END IF a=a-b LOOP UNTIL a=b PRINT a*2i END,輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：,小 結(jié),（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法 為主，更相減損術(shù)以減法為