算法案例(一)

1、案例案例1 輾轉(zhuǎn)相除法與更相減損術(shù)輾轉(zhuǎn)相除法與更相減損術(shù)2 82513 59 15 問(wèn)題問(wèn)題11：在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求出識(shí)，你能求出1818與與3030的最大公約數(shù)嗎？的最大公約數(shù)嗎？創(chuàng)設(shè)情景，揭示課題創(chuàng)設(shè)情景，揭示課題18 30231818和和3030的最大公約的最大公約數(shù)是數(shù)是2 23=6.3=6.方法：方法：先用兩個(gè)數(shù)公有的先用兩個(gè)數(shù)公有的質(zhì)質(zhì)因數(shù)因數(shù)連續(xù)去除連續(xù)去除, ,一直除到所得一直除到所得的商是互質(zhì)數(shù)為止的商是互質(zhì)數(shù)為止, ,然后把所然后把所有的除數(shù)連乘起來(lái)有的除數(shù)連乘起來(lái). .練習(xí)練習(xí)1(1)求求25和和35的最大公

2、約數(shù)的最大公約數(shù),(2)求求49和和63的最大公約數(shù)的最大公約數(shù).25（1）5535749（2）77639所以，所以，25和和35的最大公約數(shù)為的最大公約數(shù)為5所以，所以，49和和63的最大公約數(shù)為的最大公約數(shù)為7創(chuàng)設(shè)情景，揭示課題創(chuàng)設(shè)情景，揭示課題 問(wèn)題問(wèn)題2:2:我們都是利用找公約數(shù)的方法來(lái)求最我們都是利用找公約數(shù)的方法來(lái)求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求求它們的最大公約數(shù)？比如求82518251與與61056105的最的最大公約數(shù)大公

3、約數(shù)? ? 2 82512 61503 82513 61504 82514 61505 82515 61506 82516 6150思路思路1：試值？?。涸囍?？！何時(shí)結(jié)束？有何好的方法？何時(shí)結(jié)束？有何好的方法？案例一：案例一：輾轉(zhuǎn)相除法（輾轉(zhuǎn)相除法（歐幾里得算法歐幾里得算法）觀察用輾轉(zhuǎn)相除法求觀察用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過(guò)程的最大公約數(shù)的過(guò)程 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論：結(jié)論： 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù)，求的公約數(shù)，求

4、8251和和6105的最大公約數(shù)，只要的最大公約數(shù)，只要求出求出6105和和2146的公約數(shù)就可以了的公約數(shù)就可以了.第二步第二步 對(duì)對(duì)6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)的最大公約數(shù). 完整的過(guò)程完整的過(guò)程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例如，用輾轉(zhuǎn)相除法求例如，用輾轉(zhuǎn)相除法求225和和135的最大公約數(shù)的最大公約數(shù)225=1351

5、+90135=901+4590=452顯然顯然37是是148和和37的最大公約的最大公約數(shù)，也就是數(shù)，也就是8251和和6105的最的最大公約數(shù)大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考：從上面的兩個(gè)例子可思考：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？以看出計(jì)算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)：重復(fù)S1，直到余數(shù)為，直到余數(shù)為0利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下： 第一步：用較大

6、的數(shù)第一步：用較大的數(shù)m m除以較小的數(shù)除以較小的數(shù)n n得到一得到一個(gè)商個(gè)商q q0 0和一個(gè)余數(shù)和一個(gè)余數(shù)r r0 0；(m=n(m=nq q0 0+r+r0 0) ) 第二步：若第二步：若r r0 00 0，則，則n n為為m m，n n為最大公約數(shù)；為最大公約數(shù)；若若r r0 000，則用除數(shù)，則用除數(shù)n n除以余數(shù)除以余數(shù)r r0 0得到一個(gè)商得到一個(gè)商q q1 1和一和一個(gè)余數(shù)個(gè)余數(shù)r r1 1；(n=r(n=r0 0q q1 1+r+r1 1) ) 第三步：若第三步：若r r1 10 0，則，則r r0 0為為m m， r0r0為最大公約為最大公約數(shù)；若數(shù)；若r r1 100，則

7、用除數(shù)，則用除數(shù)r r0 0除以余數(shù)除以余數(shù)r r1 1得到一個(gè)商得到一個(gè)商q q2 2和一個(gè)余數(shù)和一個(gè)余數(shù)r r2 2；(r(r0 0=r=r1 1q q2 2+r+r2 2) ) 依次計(jì)算直至依次計(jì)算直至r rn n0 0，此時(shí)所得到的，此時(shí)所得到的r rn-1n-1 , ,即即為所求的最大公約數(shù)為所求的最大公約數(shù). .輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于直到余數(shù)等于0 0停止的步驟，停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu). .8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+14833

8、3=1482+37148=374+0m = n q r用程序框圖表示出右邊的過(guò)程用程序框圖表示出右邊的過(guò)程r=m MOD nm = nn = rr=0?是否否否思考：思考：畫出輾轉(zhuǎn)相除法的程序框圖并設(shè)計(jì)其程序畫出輾轉(zhuǎn)相除法的程序框圖并設(shè)計(jì)其程序開始開始 輸入兩個(gè)正數(shù)輸入兩個(gè)正數(shù)m,nr=m MOD nr=0?輸出輸出n結(jié)束結(jié)束m=nn=r是是INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT nEND否否思考：思考：畫出輾轉(zhuǎn)相除法的程序框圖并設(shè)計(jì)其程序畫出輾轉(zhuǎn)相除法的程序框圖并設(shè)計(jì)其程序開始開始 輸入兩個(gè)正數(shù)輸入兩個(gè)正數(shù)m,nmn?r=m MOD nr0

9、?輸出輸出n結(jié)束結(jié)束m=xm=nn=r否否是是是是x=nn=mINPUT m,nIF mn THEN x=n n=m m=xEND IFr=m MOD nWHILE r0 m=nn=rr=m MOD n WENDPRINT nEND練習(xí)練習(xí)2 2：利用輾轉(zhuǎn)相除法求兩數(shù)：利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.知識(shí)探究（二）知識(shí)探究（二）: :更相減損術(shù)更相減損術(shù) 1:1:設(shè)兩個(gè)正整數(shù)設(shè)兩個(gè)正整數(shù)m mn n，若，若m-n=

10、km-n=k，則，則m m與與n n的最大公約數(shù)和的最大公約數(shù)和n n與與k k的最大公約數(shù)相等的最大公約數(shù)相等. .反復(fù)利用這個(gè)原理，可求得反復(fù)利用這個(gè)原理，可求得9898與與6363的最的最大公約數(shù)為多少？大公約數(shù)為多少？98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，九章算術(shù)九章算術(shù)更相減損術(shù)更相減損術(shù) 算理：算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之以少減多，更相減損

11、，求其等也，以等數(shù)約之.第一步：第一步：任意給頂兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。任意給頂兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用若是，則用2 2約簡(jiǎn)；若不是則執(zhí)行第二步約簡(jiǎn)；若不是則執(zhí)行第二步. .第二步：第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù).2:2:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為法稱為更相減損術(shù)更相

12、減損術(shù). .一般地，用更相減損一般地，用更相減損術(shù)求兩個(gè)正整數(shù)術(shù)求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？步驟如何設(shè)計(jì)？第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn).n(mn). 第二步，計(jì)算第二步，計(jì)算m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于 m m；否則，返回第二

13、步；否則，返回第二步. . 3:3:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否4:4:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND開始開始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=m- -n是是

14、否否n=km=k否否“更相減損術(shù)更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專著在中國(guó)古代數(shù)學(xué)專著九章算術(shù)九章算術(shù)中記述為：中記述為： 可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之以等數(shù)約之. . INPUT “m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m- nWhile dn IF dn then m=d ELSE m=n n=d End if d=m-nWen

15、d d=2k*dPRINT dEnd 理論遷移理論遷移 例例1 1 分別用輾轉(zhuǎn)相除法和更相減損分別用輾轉(zhuǎn)相除法和更相減損術(shù)求術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相減損術(shù)更相減損術(shù):168-93=75:168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3

16、=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3. 例例2 2 求求325325，130130，270270三個(gè)數(shù)的最大三個(gè)數(shù)的最大公約數(shù)公約數(shù). . 因?yàn)橐驗(yàn)?25=130325=1302+652+65，130=65130=652 2，所以所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是6565. . 因?yàn)橐驗(yàn)?70=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5 5. . 故故325325，13

17、0130，270270三個(gè)數(shù)的最大公約三個(gè)數(shù)的最大公約數(shù)是數(shù)是5.5. 1. 1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù)數(shù). . 小結(jié)作業(yè)小結(jié)作業(yè) 2. 2. 更相減損術(shù)，就是對(duì)于給定的兩個(gè)正更相減損術(shù)，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將

18、差整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的減和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時(shí)相等的兩法，直到差和較小的數(shù)相等，此時(shí)相等的兩數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù)數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù). .小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)的比較小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)的比較: : （1 1）都是求最大公約數(shù)的方法，計(jì)算上）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以輾轉(zhuǎn)相除法以除法為主除法為主，更相減損術(shù)以，更相減損術(shù)以減法為減法為主主; ;計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯別較明顯. .（2 2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以體現(xiàn)結(jié)果是以相除余數(shù)為相除余數(shù)為0 0則得到，而更相減損則得到，而更相減損術(shù)則以術(shù)則以減數(shù)與差相等減數(shù)與差相等而得到而得到. .作業(yè)作業(yè)