有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題課件

有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題探究一,輾轉(zhuǎn)相除法思考1:在小學(xué)中我們是如何求出兩個正整數(shù)的最大公約數(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）解：21824用公有質(zhì)因數(shù)2除，

3912用公有質(zhì)因數(shù)3除，

343和4互質(zhì)不除了。得：18和24最大公約數(shù)是：2×3＝6

例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法想一想，如何求8251與6105的最大公約數(shù)？

有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

思考2:對于8251與6105這兩個數(shù)，它們的最大公約數(shù)是多少？你是怎樣得到的？

由于它們公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.有沒有其它的方法可以較簡單的找出它們的最大公約數(shù)呢？有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

思考3：注意到8251=6105×1+2146，那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？

我們發(fā)現(xiàn)6105=2146×2+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.

思考4：重復(fù)上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，定義:所謂的輾轉(zhuǎn)相除法,就是對于給定的兩個數(shù),用較大的數(shù)除以較小的數(shù),若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對,繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這是較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實際上是一個循環(huán)結(jié)構(gòu)

思考4：輾轉(zhuǎn)相除直到何時結(jié)束？主要運用的是哪種算法結(jié)構(gòu)？如此循環(huán)，直到得到結(jié)果。①輸入兩個正整數(shù)m和n；②求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中；③更新被除數(shù)和余數(shù)：m=n，n=r。④判斷余數(shù)r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn)向第②步繼續(xù)循環(huán)執(zhí)行。有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題第一步，給定兩個正整數(shù)m，n(m>n).第二步，計算m除以n所得的余數(shù)r.第三步，m=n，n=r.

第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.

思考5:你能把輾轉(zhuǎn)相除法編成一個計算機程序嗎？有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題程序框圖開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

思考6:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題開始輸入m，n求m除以n的余數(shù)rm=nr≠0？否輸出m結(jié)束是n=rINPUTm，nWHILEr<>0r=mMODnm=nn=rWENDPRINTmEND有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)：（1）（225，135）（2）（98，196）（3）（72，168）（4）（153，119）45982417有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題二、更相減損術(shù)

《九章算術(shù)》是中國古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”意思是：

第一步：任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡；若不是，執(zhí)行第二步.

第二步：以較大的數(shù)減去較小的數(shù)，接著把差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個等數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù).有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題例1：用更相減損術(shù)求98與63的最大公約數(shù).98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因為63不是偶數(shù)，所以所以最大公約數(shù)是7.有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

例2分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.輾轉(zhuǎn)相除法：更相減損術(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.有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

例4求325，130，270三個數(shù)的最大公約數(shù).

因為325=130×2+65，130=65×2，所以325與130的最大公約數(shù)是65.

因為270=65×4+10，65=10×6+5，10=5×2，所以65與270最大公約數(shù)是5.

故325，130，270三個數(shù)的最大公約數(shù)是5.有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題

練習(xí):用更相減損術(shù)求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？

第一步，給定兩個正整數(shù)m，n(m>n).

第二步，計算m-n所得的差k.

第三步，比較n與k的大小，其中大者用m表示，小者用n表示.

第四步，若m=n，則m，n的最大公約數(shù)等于m；否則，返回第二步.

討論:該算法的程序框圖如何表示？有關(guān)輾轉(zhuǎn)相除法和更相減損術(shù)的問題開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否

討論:該程序框圖對應(yīng)的程序如何表述？