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

1.3算法案例案例1輾轉(zhuǎn)相除法與更相減損術1.思考：

小學學過的求兩個數(shù)的最大公約數(shù)的方法？先用兩個公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來.例：求下面兩個正整數(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ù)構成新的一對數(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重復第一步的做法

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：重復S1，直到余數(shù)為0．二、更相減損術

可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之．第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步．第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)．（1）《九章算術》中的更相減損術：1.背景介紹：（2）

現(xiàn)代數(shù)學中的更相減損術：2.定義：所謂更相減損術，就是對于給定的兩個數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構成新的一對數(shù)，再用較大的數(shù)減去較小的數(shù)，反復執(zhí)行此步驟直到差數(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＝1414－7＝7所以，98和63的最大公約數(shù)等于73.方法：1.用更相減損術求兩個正數(shù)84與72的最大公約數(shù)．

練習：思路分析：先約簡，再求21與18的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)4．2.求324、243、135這三個數(shù)的最大公約數(shù)．思路分析：求三個數(shù)的最大公約數(shù)可以先求出兩個數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約數(shù)的最大公約數(shù)即為所求．比較輾轉(zhuǎn)相除法與更相減損術的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法