輾轉(zhuǎn)相除法教學教材

1、第一頁，共19頁。知識探究（一）知識探究（一）:輾轉(zhuǎn)輾轉(zhuǎn)(zhnzhun)相除法相除法思考思考(sko)1:18(sko)1:18與與3030的最大公約數(shù)是多的最大公約數(shù)是多少？你是怎樣得到的？少？你是怎樣得到的？ 先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除(q ch)(q ch)，一直除到所得的商是互質(zhì)，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù)為最大公約數(shù). . 第二頁，共19頁。思考思考2:2:對于對于82518251與與61056105這兩個數(shù)，由于其公這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約

2、有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難數(shù)就比較困難. .注意注意(zh y)(zh y)到到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩這兩個數(shù)的公約數(shù)和個數(shù)的公約數(shù)和61056105與與21462146的公約數(shù)有什么的公約數(shù)有什么關(guān)系？關(guān)系？ 第三頁，共19頁。思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公約的公約數(shù)相等數(shù)相等(xingdng).(xingdng).重復上

3、述操作，你能重復上述操作，你能得到得到82518251與與61056105這兩個數(shù)的最大公約數(shù)嗎？這兩個數(shù)的最大公約數(shù)嗎？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，第四頁，共19頁。 輾轉(zhuǎn)相除法是一個反復輾轉(zhuǎn)相除法是一個反復(fnf)(fnf)執(zhí)行直到余數(shù)等于執(zhí)行直到余數(shù)等于0 0停止的步驟，這實停止的步驟，

4、這實際上是一個循環(huán)結(jié)構(gòu)。際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示用程序框圖表示(biosh)出右邊的過出右邊的過程程r=m MOD nm = nn = rr=0?是否第五頁，共19頁。思考思考5:5:上述求兩個正整數(shù)的最大公約數(shù)的方上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法法稱為輾轉(zhuǎn)相除法或歐幾里得算法(sun (sun f).f).一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n

5、 n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法造算法(sun f)(sun f)？其算法？其算法(sun f)(sun f)步驟如步驟如何設計？何設計？ 第一步，給定第一步，給定( (i dni dn) )兩個正整數(shù)兩個正整數(shù)m m，n(mn).n(mn).第二步，計算第二步，計算(j sun)m(j sun)m除以除以n n所得的所得的余數(shù)余數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等的最大公約數(shù)等 于于m m；否則，返回第二步；否則，返回第二步. . 第六頁，共19頁。思

6、考思考6:6:該算法該算法(sun f)(sun f)的程序框圖如何的程序框圖如何表示？表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否第七頁，共19頁。思考思考7:7:該程序框圖對應該程序框圖對應(duyng)(duyng)的程序的程序如何表述？如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束

7、結(jié)束否否第八頁，共19頁。思考思考8:8:如果用當型循環(huán)結(jié)構(gòu)構(gòu)造如果用當型循環(huán)結(jié)構(gòu)構(gòu)造(guzo)(guzo)算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的最大公約數(shù)的程序框圖和程序分別如何的最大公約數(shù)的程序框圖和程序分別如何表示？表示？第九頁，共19頁。開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nr0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT mINPUT m，n nWHILE rWHILE r0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND第十頁，共19頁。練習練習(

8、linx)1(linx)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.第十一頁，共19頁。更相減損更相減損(jin sn)術(shù)術(shù)“更相減損術(shù)更相減損術(shù)”（也是求兩個（也是求兩個(lin )正整數(shù)的最大公約數(shù)的算法）正整數(shù)的最大公約數(shù)的算法）步驟：步驟：第一步：任意給定兩個第一步：任意給定兩個(lin )(lin )正整數(shù)；判斷他們是否都是偶數(shù)。正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用若是，則用2 2約簡；

9、若不是則執(zhí)行第二步。約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)或這個數(shù)與約簡的得的減數(shù)和差相等為止，則這個等數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。數(shù)的乘積就是所求的最大公約數(shù)。第十二頁，共19頁。例、用更相減損例、用更相減損(jin sn)(jin sn)術(shù)求術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù)（自己按照步驟求解）（自己按照步驟求解）解：由于解：由于6363不是偶數(shù)不

10、是偶數(shù)(u sh)(u sh)，把，把9898和和6363以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。所以所以(suy)(suy)，9898和和6363的最大公約數(shù)等于的最大公約數(shù)等于7 7。98-63=35 63-35=2835-28=728-7=2121-7=1414-7=7第十三頁，共19頁。更相減損是一個反復執(zhí)行直到減數(shù)等于差時停止(tngzh)的步驟，這實際也是一個循環(huán)結(jié)構(gòu) 思考：更相減損直到何時(h sh)結(jié)束？運用的是哪種算法結(jié)構(gòu)？第十四頁，共19頁。程序(chngx)：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a

11、/2 b=b/2 i=i+1 WEND DOIF ba THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND開始開始輸入：輸入：a,b輸出：輸出：a2i結(jié)束結(jié)束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tba?a MOD 2=0且且b MOD 2=0?YNNNYi=0i=i+1第十五頁，共19頁。 例2 分別用輾轉(zhuǎn)相除法(chf)和更相減損術(shù)求168與93的最大公約數(shù). 輾轉(zhuǎn)輾轉(zhuǎn)(zhnzhun)(zhnzhun)相除法：相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=187

12、5=184+34+3， 18=318=36.6.第十六頁，共19頁。更相減損更相減損(jin sn)(jin sn)術(shù)術(shù):168-93=75:168-93=75， 93-75=1893-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.第十七頁，共19頁。例例3 3：用輾轉(zhuǎn)：用輾轉(zhuǎn)(zhnzhun)(zhnzhun)相除法和更相減損相除法和更相減損術(shù)求術(shù)求210210與與714714的最大公約數(shù)的最大公約數(shù). .第十八頁，共19頁。比較輾轉(zhuǎn)相除法與更相減損比較輾轉(zhuǎn)相除法與更相減損(jin sn)(jin sn)術(shù)的區(qū)別術(shù)的區(qū)別（1 1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損法以除法為主，更相減損(jin sn)(jin sn)術(shù)以減法為主，術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當計算次數(shù)上輾