輾轉(zhuǎn)相除法與更相減損術(shù)課件.ppt

1、1.3 算法案例,第一課時,問題提出,1.研究一個實際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪三種？在程序設計中基本的算法語句有哪五種？,2.“求兩個正整數(shù)的最大公約數(shù)”是數(shù)學中的一個基礎性問題，它有各種解決辦法，我們以此為案例，對該問題的算法作一些探究.,輾轉(zhuǎn)相除法與 更相減損術(shù),知識探究（一）:輾轉(zhuǎn)相除法,思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？,先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù).,思考2:對于8251與6105這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法

2、求最大公約數(shù)就比較困難.,注意到: 8251=61051+2146 那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？,思考3:又6105=21462+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.重復上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎？,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,思考4:上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.一般地，用輾轉(zhuǎn)相除法求兩個正

3、整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，計算m除以n所得的余數(shù)r.,第三步，m=n，n=r.,第四步，若r=0，則m，n的最大公約數(shù)等 于m；否則，返回第二步.,思考5:該算法的程序框圖如何表示？,思考6:該程序框圖對應的程序如何表述？,INPUT m，n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,INPUT m，n,WHILE n0,r=m MOD n,m=n,n=r,WEND,PRINT m,END,思考7:用當型循環(huán)結(jié)構(gòu)構(gòu)造算法:,“更相減損術(shù)”在中國

4、古代數(shù)學專著九章算術(shù)中記述為：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之.,知識探究（二）:更相減損術(shù),第一步：任意給定兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。,第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。,思考1:求98與63的最大公約數(shù)？,98-63=35,14-7=7,21-7=14,28-7=21,35-28=7,63-35=28,思考2:上述求兩個正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù).一般地，用更相減損術(shù)求兩

5、個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設計？,第一步，給定兩個正整數(shù)m，n(mn).,第二步，判斷mn是否成立.若不成立,則輸 出m,否則轉(zhuǎn)第三步.,第四步，比較n與k的大小，其中大者用m表 示，小者用n表示.之后轉(zhuǎn)第二步.,第三步，計算m-n所得的差k.,思考3:該算法的程序框圖如何表示？,思考4:該程序框圖對應的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,理論遷移,例1 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).,輾轉(zhuǎn)

6、相除法：168=931+75， 93=751+18， 75=184+3， 18=36+0.,更相減損術(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.,例2 求325，130，270三個數(shù)的最大公約數(shù).,因為325=1302+65，130=652，所以325與130的最大公約數(shù)是65.,因為270=654+10，65=106+5，10=52+0，所以65與270最大公約數(shù)是5.,故325，130，270三個數(shù)的最大公約數(shù)是5.,1.輾轉(zhuǎn)相除法，就是對于給定的兩個正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù).,小結(jié)作業(yè),2. 更相減損術(shù)，就是對于給定的兩個正整數(shù)，用較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)構(gòu)成新的一對數(shù)，繼續(xù)上面的減法，直到差和較小的數(shù)相等，此時相等的兩數(shù)即為原來兩個數(shù)的最大公約數(shù).,比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別,1.都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)