8輾轉(zhuǎn)相除法與更相減損術(shù)(精)

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

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

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

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

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