人教必修三《1.3.1輾轉(zhuǎn)相除法與更相減損術(shù)》

1.3算法案例輾轉(zhuǎn)相除法與更相減損術(shù)1.3算法案例韓信是秦末漢初的著名軍事家.據(jù)說(shuō)有一次漢高祖劉邦在衛(wèi)士的簇?fù)硐聛?lái)到練兵場(chǎng),劉邦問(wèn)韓信有什么方法,不要逐個(gè)報(bào)數(shù),就能知道場(chǎng)上的士兵的人數(shù),韓信先令士兵排成3列縱隊(duì),結(jié)果有2人多余,接著下令排成5列縱隊(duì),結(jié)果又多出3人,隨后他又下令改為7列縱隊(duì),這次又剩下2人無(wú)法成整行.在場(chǎng)的人都哈哈大笑,以為韓信不能清點(diǎn)出準(zhǔn)確的人數(shù),不料笑聲剛落,韓信高聲報(bào)告共有士兵2333人.眾人聽(tīng)了一楞,不知道韓信用什么方法這么快就能得到正確的結(jié)果的.今天,我們將以這些古典案例的思想,設(shè)計(jì)出適宜計(jì)算機(jī)的運(yùn)行程序,提高我們對(duì)基本算法結(jié)構(gòu)和算法語(yǔ)句在實(shí)際中的運(yùn)用能力.情境創(chuàng)設(shè)探究一：輾轉(zhuǎn)相除法思考一：在小學(xué)里我們是如何救出兩個(gè)正整數(shù)的最大公約數(shù)的？算法案例之求最大公約數(shù)解：２１８２４用公有質(zhì)因數(shù)２除

３９１２用公有質(zhì)因數(shù)３除３４３和４互質(zhì)，不除了得：１８和２４的最大公約數(shù)：２x３＝６短除法例：求１８與24的最大公約數(shù)想一想，如何求8251與6105的最大公約數(shù)？思考2:對(duì)于8251與6105這兩個(gè)數(shù)，它們的最大公約數(shù)是多少？你是怎樣得到的？由于它們公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.有沒(méi)有其它的方法可以較簡(jiǎn)單的找出它們的最大公約數(shù)呢？思考3：注意到8251=6105×1+2146，那么8251與6105這兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？我們發(fā)現(xiàn)6105=2146×2+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.思考4：重復(fù)上述操作，你能得到8251與6105這兩個(gè)數(shù)的最大公約數(shù)嗎？2146=1813×1+333，148=37×4+0.8251=6105×1+2146，6105=2146×2+1813，定義:所謂的輾轉(zhuǎn)相除法,就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)除以較小的數(shù),若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì),繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡,則這是較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)例1觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過(guò)程第一步用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)

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

6105=2146×2+1813

同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。完整的過(guò)程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù)思考：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？輾轉(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用程序框圖表示出右邊的過(guò)程r=mMODnm=nn=rr=0?是否思考5:該算法的程序框圖如何表示？思考6:該程序框圖對(duì)應(yīng)的程序如何表述？IN，nDOr=mMODnm=nn=rLOOPUNTILr=0END開(kāi)始m=nn>0？結(jié)束是n=rIN，nWHILEn>0r=mMODnm=nn=rWENDEND知識(shí)探究（二）:更相減損術(shù)98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，思考3:該算法的程序框圖如何表示？IN，nWHILEm<>nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDEND理論遷移思考：把更相減損術(shù)與輾轉(zhuǎn)相除法比較，你有哪些發(fā)現(xiàn)？