輾轉(zhuǎn)相除法與更相減損術(shù)-精講版課件

1.3算法案例

第一課時(shí)問(wèn)題提出1.兩種條件語(yǔ)句的一般格式分別是什么？格式1:IF條件THEN

語(yǔ)句體ENDIF問(wèn)題提出1.兩種條件語(yǔ)句的一般格式分別是什么？格式2:IF條件THEN

語(yǔ)句體1ELSE

語(yǔ)句體2ENDIF格式1:IF條件THEN

語(yǔ)句體ENDIF2.兩種循環(huán)語(yǔ)句的一般格式分別是什么？循環(huán)體滿足條件？是否DO

循環(huán)體LOOPUNTIL條件2.兩種循環(huán)語(yǔ)句的一般格式分別是什么？循環(huán)體滿足條件？是否DO

循環(huán)體LOOPUNTIL條件2.兩種循環(huán)語(yǔ)句的一般格式分別是什么？循環(huán)體滿足條件？是否循環(huán)體滿足條件？是否DO

循環(huán)體LOOPUNTIL條件2.兩種循環(huán)語(yǔ)句的一般格式分別是什么？循環(huán)體滿足條件？是否WHILE

條件

循環(huán)體WEND

循環(huán)體滿足條件？是否問(wèn)題提出1.研究一個(gè)實(shí)際問(wèn)題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計(jì)中基本的算法語(yǔ)句有哪幾種？2.“求兩個(gè)正整數(shù)的最大公約數(shù)”是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問(wèn)題，它有各種解決辦法，我們以此為案例，對(duì)該問(wèn)題的算法作一些探究.輾轉(zhuǎn)相除法與更相減損術(shù)知識(shí)探究（一）:輾轉(zhuǎn)相除法思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？

先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái)即為最大公約數(shù).思考2:對(duì)于8251與6105這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.注意到8251=6105×1+2146，那么8251與6105這兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？思考3:又6105=2146×2+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.重復(fù)上述操作，你能得到8251與6105這兩個(gè)數(shù)的最大公約數(shù)嗎？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，思考4:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？第一步，給定兩個(gè)正整數(shù)m，n(m>n).第二步，計(jì)算m除以n所得的余數(shù)r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等 于m；否則，返回第二步.

思考5:該算法的程序框圖如何表示？開始輸入m，n求m除以n的余數(shù)rm=nn=rr=0？是輸出m結(jié)束否思考6:該程序框圖對(duì)應(yīng)的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTIL

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

思考1:設(shè)兩個(gè)正整數(shù)m>n，若m-n=k，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等.反復(fù)利用這個(gè)原理，可求得98與63的最大公約數(shù)為多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，思考2:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù).一般地，用更相減損術(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；否則，返回第二步.思考3:該算法的程序框圖如何表示？開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否思考4:該程序框圖對(duì)應(yīng)的程序如何表述？INPUTm，nWHILEm<>nk=m-nIFn>kTHENm=nn=kELSEm=kENDIFWENDPRINTmEND開始輸入m，nn>k？m=n是輸出m結(jié)束m≠n？k=m-n是否n=km=k否“更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專著《九章算術(shù)》中記述為：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之.理論遷移

例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相減損術(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三個(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.1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)