算法第8課時_輾轉(zhuǎn)相除法與更相減損術(shù)

1、算法第8課時 輾轉(zhuǎn)相除法與更相減損術(shù)一、【學(xué)習(xí)目標(biāo)】1、用輾轉(zhuǎn)相除法求最大公約數(shù).2、用更相減損術(shù)求最大公約數(shù).【教學(xué)效果】：教學(xué)目標(biāo)的給出有利于學(xué)生從整體上把握課堂.二、【自學(xué)內(nèi)容和要求及自學(xué)過程】1、閱讀教材3435頁內(nèi)容，回答問題（輾轉(zhuǎn)相除法）<1>怎樣用短除法求最大公約數(shù)？<2>怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？<3>什么叫做輾轉(zhuǎn)相除法求最大公約數(shù)？結(jié)論：<1>求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個互質(zhì)數(shù)為止，然后把所有的質(zhì)數(shù)連乘起來.<2>窮舉法求兩個正整數(shù)最大公約數(shù)的步

2、驟：從兩個數(shù)中較小數(shù)開始，由大到小列舉，直到找到公約數(shù)立即停止列舉，得到的公約數(shù)便是最大公約數(shù).<3>輾轉(zhuǎn)相除法求最大公約數(shù)，其算法步驟可以描述如下：第一步，給定兩個正整數(shù)m，n.第二步，求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中.第三步，更新被除數(shù)和余數(shù)：m=n，n=r.第四步，判斷余數(shù)r是否為0.若余數(shù)為0，則輸出結(jié)果，否則轉(zhuǎn)向第二步繼續(xù)循環(huán)執(zhí)行.如此循環(huán)直到得到結(jié)果為止.這種算法是由歐幾里得在公元前300年左右首先提出的，因此又叫做歐幾里得算法.練習(xí)一：用短除法求18和31的最大公約數(shù).用輾轉(zhuǎn)相除法求8251與6105的最大公約數(shù).畫出輾轉(zhuǎn)相除法的程序框圖，并寫出程序.

3、綜合：請畫出輾轉(zhuǎn)相除法的程序和框圖.【教學(xué)效果】：理解輾轉(zhuǎn)相除法.2、閱讀教材3637頁內(nèi)容，回答問題（更相減損術(shù)）<4>怎樣用更相減損術(shù)求最大公約數(shù)？結(jié)論：<4>九章算術(shù)是中國古代的數(shù)學(xué)專著，其中的更相減損術(shù)也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”其算法如下：第一步，任意更定兩個正整數(shù)，判斷它們是否都是偶數(shù).若是，用2約減，若不是，則執(zhí)行第二步.第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約減的

4、數(shù)的乘積就是最大公約數(shù).練習(xí)二：用更相減損術(shù)求98與63的最大公約數(shù).【教學(xué)效果】：理解更相減損術(shù).思考：輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別與聯(lián)系是什么？1o都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯.2o從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.三、三維目標(biāo)（a）知識與技能1.理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析。2.基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序。（b）

5、過程與方法在輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的學(xué)習(xí)過程中對比我們常見的約分求公因式的方法，比較它們在算法上的區(qū)別，并從程序的學(xué)習(xí)中體會數(shù)學(xué)的嚴(yán)謹(jǐn)，領(lǐng)會數(shù)學(xué)算法計算機(jī)處理的結(jié)合方式，初步掌握把數(shù)學(xué)算法轉(zhuǎn)化成計算機(jī)語言的一般步驟。（c）情態(tài)與價值觀1.通過閱讀中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻(xiàn)。2.在學(xué)習(xí)古代數(shù)學(xué)家解決數(shù)學(xué)問題的方法的過程中培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S能力，在利用算法解決數(shù)學(xué)問題的過程中培養(yǎng)理性的精神和動手實踐的能力。四、教學(xué)重難點重點：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。難點：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。五、教學(xué)設(shè)計（一）

6、創(chuàng)設(shè)情景，揭示課題1.教師首先提出問題：在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出18與30的公約數(shù)嗎？2.接著教師進(jìn)一步提出問題，我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容。3.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余

7、數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到4.課堂練習(xí)一.用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)，并在自己編寫的BASIC程序中驗證。（1）225；135 （2）98；196 （3）72；168 （4）153；1195.小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的計算方法及完整算法程序的編寫。六、自我測評 1. 用輾轉(zhuǎn)相除法求295和85的最大公約數(shù)時,需要做出除法的次數(shù)是 ( ) A 1. B 2. C 3. D 4 2. 用輾轉(zhuǎn)相除法求567和405的最大公約數(shù)是 ( ) A 81 B 7 C 5. D 35 3. 求98,196的最大公約數(shù)_。4. 用輾轉(zhuǎn)相除法求1443和999的最大公約數(shù)_。5.用輾轉(zhuǎn)相除法求168,56,264的最大公約數(shù)是_.。6、用更相減損術(shù)求294和84的最大公約數(shù)時，需做減法的次數(shù)是_.七、合作交流完成下列問題1、 輾轉(zhuǎn)相除法和更相減損術(shù)用來解決什么問題？2、 在輾轉(zhuǎn)相除法中，下一步驟中的被除數(shù)和除數(shù)分別是上一步驟中的什么數(shù)？3、 在輾轉(zhuǎn)相除法中，在什么情況下除法停止？4、 依據(jù)課本第35頁的算法步驟寫出求m與n最大