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

1、 一位美國的幼兒園老師為了教育孩子火海逃生，引導(dǎo)學(xué)生做了一個非一位美國的幼兒園老師為了教育孩子火海逃生，引導(dǎo)學(xué)生做了一個非非常有趣的游戲非常有趣的游戲“火海逃生火海逃生”。老師將許多乒乓球放進(jìn)瓶子，只露出。老師將許多乒乓球放進(jìn)瓶子，只露出系著的棉線。花瓶代表大樓，細(xì)細(xì)的瓶頸是惟一的出口，七只乒乓球則系著的棉線。花瓶代表大樓，細(xì)細(xì)的瓶頸是惟一的出口，七只乒乓球則是樓里的居民，要求當(dāng)大樓突然起火時，全體居民能在短時間里安全逃是樓里的居民，要求當(dāng)大樓突然起火時，全體居民能在短時間里安全逃離。七名學(xué)生興奮地上場了，他們各執(zhí)一根棉線，報(bào)警器一響，都以最離。七名學(xué)生興奮地上場了，他們各執(zhí)一根棉線，報(bào)警器一

2、響，都以最快的反應(yīng)拉扯繩子，可一個快的反應(yīng)拉扯繩子，可一個“人人”也沒能脫離火海，原來，七只乒乓球都也沒能脫離火海，原來，七只乒乓球都卡在了瓶口。又開始了第二次實(shí)驗(yàn)？卡在了瓶口。又開始了第二次實(shí)驗(yàn)？ 這幾個學(xué)生面面相覷，只見其中一個小聲跟同伴們商量了幾句，這這幾個學(xué)生面面相覷，只見其中一個小聲跟同伴們商量了幾句，這回大家沒有各顧各地拉繩子，而是回大家沒有各顧各地拉繩子，而是由左到右依次由左到右依次地拉。果然，報(bào)警地拉。果然，報(bào)警器的尾音還沒結(jié)束，七位器的尾音還沒結(jié)束，七位“居民居民”已離開了出口，轉(zhuǎn)移到了安全地帶。已離開了出口，轉(zhuǎn)移到了安全地帶。運(yùn)籌帷幄，決勝千里運(yùn)籌帷幄，決勝千里算法案例算法

3、案例之求最大公約數(shù)之求最大公約數(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 ）解：2 1 8 2 4 用公有質(zhì)因數(shù)2除， 3 9 1 2 用公有質(zhì)因數(shù)3除， 3 4 3和4互質(zhì)不除了。 得：18和24最大公約數(shù)是：236 想一想，如何求8251與6105的最大公約數(shù)？ 例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法短除法開始開始i=m+1輸入：輸入：m,nm MOD i=0且且n MOD i=0?i=

4、i-1輸出：輸出：i結(jié)束結(jié)束YNmn?t=m,m=n,n=tNY窮舉法（也叫枚舉法）步驟： 從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù) 。窮舉法窮舉法定理： 已知m,n,r為正整數(shù)，若m=nq+r（0ra THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND開始開始輸入：輸入：a,b輸出：輸出：a2i結(jié)束結(jié)束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tba?a MOD 2=0且且b MOD 2=0?YNNNYi=0i=i+1輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：小小 結(jié)結(jié)（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計(jì)算次數(shù)的次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計(jì)算次數(shù)的區(qū)別較明顯。區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果