AA3007=高一數(shù)學(xué)(1.3-1輾轉(zhuǎn)相除法與更相減(精)

1、1. 3算法案例第一課時(shí)問(wèn)題提出1研究一個(gè)實(shí)際問(wèn)題的算法，主要從算法步驟、程序框圖和編寫(xiě)程序三方面展開(kāi).在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計(jì)中基本的算法語(yǔ)句有哪幾種?2“求兩個(gè)正整數(shù)的最大公約數(shù)” 是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問(wèn)題，它有各種 解決辦法，我們以此為案例，對(duì)該問(wèn)題 的算法作一些探究.知識(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ù)就比較困難注意到

2、8251=6105X1+2146,那么8251與6105這 兩個(gè)數(shù)的公約數(shù)和6105與2146的公約數(shù) 有什么關(guān)系？思考3:又6105=2146X2+1813,同理，6105與2146的公約數(shù)和2146與1813的公 約數(shù)相等重復(fù)上述操作，你能得到8251與6105這兩個(gè)數(shù)的最大公約數(shù)嗎？8251=6105X1+2146,6105=2146X2+1813, 2146=1813X1+333,1813=333X5+148, 333=148X2+ ,148=X4+0思考4:上述求兩個(gè)正整數(shù)的最大公約數(shù) 的方法稱(chēng)為輾轉(zhuǎn)相除法或歐幾里得算法. 一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m, n的最大公約數(shù)，可以用

3、什么邏輯結(jié)構(gòu)來(lái) 構(gòu)造算法？其算法步驟如何設(shè)計(jì)？ 第一步，給定兩個(gè)正整數(shù)m, n(mn).第二步，計(jì)算m除以n所得的余數(shù)r.第三步，m=n, n=r.第四步，若r=0,則m, n的最大公約數(shù)等于m;否則，返回第二步.思考5:該算法的程序框圖如何表示?/ 11，求 m 除以 n 的余數(shù) r思考6:該程序框圖對(duì)應(yīng)的程序如何表述?INPUT m, nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mm=n否出 m/MSEND思考7:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法， 則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m, n的最 大公約數(shù)的程序框圖和程序分別如何表 示？/侖出m /INPUTWHILEm=

4、m9nn0MODnrxi知識(shí)探究(二)：更相減損術(shù)思考1:設(shè)兩個(gè)正整數(shù)mn,若m-n二k,貝Ijm與n的最大公約數(shù)和n與k的最大公約數(shù)相 等反復(fù)利用這個(gè)原理，可求得98與63的 最大公約數(shù)為多少？98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.7-7=0.思考2:上述求兩個(gè)正整數(shù)的最大公約數(shù) 的方法稱(chēng)為更相減損術(shù).一般地，用更相 減損術(shù)求兩個(gè)正整數(shù)m, n的最大公約數(shù), 可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算 法步驟如何設(shè)計(jì)？第一步，給定兩個(gè)正整數(shù)叫n (mn).第二步，計(jì)算m-n所得的差k.第三步，比較11與k的大小，其中大者用示，小者用n表示.

5、第四步，若m=n,則m, n的最大公約數(shù)等于m;否則，返回第二步.思考4:該程序框圖對(duì)應(yīng)的程序如何表述?INPUT m, n WHILEmon k=m-nIF nk THEN m=nn=kELSE ,m=kEND IFWEND思考3:該算法的程序框圖如何表示?PRINT mEND“更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專(zhuān)著九章算術(shù)中記述為：可半者半之，不可半者，副置分母、子 之?dāng)?shù)，以少減多，更相減損，求其等也, 以等數(shù)約之.理論遷移例1分別用輾轉(zhuǎn)相除法和更相減損 術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法：168=93X1+75,93=75X1+18,75=18X4+3,18=3X6+0.更相減損術(shù):168

6、-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=130X2+65，130=65X2,所以325與130的最大公約數(shù)是65.10=5X2,所以65與270最大公約數(shù)是5.故325, 130, 270三個(gè)數(shù)的最大公約 數(shù)是5小結(jié)作業(yè)為27065=11輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)， 用較大的數(shù)除以較小的數(shù)， 若余數(shù)不為 零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)， 繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止, 這時(shí)的較小的數(shù)即為原來(lái)兩個(gè)數(shù)的最大公約數(shù).2.更相減損術(shù)，就是對(duì)于給定的兩個(gè)正 整數(shù)，