輾轉相除法和更相減損術上課講義

1.3.1輾轉相除法和更相減損術臨高中學李吉傳2013年5月8日復習1.研究一個實際問題的算法，主要從哪幾方面展開？2.在程序框圖中算法的基本邏輯結構有哪幾種？3.在程序設計中基本的算法語句有哪幾種？算法步驟、程序框圖和編寫程序三方面展開.順序結構、條件結構、循環(huán)結構輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句一、輾轉相除法

思考1:18與30的最大公約數是多少？你是怎樣得到的？

先用兩個數公有的質因數連續(xù)去除，一直除到所得的商是互質數為止，然后把所有的除數連乘起來即為最大公約數.

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

由于它們公有的質因數較大，利用上述方法求最大公約數就比較困難.有沒有其它的方法可以較簡單的找出它們的最大公約數呢？

上述求兩個正整數的最大公約數的方法稱為輾轉相除法或歐幾里得算法.第一步，給定兩個正整數m，n(m>n).第二步，計算m除以n所得的余數r.第三步，m=n，n=r.

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

思考5:你能把輾轉相除法編成一個計算機程序嗎？程序框圖開始輸入m，n求m除以n的余數rm=nn=rr=0？是輸出m結束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND

思考6:如果用當型循環(huán)結構構造算法，則用輾轉相除法求兩個正整數m、n的最大公約數的程序框圖和程序分別如何表示？開始輸入m，n求m除以n的余數rm=nr≠0？否輸出m結束是n=rINPUTm，nWHILEr<>0r=mMODnm=nn=rWENDPRINTmEND二、更相減損術

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

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

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

例2分別用輾轉相除法和更相減損術求168與93的最大公約數.168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.輾轉相除法：更相減損術: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用更相減損術求80與36的最大公約數.

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

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

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

故325，130，270三個數的最大公約數是5.

練習:用更相減損術求兩個正整數m，n的最大公約數，可以用什么邏輯結構來構造算法？其算法步驟如何設計？

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

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

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

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

討論:該算法的程序框圖如何表示？開始輸入m，nn>k？m=n是輸出m結束m≠n？k=m-n是否n=km=k否

討論:該程序框圖對應的程序如何表述？INPUTm，nWHILEm≠nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND開始輸入