1、v主講老師 潘學國思考：思考：18與與30的最大公約數(shù)是多少？你是怎樣得到的最大公約數(shù)是多少？你是怎樣得到的？的？ 先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù)來即為最大公約數(shù). . 1823091535318與與30的最大公約數(shù)的最大公約數(shù)是是23=6.短除法短除法快樂回顧快樂回顧 提出問題提出問題“求兩個正整數(shù)的最大求兩個正整數(shù)的最大公約數(shù)公約數(shù)”是數(shù)學中的一是數(shù)學中的一個基礎(chǔ)性問題，它有多個基礎(chǔ)性問題，它有多種解決辦法，以前我們種解決辦法，以前我們通

2、常用短除法。但是，通常用短除法。但是，當兩個數(shù)公有的質(zhì)因數(shù)當兩個數(shù)公有的質(zhì)因數(shù)較大時，使用上述方法較大時，使用上述方法就比較困難。下面我們就比較困難。下面我們介紹兩種古老而有效的介紹兩種古老而有效的方法。方法。思考：思考：對于對于8251與與6105這兩個數(shù)，由于其公有的質(zhì)這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用短除法求最大公約數(shù)就比較困難。因數(shù)較大，利用短除法求最大公約數(shù)就比較困難。那么，有其它解決的辦法嗎那么，有其它解決的辦法嗎?我們注意到我們注意到8251=61051+2146，故，故6105與與2146的公約數(shù)也的公約數(shù)也是是8251與與6105的公約數(shù)，反過來，的公約數(shù)，反過來，825

3、1與與6105的的公約數(shù)也是公約數(shù)也是6105與與2146的公約數(shù)，那么，它們的最的公約數(shù)，那么，它們的最大公約數(shù)有什么關(guān)系呢？大公約數(shù)有什么關(guān)系呢？ 相等相等. .輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法思考：思考：又又6105=21462+1813，同理，同理，6105與與2146的最大公約數(shù)和的最大公約數(shù)和2146與與1813的最大公約數(shù)相等。重的最大公約數(shù)相等。重復上述操作，你能得到復上述操作，你能得到8251與與6105這兩個數(shù)的最大這兩個數(shù)的最大公約數(shù)嗎？公約數(shù)嗎？2146=18131+333，148=374+0.333=1482+37，1813=3335+148，8251=61051+2146，61

4、05=21462+1813，最大公約數(shù)是最大公約數(shù)是37.37.思考：思考：上述方法就是上述方法就是輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法。那么，輾轉(zhuǎn)相除。那么，輾轉(zhuǎn)相除法的具體算法又是怎樣操作的呢？法的具體算法又是怎樣操作的呢？ 對于給定的兩個正整數(shù)，用較大的數(shù)除以較小對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡，則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。這則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。這種算法是由歐幾里得在公元前種算法是由歐

5、幾里得在公元前300300年左右首先提出年左右首先提出的，因而又叫的，因而又叫歐幾里得算法歐幾里得算法。練習：練習： 1 1、用輾轉(zhuǎn)相除法求、用輾轉(zhuǎn)相除法求225225和和135135的最大公約的最大公約數(shù)。數(shù)。225=1351+90135=901+4590=452+0225225和和135135的最大公約數(shù)是的最大公約數(shù)是4545. . 快樂練習快樂練習練習練習2 2：利用輾轉(zhuǎn)相除法求兩數(shù)利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大的最大公約數(shù)公約數(shù). . 20723=40815+318;4081=31812+265;318=2651+53;265=535+0.4081

6、4081和和2072320723的最大公約數(shù)是的最大公約數(shù)是5353. . 其中包含重復操作的步驟，其中包含重復操作的步驟，實際上是一個循環(huán)結(jié)構(gòu)實際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = nqr用程序框圖表示出右邊的過程：用程序框圖表示出右邊的過程：r=m MOD nm = nn = rr=0?是是否否觀察：觀察：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是那種邏輯結(jié)構(gòu)？輾轉(zhuǎn)相除法中的關(guān)鍵步驟是那種邏輯結(jié)構(gòu)？思考：思考：求兩個正整數(shù)求兩個正整數(shù)m，n的最大公約數(shù)，可以用循

7、環(huán)的最大公約數(shù)，可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？ 算法設(shè)計：算法設(shè)計：第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn).第二步，計算第二步，計算m m除以除以n n所得的余數(shù)所得的余數(shù)r r. 第三步，第三步，m=nm=n，n=n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于m m；否則，返回第二步否則，返回第二步. . 思考：思考：上述算法的程序上述算法的程序框圖如何表示？框圖如何表示？開始開始輸入輸入m，n求求m m除以除以n n的余數(shù)的余數(shù)r rm=nn=rr=0？是

8、是輸出輸出m m結(jié)束結(jié)束否否思考：思考：該程序框圖對應的程序如該程序框圖對應的程序如何表述？何表述？INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否思考：思考：你用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個正整數(shù)的你用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個正整數(shù)的最大公約數(shù)嗎？試寫出算法步驟、程序框圖和程序。最大公約數(shù)嗎？試寫出算法步驟、程序框圖和程序。算法設(shè)計：算法設(shè)計：第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn).第二步，若第二步，若n

9、0n0，計算，計算m m除以除以n n所得的余數(shù)所得的余數(shù)r r. m=nm=n，n=n=r. 否則否則,m,m，n n的最大公約數(shù)等于的最大公約數(shù)等于m m。開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT m，nWHILE n0r=m MOD nm=nn=rWENDPRINT mEND “可半者半之，不可半者，副置分母、子之數(shù)，以少減多，可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也。以等數(shù)約之。更相減損，求其等也。以等數(shù)約之。” 第一步，任意給定兩個正整數(shù)，判斷他們是否都是偶數(shù)。第一步，任意給定兩個正整數(shù)，判

10、斷他們是否都是偶數(shù)。若是，則用若是，則用2 2約簡；若不是，執(zhí)行第二步。約簡；若不是，執(zhí)行第二步。 第二步，以較大的數(shù)減較小的數(shù)，接著把所得的差與較第二步，以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。乘積就是所求的最大公約數(shù)。 九章算術(shù)九章算術(shù)是中國古代的數(shù)學專著，其中的是中國古代的數(shù)學專著，其中的“更相減損術(shù)更相減損術(shù)”也可以用來求兩個數(shù)的最大公約數(shù)，即也可以用來求兩個數(shù)的

11、最大公約數(shù)，即 翻譯為現(xiàn)代語言如下：翻譯為現(xiàn)代語言如下： 更相減損術(shù)更相減損術(shù)例例1：用更相減損術(shù)求用更相減損術(shù)求98與與63的最大公約數(shù)。的最大公約數(shù)。98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，最大公約數(shù)是最大公約數(shù)是7.思考：思考：把更相減損術(shù)與輾轉(zhuǎn)相除法比較，你有什么發(fā)把更相減損術(shù)與輾轉(zhuǎn)相除法比較，你有什么發(fā)現(xiàn)？你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(shù)的現(xiàn)？你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(shù)的最大公約數(shù)嗎？最大公約數(shù)嗎？第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn). 第二步，若第二步，若m m，n

12、 n都是偶數(shù)，則不斷用都是偶數(shù)，則不斷用2 2約簡，使它約簡，使它們不同時為偶數(shù)，約簡后的兩個數(shù)仍記為們不同時為偶數(shù)，約簡后的兩個數(shù)仍記為m m，n.n. 第三步，第三步，d = m-n.d = m-n. 第四步，判斷第四步，判斷“dndn”是否成立。若是，則將是否成立。若是，則將n n，d d中較大者記為中較大者記為m m，較小者記為，較小者記為n n，返回第三步，否，返回第三步，否則，則，2k2k* *d d（k k為約簡整數(shù)的為約簡整數(shù)的2 2的個數(shù)）為所求的最的個數(shù)）為所求的最大公約數(shù)。大公約數(shù)。算法設(shè)計：算法設(shè)計：INPUT “m，n=”；m，nk=0WHILE m MOD 2=0

13、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-nWEND d=2k*dPRINT dEND 程序：程序： 例例2 2：分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=931+75， 93=751+18， 75=184+3， 18=36+0.典例剖析典例剖析 例例2 2：分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168168與與9393的最大公約數(shù)

14、的最大公約數(shù). . 典例剖析典例剖析更相減損術(shù)更相減損術(shù): : 168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3. 例例3 3：求求325325，130130，270270三個數(shù)的最大公約數(shù)三個數(shù)的最大公約數(shù). . 因為因為325=130325=1302+652+65，130=65130=652 2，所以，所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因為因為270=65270=654+104+10，65=1065=10

15、6+56+5，10=510=52 2，所，所以以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個數(shù)的最大公約數(shù)是三個數(shù)的最大公約數(shù)是5.5.課時小結(jié)課時小結(jié): : 1、輾轉(zhuǎn)相除法，就是對于給定的兩個正整數(shù)，、輾轉(zhuǎn)相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù)即為原來兩個數(shù)的最大公約數(shù). 2、更相減損術(shù)，就是對于給定的兩個正整數(shù)，、更相減損術(shù)，就是對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的減法，直到差和較構(gòu)成新的一對數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時相等的兩數(shù)即為原來兩個數(shù)的小的數(shù)相等，此時相等的兩數(shù)即為原來兩個數(shù)的最大公約數(shù)最大公約數(shù).課時小結(jié)課時小結(jié): :比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1 1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為