1、輾轉相除法與更相減損術復習回顧1研究一個實際問題的算法，主要從算法步驟、程序框和編寫程序三方面展開在程序框圖中算法的基本邏輯結 構有哪幾種？在程序設計中基本的算法語句有哪幾種?新課引入2“求兩個正整數的最大公約數”是數學中的一個基礎性 問題，它有各種解決辦法，我們以此為案例，對該問題的 算法作一些探究.K創設情景，揭示課題H問題1：在小學，我們已經學過求最大公約數的知 識，你能求出18與30的最大公約數嗎？先用兩個數公有的質因數連 續去除，一直除到所得的商是 互質數為止，然后把所有的除 數連乘起來.ex：(1)求25和35的最大公約數( (2)求49和63的最大公約數K創設情景，揭示課題H問題

2、2:我們都是利用找公約數的方法來求最 大公約數，如果公約數比較大而且根據我們的 觀察又不能得到一些公約數，我們又應該怎樣 求它們的最大公約數？比如求8251與6105的最 大公約數？318和30的最大公約數是2X3=6.(1)52535(2)7496379思考2:對于8251與6105這兩個數，由于其公有的質因數 較大，利用上述方法求最大公約數就比較困難了.注意到8251=6105X1+2146,8251與6105的公約數和6105與2146的公約數相同又6105=2146X2+1813,同理，6105與2146的公約數和2146與1813的公約數相等. 重復上述操作，你能得到8251與610

3、5這兩個數的 最大公約數37148=37X4+0.8251=6105X1+2146,6105=2146X2+1813,2146=1813X1+333,1813=31813=333X5+148,333=14完整的過程例如，用輾轉相除法求225和135的最大公約數8251=6105X1+214225=135X1+90/1813=333X5+148148=37X4+0顯然45是90和45的最大公約數， 也思考：從上面的兩個例子可以看出計算的規律是什么？用大顯然37是148和37的最大公約數， 也就是除數變成被除數，余數變成除數S3：重復S1,直到余思埶援轉相除法中的關鍵步驟是哪種邏解構2輾轉相除法是

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

5、53X5+0.匕述算法的程序框圖如何表示?INPUT練習2072320723=4081 X5+31出m /結束知識探究（二）：更相減損術思考1:設兩個正整數mn,若mn=k,則m與n的最大公約數 和n與k的最大公約數；相等.反復利用這個原理，可求得：98與63的最大公約數為798-63=35,63-35=28,35-28=7,28-7=21,21-7=14, 14-7=7.理論遷移例1求168與93的最大公約數.（要求：分別用輾轉相除法和更相減損術） 輾轉相除法：168=93X1+75,93=75X1+18,75=18X4+3,18=3X6+0 故最大公約數為312-3=9,9-3=6,這種求兩個正整數的最大公約數的 方法稱為更相減損術.總鬆93-75=18,756-3=3 理論遷移例2.求325, 130, 270三個數的最大公約數.所以325與130的最大公約數是65.又因為270=65X4+10, 65=10X6+5, 10=5X2+0,所以65與270最大公約數是5.故325, 130, 270三個數的最大公約數是5.課堂練習比 _1.用輾轉相除法計算60與48的最大公約數時，需要做_ 次除法運算。2.分別用輾轉相除法和更相減損術計算288與123的最大公 約數。|課堂小結1輾轉程序程序m,“更相減損術”在中國古代數學專著九章算術中記述 為：可半