算法案例1 輾轉(zhuǎn)相除法與更相減損術(shù)

1、紐紳中學(xué)紐紳中學(xué)新課導(dǎo)入新課導(dǎo)入方法：方法： 先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一先用兩個(gè)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái)。有的除數(shù)連乘起來(lái)。解：2 1 8 2 4 用公有質(zhì)因數(shù)2除， 3 9 1 2 用公有質(zhì)因數(shù)3除， 3 4 3和4互質(zhì)不除了。 得：18和24最大公約數(shù)是：236 例、求例、求18與與24的最大公約數(shù)：的最大公約數(shù)：短除法短除法求算出求算出8256和和6105的最大公約數(shù)的最大公約數(shù)解析解析: 如果按照以上的方法求最大公約數(shù)，如果按照以上的方法求最大公約數(shù)，會(huì)很麻煩，而其工作量也很多。會(huì)很麻煩，而其

2、工作量也很多。除了用這種方法外還有沒(méi)有其它方法？除了用這種方法外還有沒(méi)有其它方法？輾轉(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ù)，求求8251和和6105的最大公約數(shù)，只要求出的最大公約數(shù)，只要求出6105和和2146的公約的公約數(shù)就可以了。數(shù)就可以了。第二步第二步 對(duì)對(duì)610

3、5和和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例例2 用輾轉(zhuǎn)相除法求用輾轉(zhuǎn)相除法求225和和135的的最大公約數(shù)。最大公約數(shù)。225=1351+90135=901+4590=452+0顯然顯然37是是148和和37的最大的最大公約數(shù)，也就是公約數(shù)，也就是8251和和6105的最大公

4、約數(shù)的最大公約數(shù) 顯然顯然45是是90和和45的最大公約數(shù)，也就是的最大公約數(shù)，也就是225和和135的最大公約數(shù)的最大公約數(shù) 思考思考1：從上面的兩個(gè)例子可以看出計(jì)從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)：重復(fù)S1，直到，直到余數(shù)為余數(shù)為0算法步驟！算法步驟！用程序框圖表示出過(guò)程用程序框圖表示出過(guò)程r=m MOD nm = nn = rr=0?是是否否 輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止停止的步驟，這實(shí)際上是一的步驟，這

5、實(shí)際上是一個(gè)個(gè) 結(jié)構(gòu)結(jié)構(gòu)。？循環(huán)循環(huán)輾轉(zhuǎn)相除法（歐幾里得算法）輾轉(zhuǎn)相除法（歐幾里得算法） 所謂輾轉(zhuǎn)相除法所謂輾轉(zhuǎn)相除法，就是對(duì)于給定的兩，就是對(duì)于給定的兩個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)個(gè)數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時(shí)除盡，則這時(shí)較小的數(shù)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)最大公約數(shù)。輾轉(zhuǎn)相除法算法步驟：輾轉(zhuǎn)相除法算法步驟：第一步：輸入兩個(gè)正整數(shù)第一步：輸入兩個(gè)正整數(shù)m,n(mn)；第二步：計(jì)算第二步：計(jì)算m除以除以n

6、所得的余數(shù)所得的余數(shù)r；第三步：第三步：m=n,n=r；第四步：若第四步：若r0,則則m,n的最大公約數(shù)等于的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步；否則轉(zhuǎn)到第二步；第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)m。程序框圖程序框圖開(kāi)始開(kāi)始輸入輸入m,n r=m MOD n m=nr=0?是是否否 n=r 輸出輸出m結(jié)束結(jié)束程序程序INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND求求8251和和6105的最大公約數(shù)。的最大公約數(shù)。148=37 4+0=378251=61051+21466105=2146 2+1813=（2146

7、，1813）2146=1813 1+333=（1813，333）1813=333 5+148=（333，148）333=148 2+37=（148，37） （8251，6105）解：解：=（6105，2146）九章算術(shù)九章算術(shù)更相減損術(shù)更相減損術(shù) 算理：算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。以少減多，更相減損，求其等也，以等數(shù)約之。第一步：第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否任意給定兩個(gè)正整數(shù)；判斷他們是否都是都是偶數(shù)。若是，則用偶數(shù)。若是，則用2 2約簡(jiǎn)；若不是則執(zhí)行第二步。約簡(jiǎn)；若不是則執(zhí)行第二步

8、。第二步：第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止直到所得的減數(shù)和差相等為止，則這個(gè)數(shù)（等數(shù)），則這個(gè)數(shù)（等數(shù)）或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)最大公約數(shù)。例例1、用用更相減損術(shù)求更相減損術(shù)求98與與63的最大公約數(shù)。的最大公約數(shù)。解析：解析：由于由于63不是偶數(shù)，把不是偶數(shù)，把98和和63以大數(shù)減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。小數(shù)，并輾轉(zhuǎn)相減。按照算法步按照算法步驟來(lái)求解！驟來(lái)求解！= 7所以，

9、所以，98和和63的的最大公約數(shù)最大公約數(shù)等于等于7。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） （98，63）解：解： =（63，35） 更相減損術(shù)更相減損術(shù) 所謂更相減損術(shù)所謂更相減損術(shù)，就是對(duì)于給定的兩，就是對(duì)于給定的兩個(gè)數(shù)，用個(gè)數(shù)，用較大的數(shù)減去較小的數(shù)較大的數(shù)減去較小的數(shù)，然后將，然后將差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大差和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等差數(shù)和較小的數(shù)相等，此時(shí)

10、，此時(shí)相等的兩數(shù)相等的兩數(shù)便便為原來(lái)兩個(gè)數(shù)的為原來(lái)兩個(gè)數(shù)的最大公約數(shù)最大公約數(shù)。更相減損術(shù)算法更相減損術(shù)算法描述：描述：第一步：輸入兩個(gè)正整數(shù)第一步：輸入兩個(gè)正整數(shù)a,b(ab);第二步：若第二步：若a不等于不等于b ,則執(zhí)行第三步；否則轉(zhuǎn)則執(zhí)行第三步；否則轉(zhuǎn) 到第五步；到第五步；第三步：把第三步：把a(bǔ)-b的差賦予的差賦予r;第四步：如果第四步：如果br, 那么把那么把b賦給賦給a,把把r賦給賦給b;否否 則把則把r賦給賦給a，執(zhí)行第二步；，執(zhí)行第二步；第五步：輸出最大公約數(shù)第五步：輸出最大公約數(shù)b。算法步驟！算法步驟！a=r開(kāi)始開(kāi)始輸入輸入a,bab?是是否否 輸出輸出b結(jié)束結(jié)束 b=ra=

11、br=a-brb?否否是是程序框圖程序框圖程序程序INPUT “a,b=”;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND 例例2 2、分別用分別用輾轉(zhuǎn)相除法和更相減損術(shù)輾轉(zhuǎn)相除法和更相減損術(shù)求求168168與與9393的最大公約數(shù)的最大公約數(shù). . 168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36+6+0 0輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：更相減損術(shù)更相減損術(shù): : 168-93=75 168-93=75， 93-75=189

12、3-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-6-3 3= =3 3. .例例3、求求324、243、135這三個(gè)數(shù)這三個(gè)數(shù)的最大公約數(shù)。的最大公約數(shù)。思路分析：思路分析：求三個(gè)數(shù)的最大公約數(shù)可以求三個(gè)數(shù)的最大公約數(shù)可以先求出先求出兩個(gè)數(shù)的最大公約數(shù)兩個(gè)數(shù)的最大公約數(shù)，第三個(gè)數(shù)與前兩個(gè)數(shù)的最第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)的最大公約數(shù)大公約數(shù)的最大公約數(shù)即為所求。即為所求。（1 1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以法以除法為主除法為主，更相減損術(shù)以，更相減損術(shù)以減法為主減法為主，計(jì)算次數(shù)，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別