1.3(1)輾轉(zhuǎn)相除法課件

1、2021/6/1612021/6/162學(xué)習(xí)目標(biāo)1.理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的原理。2.能寫出兩種求最大公約數(shù)方法的算法步驟與程序框圖。3.會求出兩個數(shù)的最大公約數(shù)，進(jìn)一步體會算法的基本思想以及算法在解決問題的過程中所體現(xiàn)的特點(diǎn)。2021/6/163知識探究（一）知識探究（一）: :輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法思考思考1:1:1818與與3030的最大公約數(shù)是多少？你的最大公約數(shù)是多少？你是怎樣得到的？是怎樣得到的？ 先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公后把所有的除

2、數(shù)連乘起來即為最大公約數(shù)約數(shù). . 2021/6/164思考思考2:2:對于對于82518251與與61056105這兩個數(shù)，由于這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難最大公約數(shù)就比較困難. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個數(shù)的公約數(shù)和這兩個數(shù)的公約數(shù)和61056105與與21462146的公約的公約數(shù)有什么關(guān)系？數(shù)有什么關(guān)系？ 2021/6/165思考思考3:3:又又6105=21466105=21462+18132+1813，同理，

3、同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公的公約數(shù)相等約數(shù)相等. .重復(fù)上述操作，你能得到重復(fù)上述操作，你能得到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，2021/6

4、/166以上的方法就是輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法1.適合兩個數(shù)適合兩個數(shù) 公有的質(zhì)因數(shù)較大時。公有的質(zhì)因數(shù)較大時。2.算到什么情況下，就停止計(jì)算了？算到什么情況下，就停止計(jì)算了？ 余數(shù)為零時，停止計(jì)算。余數(shù)為零時，停止計(jì)算。3.最大公約數(shù)是最大公約數(shù)是 ？除數(shù)（？除數(shù)（較小的數(shù)較小的數(shù)）2021/6/167理論遷移理論遷移(1) 1515，600(2) 117，182例例1 用輾轉(zhuǎn)相除法求下列各數(shù)的最大用輾轉(zhuǎn)相除法求下列各數(shù)的最大公約數(shù)公約數(shù).2021/6/168理論遷移理論遷移(1) 1515，600(2) 117，182例例1 用輾轉(zhuǎn)相除法求下列各數(shù)的最大用輾轉(zhuǎn)相除法求下列各數(shù)的最大公約數(shù)公約數(shù)

5、.答案答案：(1)15 (2)132021/6/169 由上述例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步由上述例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步驟，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法驟，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否2021/6/1610思考思考5:5:上述求兩個正整數(shù)的最大公約數(shù)上述求兩個正整數(shù)的最大公約數(shù)的方法稱為

6、的方法稱為輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法或或歐幾里得算法歐幾里得算法. .一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的最大公約數(shù)，算法步驟如下：的最大公約數(shù)，算法步驟如下： 第一步，給定兩個正整數(shù)第一步，給定兩個正整數(shù)m m，n (mn (mn).n).第二步，計(jì)算第二步，計(jì)算m 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；否則，返回第二步；否則，返回第二步. . 2021/6/1611思考思考6:6:該算法的程序框圖如何表

7、示？該算法的程序框圖如何表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否2021/6/1612思考思考7:7:該程序框圖對應(yīng)的程序如何表述？該程序框圖對應(yīng)的程序如何表述？INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否2021/6/1613思考思考8:8:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，如果用當(dāng)型

8、循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)則用輾轉(zhuǎn)相除法求兩個正整數(shù)m m，n n的最的最大公約數(shù)的程序框圖和程序分別如何表大公約數(shù)的程序框圖和程序分別如何表示？示？2021/6/1614開始開始輸入輸入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 mENDEND2021/6/1615練習(xí)練習(xí)1 1：利用輾轉(zhuǎn)除法求兩數(shù)：利用輾轉(zhuǎn)除法求兩數(shù)40814081與與2072320723的最大公約數(shù)

9、的最大公約數(shù). . (53)(53)20723=40815+318;4081=31812+265;318=2651+53;265=535+0.2021/6/1616更相減損術(shù)更相減損術(shù)“更相減損術(shù)更相減損術(shù)”（也是求兩個正整數(shù)的最大公約數(shù)的算（也是求兩個正整數(shù)的最大公約數(shù)的算法）法）步驟：步驟：第一步：任意給定兩個正整數(shù)；判斷他們是否都第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。是偶數(shù)。若是，則用若是，則用2約簡；若不是則執(zhí)行第二步。約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個差與

10、較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的操作，直到所得的減數(shù)和差相等減數(shù)和差相等為止，則這個等為止，則這個等數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公數(shù)或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù)。約數(shù)。2021/6/1617例例1 1、用更相減損術(shù)求、用更相減損術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)（自己按照步驟求解）（自己按照步驟求解）解由于解由于63不是偶數(shù)，把不是偶數(shù)，把98和和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減。所以，所以，98和和63的最大公約數(shù)等于的最大公約數(shù)等于7。98-63=35 63-35=2835-28=728-7=2121-7=1414

11、-7=72021/6/1618更相減損是一個反復(fù)執(zhí)行直到更相減損是一個反復(fù)執(zhí)行直到減數(shù)等于差減數(shù)等于差時時停止的步驟，這實(shí)際也是一個循環(huán)結(jié)構(gòu)停止的步驟，這實(shí)際也是一個循環(huán)結(jié)構(gòu) 。思考九：更相減損直到何時結(jié)束？運(yùn)用的是思考九：更相減損直到何時結(jié)束？運(yùn)用的是哪種算法結(jié)構(gòu)？哪種算法結(jié)構(gòu)？輾轉(zhuǎn)相除法與更相減損術(shù)輾轉(zhuǎn)相除法與更相減損術(shù) 進(jìn)行到哪一步停止運(yùn)算？進(jìn)行到哪一步停止運(yùn)算？2021/6/16192021/6/1620 例例2 2 分別用輾轉(zhuǎn)相除法和更相減損分別用輾轉(zhuǎn)相除法和更相減損術(shù)求術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=93168=931+7

12、51+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.2021/6/1621更相減損術(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.2021/6/1622例例3 . 用兩種方法求用兩種方法求612與與468的最大公的

13、最大公約數(shù)？約數(shù)？ 方法一：輾轉(zhuǎn)相除法方法一：輾轉(zhuǎn)相除法 612=4681+144， 468=1441+36， 144=364+0.2021/6/1623方法二：更相減損術(shù)方法二：更相減損術(shù)612與與468都是偶數(shù)，所以兩次用都是偶數(shù)，所以兩次用2約分約分化簡化簡612=1534 468=1174153-117=36 117-36=81 81-36=45 45-36=9 36-9=27 27-9=18 18-9=99是153與117的最大公約數(shù)。94=36是是612與與468的最大公約數(shù)。的最大公約數(shù)。2021/6/1624比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1

14、1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個數(shù)字上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計(jì)算次數(shù)的區(qū)別較明顯。大小區(qū)別較大時計(jì)算次數(shù)的區(qū)別較明顯。（2 2）通過輾轉(zhuǎn)相除和更相減損術(shù)來求兩個數(shù)的最）通過輾轉(zhuǎn)相除和更相減損術(shù)來求兩個數(shù)的最大公約數(shù)的案例分析，感受其中所蘊(yùn)含的算法基本大公約數(shù)的案例分析，感受其中所蘊(yùn)含的算法基本思想，重點(diǎn)培養(yǎng)學(xué)生利用算法思想的邏輯思維能力。思想，重點(diǎn)培養(yǎng)學(xué)生利用算法思想的邏輯思維能力。2021/6/1625 作業(yè)：寫出更相減損術(shù)的算法。作業(yè)：寫出更相減損術(shù)的算法。2021/6/1626程序：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DOIF ba TH