輾轉(zhuǎn)相除與更相減損術(shù)

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

2、方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求的最大公約數(shù)？比如求82518251與與61056105的最大公約數(shù)的最大公約數(shù)? ? 研探新知研探新知1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :例例1 1 求兩個正數(shù)求兩個正數(shù)82518251和和61056105的最大公約數(shù)。的最大公約數(shù)。分析：分析：82518251與與61056105兩數(shù)都比較大，而且沒兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根有明顯的公約數(shù)，如能把它們都變小一點，

3、根據(jù)已有的知識即可求出最大公約數(shù)據(jù)已有的知識即可求出最大公約數(shù). .解：解：82518251610561051 121462146顯然顯然82518251與與61056105的最大公約數(shù)也必是的最大公約數(shù)也必是21462146的約數(shù)，同樣的約數(shù)，同樣61056105與與21462146的公約數(shù)也必是的公約數(shù)也必是82518251的約數(shù)，所以的約數(shù)，所以82518251與與61056105的最大公約數(shù)也是的最大公約數(shù)也是61056105與與21462146的最大公約數(shù)。的最大公約數(shù)。思考思考2:2:對于對于82518251與與61056105這兩個數(shù)，由于這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上

4、述方法求其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難最大公約數(shù)就比較困難. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個數(shù)的公約數(shù)和這兩個數(shù)的公約數(shù)和61056105與與21462146的公約的公約數(shù)有什么關(guān)系？數(shù)有什么關(guān)系？ 思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公的公約數(shù)相等約數(shù)相等. .重復(fù)上述操作，你能得到重復(fù)上述操作，你能得到82518251與

5、與61056105這兩個數(shù)的最大公約數(shù)嗎？這兩個數(shù)的最大公約數(shù)嗎？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，研探新知研探新知1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: :例例1 1 求兩個正數(shù)求兩個正數(shù)82518251和和61056105的最大公約數(shù)的最大公約數(shù)。則則3737為為82518251與與61056105的最大

6、公約數(shù)。的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相輾轉(zhuǎn)相除法。也叫歐幾里德算法除法。也叫歐幾里德算法，它是由歐幾里德在，它是由歐幾里德在公元前公元前300300年左右首先提出的。年左右首先提出的。 21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟

7、如下：利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下： 第一步：用較大的數(shù)第一步：用較大的數(shù)m m除以較小的數(shù)除以較小的數(shù)n n得到得到一個商一個商q q0 0和一個余數(shù)和一個余數(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得到一個得到一個商商q q1 1和一個余數(shù)和一個余數(shù)r r1 1；(n=r(n=r0 0q q1 1+r+r1 1) ) 第三步：若第三步：若r r1 10 0，則，則r r0 0為為m m，n

8、 n的最大公約的最大公約數(shù)；若數(shù)；若r r1 100，則用除數(shù)，則用除數(shù)r r0 0除以余數(shù)除以余數(shù)r r1 1得到一個得到一個商商q q2 2和一個余數(shù)和一個余數(shù)r r2 2；(r(r0 0=r=r1 1q q2 2+r+r2 2) ) 依次計算直至依次計算直至r rn n0 0，此時所得到的，此時所得到的r rn-1n-1 即為所求的最大公約數(shù)。即為所求的最大公約數(shù)。思考思考4:4:上述求兩個正整數(shù)的最大公約數(shù)上述求兩個正整數(shù)的最大公約數(shù)的方法稱為的方法稱為輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法或或歐幾里得算法歐幾里得算法. .一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的

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

10、0？是是輸出輸出m結(jié)束結(jié)束否否思考思考6:6:該程序框圖對應(yīng)的程序如何表述？該程序框圖對應(yīng)的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否思考思考7:7:如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，如果用當型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)則用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的最的最大公約數(shù)的程序框圖和程序分別如何表大公約數(shù)的程序框圖和程

11、序分別如何表示？示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND練習(xí)練習(xí)1 1：利用輾轉(zhuǎn)相除法求兩數(shù)：利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.2.2.更相減損術(shù)更相減損術(shù): :我國早期也有解決

12、求最大公約數(shù)問題的算我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。法，就是更相減損術(shù)。更相減損術(shù)更相減損術(shù)求最大公約數(shù)的步驟如下：求最大公約數(shù)的步驟如下：可可半者半之，不可半者，副置分母半者半之，不可半者，副置分母子之數(shù)，以少子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：翻譯出來為：第一步：第一步：任意給出兩個正數(shù)；任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用判斷它們是否都是偶數(shù)。若是，用2 2約簡；若不是，約簡；若不是，執(zhí)行第二步。執(zhí)行第二步。第二步：第二步：以以較大的數(shù)減去較小的數(shù)較大的數(shù)減去較小的數(shù)，接著把，接著把較小的

13、數(shù)與所得的差比較，較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)并以大數(shù)減小數(shù)。繼。繼續(xù)這個操作，續(xù)這個操作，直到所得的數(shù)相等為止直到所得的數(shù)相等為止，則這個數(shù)，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。（等數(shù)）就是所求的最大公約數(shù)。例例2 2 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). .解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，減小數(shù)，并輾轉(zhuǎn)相減， 即：即：986335; 633528; 35287; 28721; 21714; 1477.所以，所以，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。練習(xí)練

14、習(xí)2 2：用更相減損術(shù)求兩個正數(shù)：用更相減損術(shù)求兩個正數(shù)8484與與7272的最大的最大公約數(shù)。公約數(shù)。 (12)(12) 例例2 2 求求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=106+56+5，10=510=52 2，所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，27

15、0270三個數(shù)的最大公約三個數(shù)的最大公約數(shù)是數(shù)是5.5. 練習(xí)：求練習(xí)：求325,130,270三個數(shù)的最三個數(shù)的最大公約數(shù)大公約數(shù)小結(jié)：見大聚焦小結(jié)：見大聚焦閱讀閱讀P12倒數(shù)第二段倒數(shù)第二段P15思考，并完成下表：思考，并完成下表：語句語句一般格式一般格式主要功能主要功能說明說明輸入語句輸入語句輸出語句輸出語句賦值語句賦值語句（1）;變量變量PRINT “提示內(nèi)容提示內(nèi)容”;表達式表達式變量表達式變量表達式可對程序中可對程序中的變量賦值的變量賦值可輸出表達式可輸出表達式的值，計算的值，計算可對程序中的變可對程序中的變量賦值，計算量賦值，計算（1）提示內(nèi)容和它后面）提示內(nèi)容和它后面 的的“；”可以省略可以省略（2）一個語