算法案例講義

算法案例(第一課時(shí))輾轉(zhuǎn)相除法（歐幾里得算法）與更相減損術(shù)安慶一中羅志強(qiáng)1、求兩個(gè)正整數(shù)的最大公約數(shù)（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)2、求8251和6105的最大公約數(shù)25（1）5535749（2）77639所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

8251=6105×1+2146結(jié)論：8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。第二步對6105和2146重復(fù)第一步的做法

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。為什么呢？思考：從上述的過程你體會(huì)到了什么？完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù)，也就是225和135的最大公約數(shù)思考1：從上面的兩個(gè)例子可以看出計(jì)算的規(guī)律是什么？

S1：給定兩個(gè)正整數(shù)m,nS2：用大數(shù)除以小數(shù)，計(jì)算m除以n所得的余數(shù)；S3：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)，即m=n,n=rS4：重復(fù)S2,直到余數(shù)為0，即若r=0，則m,n的最大公約數(shù)為m，否則返回S2

輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q＋r用程序框圖表示出右邊的過程r=mMODnm=nn=rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？r=mMODnm=nn=rr=0?是否開始

輸入兩個(gè)正數(shù)m,n

輸出m,n結(jié)束INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).

20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.(53)思考:你能用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？寫出算法步驟、程序框圖和程序。

輸入兩個(gè)正數(shù)m,n否開始r=mMODnr≠0?輸出n結(jié)束m=nn=r是INPUTm,nr=mMODnWHILEr<>0m=nn=rr=mMODnWENDPRINTnEND《九章算術(shù)》——更相減損術(shù)算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給定兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所求的最大公約數(shù)。例3

用更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減98－63＝35

63－35＝28

35－28＝7

28－7＝2121－7＝1414－7＝7所以，98和63的最大公約數(shù)等于7練習(xí)3：分別用輾轉(zhuǎn)相除法和更相減損術(shù)求204與85的最大公約數(shù)。

解：思考：把更相減損術(shù)與輾轉(zhuǎn)相除法相比較，你有什么發(fā)現(xiàn)？你能根據(jù)更相減損術(shù)設(shè)計(jì)程序，求兩個(gè)正整數(shù)的最大公約數(shù)嗎？S1:給定兩個(gè)正整數(shù)m,n不妨設(shè)m>n;S2：若m,n都是偶數(shù)，則不斷用2約簡，使它們不同時(shí)是偶數(shù)，約簡后的兩個(gè)數(shù)仍記為m,n;S3：d=m-n;S4:判斷“d≠n”是否成立。若是，則將n,d中的較大者記為m，較小者記為n，返回s3;否則，2kd(k時(shí)約簡整數(shù)的2的個(gè)數(shù))為所求的最大公約數(shù)。開始輸m,n(m>n)K=0M,n為偶數(shù)?K=k+1M=m/2N=n/2D=m-nD<>n?D>n?否M=nN=dD=m-nM=d是輸出2^k*d結(jié)束是否否是INPUT“m,n=“;m,nIFm<nTHENa=m

m=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+