輾轉(zhuǎn)相除法和更相減損術(shù)上課講義

1.3.1輾轉(zhuǎn)相除法和更相減損術(shù)臨高中學(xué)李吉傳2013年5月8日復(fù)習(xí)1.研究一個(gè)實(shí)際問(wèn)題的算法，主要從哪幾方面展開(kāi)？2.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？3.在程序設(shè)計(jì)中基本的算法語(yǔ)句有哪幾種？算法步驟、程序框圖和編寫程序三方面展開(kāi).順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)輸入語(yǔ)句、輸出語(yǔ)句、賦值語(yǔ)句、條件語(yǔ)句、循環(huán)語(yǔ)句一、輾轉(zhuǎn)相除法

思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？

先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái)即為最大公約數(shù).

思考2:對(duì)于8251與6105這兩個(gè)數(shù)，它們的最大公約數(shù)是多少？你是怎樣得到的？

由于它們公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.有沒(méi)有其它的方法可以較簡(jiǎn)單的找出它們的最大公約數(shù)呢？

上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.第一步，給定兩個(gè)正整數(shù)m，n(m>n).第二步，計(jì)算m除以n所得的余數(shù)r.第三步，m=n，n=r.

第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.

思考5:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？程序框圖開(kāi)始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND

思考6:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？開(kāi)始輸入m，n求m除以n的余數(shù)rm=nr≠0？否輸出m結(jié)束是n=rINPUTm，nWHILEr<>0r=mMODnm=nn=rWENDPRINTmEND二、更相減損術(shù)

《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”也可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”意思是：

第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步.

第二步：以較大的數(shù)減去較小的數(shù)，接著把差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù).例1：用更相減損術(shù)求98與63的最大公約數(shù).98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，因?yàn)?3不是偶數(shù)，所以所以最大公約數(shù)是7.

例2分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.輾轉(zhuǎn)相除法：更相減損術(shù):168-93=75，

93-75=18，

75-18=57，

57-18=39，

39-18=21，

21-18=3，

18-3=15，

15-3=12，

12-3=9，

9-3=6，

6-3=3.例3用更相減損術(shù)求80與36的最大公約數(shù).

例4求325，130，270三個(gè)數(shù)的最大公約數(shù).

因?yàn)?25=130×2+65，130=65×2，所以325與130的最大公約數(shù)是65.

因?yàn)?70=65×4+10，65=10×6+5，10=5×2，所以65與270最大公約數(shù)是5.

故325，130，270三個(gè)數(shù)的最大公約數(shù)是5.

練習(xí):用更相減損術(shù)求兩個(gè)正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？

第一步，給定兩個(gè)正整數(shù)m，n(m>n).

第二步，計(jì)算m-n所得的差k.

第三步，比較n與k的大小，其中大者用m表示，小者用n表示.

第四步，若m=n，則m，n的最大公約數(shù)等于m；否則，返回第二步.

討論:該算法的程序框圖如何表示？開(kāi)始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否

討論:該程序框圖對(duì)應(yīng)的程序如何表述？INPUTm，nWHILEm≠nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND開(kāi)始輸入