1、1.3算法案例問題提出1.研究一個實際問題的算法，主要從 算法步驟、程序框圖和編寫程序三方面 展開.在程序框圖中算法的基本邏輯結構 有哪幾種？在程序設計中基本的算法語 句有哪幾種？2.“求兩個正整數的最大公約數” 是數學中的一個基礎性問題，它有各種 解決辦法，我們以此為案例，對該問題 的算法作一些探究.知識探究（一）：輾轉相除法思考1:18與30的最大公約數是多少？你 是怎樣得到的？先用兩個數公有的質因數連續去除, 一直除到所得的商是互質數為止，然 后把所有的除數連乘起來即為最大公 約數.例.求30和75的最大公約數3| 30 755嚴2525所以，30和35的最大 公約數為15思考2:對于8

2、251與6105這兩個數，由于 其公有的質因數較大，利用上述方法求 最大公約數就比較困難注意到8251=6105X1+2146,那么8251與6105這 兩個數的公約數和6105與2146的公約數 有什么關系？148=37X4+0思考3:又6105=2146X2+1813,同理,6105與2146的公約數和2146與1813的公約數相等重復上述操作，你能得到8251與6105這兩個數的最大公約數嗎?8251=6105X1+2146, 6105=2146X2+1813,2146=1813X1+333, 1813=333X5+148,333=148X2+,148=X4+0.舉蓉相除法中狗羌健步瞬是

3、哪種邏輯輾轉相除法是一個反復執行直到余數等于0停止的步驟，這實際上是 一個循環結構。8251=6105X1+21466105=2146X2+18132146=1813X1+3331813=333X5+148用程333=48 X 2+思考5:上述求兩個正整數的最大公約數 的方法稱為輾轉相除法或歐幾里得算法. 一般地，用輾轉相除法求兩個正整數m, n的最大公約數，可以用什么邏輯結構來 構造算法？其算法步驟如何設計？ 第一步，給定兩個正整數m, n (mn).第二步，計算m除以n所得的余數工第三步，m=n, n=r.第四步，若r=0,則m, n的最大公約數等于m;否則，返回第二步.思考5:該算法的程

4、序框圖如何表示?結束思考6:該程序框圖對應的程序如何表述?INPUT m, nDOr=m MODnm=n n=rLOOP UNTIL r=0 PRINT mEND思考7:如果用當型循環結構構造算法，則用輾轉相除法求兩個正整數m,n的最 大公約數的程序框圖和程序分別如何表 示？求m除以m=n否INPUT m, nWHILE n0 r=mMODn m=nn=rWENDPRINT m END練習1：利用輾轉相除法求兩數4081與20723的最大公約數.20723=4081X5+314081=318X12+265;/蕭出結束265=53X5+0.知識探究(二)：更相減損術思考1： 設兩個正整數mn,若

5、m-n=k,貝!Jm與n的最大公約數和n與k的最大公約數相 等反復利用這個原理，可求得98與63的 最大公約數為多少？98-63=35,63-35=28，35-28=7,28-7=21,21-7=14,14-7=7.思考2:上述求兩個正整數的最大公約數 的方法稱為更相減損術一般地， 用更相 減損術求兩個正整數叫n的最大公約數， 可以用什么邏輯結構來構造算法？其算 法步驟如何設計？第一步，給定兩個正整數n (mn)第二步，計算m-n所得的差k.第三步，比較n與k的大小，其中大者用示，小者用n表示.第四步，若m=n,則m, n的最大公約數等于m;否則，返回第二步.INPUTm, nWHILEmon

6、k=m-nIF nkTHEN思思考4:該程序框圖對應的程序如何表述?開始n=kELSE ,PRIN“更相減損術”在中國古代數學專著九章算術中記述為：可半者半之，不可半者，副置分母、子 之數，以少減多，更相減損，求其等也， 以等數約之.INPUTum,n=u;m,nWhile donIFmn thena=mm=dm=nELSEn=am=nEND IFn=dK=0End ifWHILE m MOD 2=0d=m-nAND n MOD 2=0Wendm=m/2d=2Ak*dn=n/2PRINT dk=k+1EndWENDd=m- n理論遷移例1分別用輾轉相除法和更相減損 術求168與93的最大公約數

7、.輾轉相除法：168=93X1+75, 93=75X1+18,75=18X4+3,18=3X6.更相減損術: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,例2求325, 130, 270三個數的最大 公約數.因為325=130X2+65, 130=65X2,所以325與130的最大公約數是65.因為270=65X4+10, 65=10X6+5,10二5X2,所以65與270最大公約數是5.故325, 130, 270三個數的最大公約 數是5.小結作業1輾轉相除法，就是對于給定的兩個正整 數，用較大的數除以較小的數，若余數不為 零，則將余數和較小的數構成新的一對數， 繼續上面的除法，直到大數被小數除盡為止， 這時的較小的數即為原來兩個數的最大公約 數.2.更相減損術，就是對于給定的兩個正 整數，用較大的數減去較小的數，然后將差 和較小的數構成新的一對數，繼續上面的減 法，直到差和較小的數相等，此時相等的兩 數即為原來兩個數的最大公約數.小結比較輾轉相除法與更相減損術的區別(1)都是求最大公約數的方法，計算上輾轉相除 法以除法為主，更相減損術以減法為主，