1.3.1 輾轉(zhuǎn)相除法 和更相減損術(shù),臨高中學(xué) 李吉傳 2013年5月8日,復(fù)習(xí),1.研究一個(gè)實(shí)際問(wèn)題的算法，主要從哪幾方面展開？,2.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？,3.在程序設(shè)計(jì)中基本的算法語(yǔ)句有哪幾種？,算法步驟、程序框圖和編寫程序三方面展開.,順序結(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ù)呢？,思考3：注意到8251=61051+2146，那么8251與6105這兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？,我們發(fā)現(xiàn)6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.,思考4：重復(fù)上述操作，你能得到8251與6105這兩個(gè)數(shù)的最大公約數(shù)嗎？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.,第一步，給定兩個(gè)正整數(shù)m，n(mn).,第二步，計(jì)算m除以n所得的余數(shù)r.,第三步，m=n，n=r.,第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.,思考5:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？,程序框圖,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,思考6:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示？,INPUT m，n,WHILE r0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,二、更相減損術(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=931+75， 93=751+18， 75=184+3， 18=36.,輾轉(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=1302+65，130=652，所以325與130的最大公約數(shù)是65.,因?yàn)?70=654+10，65=106+5，10=52，所以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(mn).,第二步，計(jì)算m-n所得的差k.,第三步，比較n與k的大小，其中大者用m表示，小者用n表示.,第四步，若m=n，則m，n的最大公約數(shù)等于m；否則，返回第二步.,討論:該算法的程序框圖如何表示？,討論:該程序框圖對(duì)應(yīng)的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk T