高一數(shù)學(xué) 1.3算法案例 新人教A必修3

一位美國(guó)的幼兒園老師為了教育孩子火海逃生，引導(dǎo)學(xué)生做了一個(gè)非非常有趣的游戲──“火海逃生”。老師將許多乒乓球放進(jìn)瓶子，只露出系著的棉線。花瓶代表大樓，細(xì)細(xì)的瓶頸是惟一的出口，七只乒乓球則是樓里的居民，要求當(dāng)大樓突然起火時(shí)，全體居民能在短時(shí)間里安全逃離。七名學(xué)生興奮地上場(chǎng)了，他們各執(zhí)一根棉線，報(bào)警器一響，都以最快的反應(yīng)拉扯繩子，可一個(gè)“人”也沒(méi)能脫離火海，原來(lái)，七只乒乓球都卡在了瓶口。又開(kāi)始了第二次實(shí)驗(yàn)？火海逃生這幾個(gè)學(xué)生面面相覷，只見(jiàn)其中一個(gè)小聲跟同伴們商量了幾句，這回大家沒(méi)有各顧各地拉繩子，而是由左到右依次地拉。果然，報(bào)警器的尾音還沒(méi)結(jié)束，七位“居民”已離開(kāi)了出口，轉(zhuǎn)移到了安全地帶。運(yùn)籌帷幄，決勝千里編輯ppt算法案例之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。(注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來(lái)表示m和n的最大公約數(shù)。)（1）（18，30）（2）（24，16）（3）（63，63）（4）（72，8）（5）（301，133）解：21824用公有質(zhì)因數(shù)2除，3912用公有質(zhì)因數(shù)3除，343和4互質(zhì)不除了。得：18和24最大公約數(shù)是：2×3＝6

想一想，如何求8251與6105的最大公約數(shù)？

例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法編輯ppt開(kāi)始i=m+1輸入：m,nmMODi=0且nMODi=0?i=i-1輸出：i結(jié)束YNm>n?t=m,m=n,n=tNY窮舉法（也叫枚舉法）步驟：從兩個(gè)數(shù)中較小數(shù)開(kāi)始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)。窮舉法編輯ppt定理：已知m,n,r為正整數(shù)，若m=nq+r（0≤r<n）（即r=mMODn）,則（m,n）=(n,r)。輾轉(zhuǎn)相除法分析：m=nq+r……①r=m-nq……②例1、求8251和6105的最大公約數(shù)。148=37×4=378251=6105×1+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）解：編輯ppt練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417編輯ppt次數(shù)123456mnr8251和6105的最大公約數(shù)解：8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，37）=37關(guān)系式m=np+r中m,n,r得取值變化情況82516105214661052146214618131813333181333314814833337148370編輯ppt輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)

思考：輾轉(zhuǎn)相除直到何時(shí)結(jié)束？主要運(yùn)用的是哪種算法結(jié)構(gòu)？如此循環(huán)，直到得到結(jié)果。①輸入兩個(gè)正整數(shù)m和n；②求余數(shù)r：計(jì)算m除以n，將所得余數(shù)存放到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r。④判斷余數(shù)r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn)向第②步繼續(xù)循環(huán)執(zhí)行。編輯ppt開(kāi)始輸入：m,n輸出：m結(jié)束r=0?m=nNYr=mMODnn=r程序：

INPUT“m，n=”;m,n

DO

r=mMODn

m=n

n=r

LOOPUNTILr=0

PRINTm

END編輯ppt更相減損術(shù)同理：a,b,c為正整數(shù)，若a-b=c，則（a,b）=(b,c)?！案鄿p損術(shù)”（也是求兩個(gè)正整數(shù)的最大公約數(shù)的算法）步驟：第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。編輯ppt例、用更相減損術(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=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）編輯ppt練習(xí)：用更相減損術(shù)求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417編輯ppt例

用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減

98-63=35

63-35=28

35-28=7

28-7=2121-7=14

14-7=7

所以，98和63的最大公約數(shù)等于7。（98，63）=（63，35）=（35，28）=（28，7）=（21，7）=（14，7）=（7，7）=7次數(shù)123456a986335282114b633528777c3528721147關(guān)系式a-b=c中a,b,c得取值變化情況編輯ppt更相減損是一個(gè)反復(fù)執(zhí)行直到減數(shù)等于差時(shí)停止的步驟，這實(shí)際也是一個(gè)循環(huán)結(jié)構(gòu)

思考：更相減損直到何時(shí)結(jié)束？運(yùn)用的是哪種算法結(jié)構(gòu)？編輯ppt程序：INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND開(kāi)始輸入：a,b輸出：a×2i結(jié)束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?YNNNYi=0i=i+1編輯ppt輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：小結(jié)（1）都是求最大公