1.3.1算法案例1輾轉(zhuǎn)相除法與更相減損術(shù)ppt課件

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

2、溯至東漢出現(xiàn)的九章算術(shù)。它并不需要把二數(shù)作質(zhì)因數(shù)分解 歐幾歐幾里德里德4研探新知研探新知1.1.輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法例例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：重復(fù)：重復(fù)S1，直到余數(shù)為，直到余數(shù)為05開始開始求求m m除以除以n n的余數(shù)的余數(shù)r r輸出輸出m m結(jié)束結(jié)束是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程序程序?qū)懗鲚氜D(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)的算法、框圖和程序?qū)懗鲚氜D(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)的算法、框圖和程序第一步：第一步：輸入兩個正整數(shù)輸入兩個正整數(shù)m,n(mn);第二步：第二步：求出求出mn的余數(shù)的余數(shù)r;第三步：第三步：m=n，n=r

4、；若若r=0，則，則(m,n)=m；否則，返回第二；否則，返回第二步。步。第四步：第四步：算法算法6 思考思考: :如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的最大公約的最大公約數(shù)的程序框圖和程序分別如何表示？數(shù)的程序框圖和程序分別如何表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn0？否否輸出輸出m結(jié)束結(jié)束是是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ù)的步驟如下： 可半者半之，不可半者，副置分母可半者半之，不可半者，副置分母子之?dāng)?shù)，子之?dāng)?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.更相減損術(shù)更相減損術(shù)8解：由于解：由于6363不是偶數(shù)，把不是偶數(shù)，把9898和和6363以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：即：989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以

7、，9898與與6363的最大公約數(shù)是的最大公約數(shù)是7 7。例例2 2 用更相減損術(shù)求用更相減損術(shù)求9898與與6363的最大公約數(shù)。的最大公約數(shù)。 分析：先約簡，再求分析：先約簡，再求21與與18的最大公約數(shù)的最大公約數(shù),然后乘以兩次約簡的質(zhì)因數(shù)然后乘以兩次約簡的質(zhì)因數(shù)4練習(xí)：用更相減損術(shù)求兩個正數(shù)練習(xí)：用更相減損術(shù)求兩個正數(shù)84與與72的最大公約數(shù)。的最大公約數(shù)。（答案：（答案：12）9第一步：給定兩個正整數(shù)第一步：給定兩個正整數(shù),不妨設(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ù).更相減損術(shù)算法更相減損術(shù)算法 思考：你能根據(jù)更相減損術(shù)設(shè)計程序，求兩個正整數(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結(jié)束結(jié)束否否否否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ù)嗎？第一步，給定兩個正整數(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ù),然后乘以兩次約簡的質(zhì)因數(shù)然后乘以兩次約簡的質(zhì)因數(shù)4練習(xí)：用更相減損術(shù)求兩個正數(shù)練習(xí)：用更相減損術(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結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否(2)、程序框圖、程序框圖(3)、程序、程序13練習(xí)練習(xí) 1.1.分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=93168=931+751+75，93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.更相減損術(shù)更相減損術(shù): :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ù). . 解：因?yàn)榻猓阂驗(yàn)?25=130325=1302+652+65，130=65130=652 2， 所以所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因?yàn)橐驗(yàn)?70=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.練習(xí)練習(xí)15練習(xí)練習(xí)1 1：利用輾轉(zhuǎn)相除法求兩數(shù)：利用輾轉(zhuǎn)相除法求兩數(shù)40814081與與2072320723的最大公約數(shù)的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.16課堂練習(xí)課堂練習(xí)一一. .用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)，并編寫程序。用輾轉(zhuǎn)相除法

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

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