1.3.1算法案例1輾轉相除法與更相減損術ppt課件

1、1案例案例1 輾轉相除法與更相減損術輾轉相除法與更相減損術2方法方法1：質因數(shù)分解法：質因數(shù)分解法方法方法2：短除法：短除法例如：求例如：求18與與30的最大公約數(shù)的最大公約數(shù)182 3 3302 3 518302 36 ，與最大公約數(shù)為 記作（18，30）=618 302915335（18，30）=2 3=6復習回顧復習回顧求求8251與與6105的最大公約數(shù)的最大公約數(shù)? 輾轉相除法輾轉相除法3輾轉相除法, 又名“歐幾里德算法”（Euclidean algorithm）乃求兩數(shù)之最大公因數(shù)算法。它是已知最古老的算法, 其可追溯至前300年。它首次出現(xiàn)于歐幾里德的幾何原本中，而在中國則可以追

2、溯至東漢出現(xiàn)的九章算術。它并不需要把二數(shù)作質因數(shù)分解 歐幾歐幾里德里德4研探新知研探新知1.1.輾轉相除法輾轉相除法例例1 1 求兩個正數(shù)求兩個正數(shù)82518251和和61056105的最大公約數(shù)。的最大公約數(shù)。解：解：82518251610561051 12146;2146;6105214621813;214618131333333148237;1483740.則則3737為為82518251與與61056105的最大公約數(shù)。的最大公約數(shù)。思考：從上面例子中看出計算的規(guī)律是什么？思考：從上面例子中看出計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)：用大數(shù)除以小數(shù)S2：除數(shù)

3、變成被除數(shù)，余數(shù)變成除數(shù)：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復：重復S1，直到余數(shù)為，直到余數(shù)為05開始開始求求m m除以除以n n的余數(shù)的余數(shù)r r輸出輸出m m結束結束是r r0?0?m=nm=nn=r輸入輸入m,nm,n否程序框圖程序框圖INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0 PRINT mEND程序程序寫出輾轉相除法求兩個數(shù)的最大公約數(shù)的算法、框圖和程序寫出輾轉相除法求兩個數(shù)的最大公約數(shù)的算法、框圖和程序第一步：第一步：輸入兩個正整數(shù)輸入兩個正整數(shù)m,n(mn);第二步：第二步：求出求出mn的余數(shù)的余數(shù)r;第三步：第三步：m=n，n=r

4、；若若r=0，則，則(m,n)=m；否則，返回第二；否則，返回第二步。步。第四步：第四步：算法算法6 思考思考: :如果用當型循環(huán)結構構造算法，則用輾轉相除法求兩個正整數(shù)如果用當型循環(huán)結構構造算法，則用輾轉相除法求兩個正整數(shù)m m，n n的最大公約的最大公約數(shù)的程序框圖和程序分別如何表示？數(shù)的程序框圖和程序分別如何表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結束結束是是n=rINPUT mINPUT m，n nWHILE nWHILE n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND

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

6、大的數(shù)減去較小的數(shù)，接著把較小的數(shù) 與所得的差比較，并以大數(shù)減小數(shù)。與所得的差比較，并以大數(shù)減小數(shù)。 繼續(xù)這個操作，直到所得的數(shù)相等為止，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。2.2.更相減損術更相減損術8解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，并輾轉相減，以大數(shù)減小數(shù)，并輾轉相減，即：即：989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以

7、，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。例例2 2 用更相減損術求用更相減損術求9898與與6363的最大公約數(shù)。的最大公約數(shù)。 分析：先約簡，再求分析：先約簡，再求21與與18的最大公約數(shù)的最大公約數(shù),然后乘以兩次約簡的質因數(shù)然后乘以兩次約簡的質因數(shù)4練習：用更相減損術求兩個正數(shù)練習：用更相減損術求兩個正數(shù)84與與72的最大公約數(shù)。的最大公約數(shù)。（答案：（答案：12）9第一步：給定兩個正整數(shù)第一步：給定兩個正整數(shù),不妨設不妨設mn,第二步：若第二步：若m,n都是偶數(shù)都是偶數(shù),則不斷用則不斷用2約簡約簡,使他們不同時是偶數(shù)使他們不同時是偶數(shù),約簡后的兩個數(shù)仍記約簡后的兩個數(shù)仍

8、記為為m,n第三步：第三步： d=m-n第四步：判斷第四步：判斷”d0”是否成立是否成立,若是若是,則將則將n,d 中較大者記為中較大者記為m,較小的記為較小的記為n,返回第返回第三步三步;否則否則,2k *d(k是約簡整數(shù)的是約簡整數(shù)的2的個數(shù)的個數(shù))為所求的最大公約數(shù)為所求的最大公約數(shù).更相減損術算法更相減損術算法 思考：你能根據(jù)更相減損術設計程序，求兩個正整數(shù)的最大公約數(shù)嗎？10開始開始輸輸m,n(mn)K=0m,n為偶數(shù)為偶數(shù)?m=m/2n=n/2d=m-ndn?dn?是是否否m=nn=dd=m-nm=d是是輸出輸出2k d結束結束否否否否INPUT “m,n=“;m,nK=0WHIL

9、E m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m- nWHILE dn IF dn THEN m=dELSE m=n n=dEND IF d=m-nWEND d=2kdPRINT dEND K=k+1是是11(1)、算法步驟、算法步驟 思考：你能根據(jù)更相減損術設計程序，求兩個正整數(shù)的最大公約數(shù)嗎？第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n(mn).n(mn). 第二步，計算第二步，計算m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表示，小者用表示，小者用

10、n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于m m；否則，返回第二；否則，返回第二步步. . 分析：先約簡，再求分析：先約簡，再求21與與18的最大公約數(shù)的最大公約數(shù),然后乘以兩次約簡的質因數(shù)然后乘以兩次約簡的質因數(shù)4練習：用更相減損術求兩個正數(shù)練習：用更相減損術求兩個正數(shù)84與與72的最大公約數(shù)。的最大公約數(shù)。（答案：（答案：12）12INPUT mINPUT m，n nWHILE mWHILE mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFE

11、ND IFWENDWENDPRINT mPRINT mENDEND開始開始輸入輸入m，nnk？m=n是是輸出輸出m結束結束mn？k=m- -n是是否否n=km=k否否(2)、程序框圖、程序框圖(3)、程序、程序13練習練習 1.1.分別用輾轉相除法和更相減損術求分別用輾轉相除法和更相減損術求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉相除法：輾轉相除法：168=93168=931+751+75，93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相減損術更相減損術: :168-93=75168-93=75， 93-75=1893

12、-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3.14 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

13、=654+104+10，65=1065=106+56+5，10=510=52 2， 所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個數(shù)的最大公約數(shù)是三個數(shù)的最大公約數(shù)是5.5.練習練習15練習練習1 1：利用輾轉相除法求兩數(shù)：利用輾轉相除法求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.16課堂練習課堂練習一一. .用輾轉相除法求下列各組數(shù)的最大公約數(shù)，并編寫程序。用輾轉相除法

14、求下列各組數(shù)的最大公約數(shù)，并編寫程序。 （1 1）225225；135 135 （2 2）9898；196 196 （3 3）7272；168 168 （4 4）153153；119119二二. .思考：用求質因數(shù)的方法可否求上述思考：用求質因數(shù)的方法可否求上述4 4組數(shù)的最大公約數(shù)？組數(shù)的最大公約數(shù)？ 可否利用求質因數(shù)的算法設計出程序框圖及程序？可否利用求質因數(shù)的算法設計出程序框圖及程序？ 若能，在電腦上測試自己的程序；若能，在電腦上測試自己的程序； 若不能說明無法實現(xiàn)的理由。若不能說明無法實現(xiàn)的理由。三三. .思考：利用輾轉相除法是否可以求兩數(shù)的最大公倍數(shù)？思考：利用輾轉相除法是否可以求兩

15、數(shù)的最大公倍數(shù)？ 試設計程序框圖并轉換成程序在試設計程序框圖并轉換成程序在BASICBASIC中實現(xiàn)。中實現(xiàn)。17 1. 1.輾轉相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為輾轉相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，零，則將余數(shù)和較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù)這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù). . 小結作業(yè)小結作業(yè) 2. 2. 更相減損術，就是對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和更相減損術，就是對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時相等的兩數(shù)即較小的數(shù)構成新的一對數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時相等的兩數(shù)即為原來兩個數(shù)的最大公約數(shù)為原來兩個數(shù)的最大公約數(shù). .18比較輾轉相除法與更相減損術的區(qū)別比較輾轉相除法與更相減損術的區(qū)別（1 1）都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術）都是求最大公約數(shù)的方法，計算上