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

邊城高級中學(xué)

張秀洲1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)1．通過閱讀中國古代中的更相減損術(shù)算法案例，體會中國數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻(xiàn)；2．知道輾轉(zhuǎn)相除法和更相減損術(shù)，能用輾轉(zhuǎn)相除法和更相減損術(shù)求兩個正整數(shù)的最大公約數(shù)．自學(xué)教材P34-P37解決下列問題一、能用輾轉(zhuǎn)相除法和更相減損術(shù)求兩個正整數(shù)的最大公約數(shù).二、《學(xué)海導(dǎo)航》P25-P26“雙層練習(xí)”“范例剖析”三、教材P45第1題例：求下面兩個正整數(shù)的最大公約數(shù)：（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7思考：除了用這種方法外還有沒有其它方法？例：如何算出8251和6105的最大公約數(shù)？一、輾轉(zhuǎn)相除法（歐幾里得算法）1、定義：

所謂輾轉(zhuǎn)相除法，就是對于給定的兩個數(shù)，用較大的數(shù)除以較小的數(shù)。若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡,則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù)。

2、步驟:（以求8251和6105的最大公約數(shù)的過程為例）第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。第二步對6105和2146重復(fù)第一步的做法6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例:用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)思考1：從上面的兩個例子中可以看出計算的規(guī)律是什么？S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0

輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0才停止的步驟，這實(shí)際上是一個循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q

＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否思考：你能把輾轉(zhuǎn)相除法編成一個計算機(jī)程序嗎？(1)、算法步驟：第一步：輸入兩個正整數(shù)m,n(m>n).第二步：計算m除以n所得的余數(shù)r.第三步：m=n,n=r.第四步：若r＝0,則m,n的最大公約數(shù)等于m；否則轉(zhuǎn)到第二步.第五步：輸出最大公約數(shù)m.開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否(2)、程序框圖：開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否INPUTm，nDOr=m

MODnm=nn=rLOOPUNTILr=0PRINTmEND(3)、程序：思考:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)的程序框圖和程序分別如何表示？開始輸入m，n求m除以n的余數(shù)rm=nn>0？否輸出m結(jié)束是n=rINPUTm，nWHILE

n>0r=mMODnm=nn=rWENDPRINTmEND二、更相減損術(shù)可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。（1）、《九章算術(shù)》中的更相減損術(shù)：1、背景介紹：（2）、現(xiàn)代數(shù)學(xué)中的更相減損術(shù)：2、定義：所謂更相減損術(shù)，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等，此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù)。例:用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝2114－7＝7所以，98和63的最大公約數(shù)等于73、方法：(1)、算法步驟第一步：輸入兩個正整數(shù)a,b(a>b);第二步：若a不等于b,則執(zhí)行第三步；否則轉(zhuǎn)到第五步；第三步：把a(bǔ)-b的差賦予r;第四步：如果b>r,那么把b賦給a,把r賦給b;否則把r賦給a,執(zhí)行第二步；第五步：輸出最大公約數(shù)b.思考：你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(shù)的最大公約數(shù)嗎？(2)、程序框圖開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否(3)、程序開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否INPUTm，nWHILE

m<>nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND【例1】分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法：168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.更相減損術(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.因?yàn)?25=130×2+65，130=65×2，所以325與130的最大公約數(shù)是65.

因?yàn)?70=65×4+10，65=10×6+5，10=5×2，所以65與270最大公約數(shù)是5.故325，130，270三個數(shù)的最大公約數(shù)是5.【例2】求325，130，270三個數(shù)的最大公約數(shù).三、教材P45第1題提煉精華總結(jié)收獲，暢談體會※對自己說，你有什么收獲？※對同學(xué)說，你有什么提示？※對老師說，你有什么疑惑？比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次