數學人教版必修三：1.3 算法案例 第一課時 輾轉相除法與更相減損術

1、1.3 算法案例輾轉相除法與更相減損術鄭州一中鄭州一中 胡莉萍胡莉萍人教版（數學）必修三人教版（數學）必修三引入課題引入課題求求24與與9的最大公約數？的最大公約數？知識準備知識準備249 26 (24,9)(9,6)2493996 請同學們結合課本的基礎知識，思請同學們結合課本的基礎知識，思考解決考解決學習指導書學習指導書第第1-2頁問題。頁問題。 請同學們討論各自的疑惑及感悟，請同學們討論各自的疑惑及感悟，提出問題，并相互解決。提出問題，并相互解決。1. 關于輾轉相除法的算理問題關于輾轉相除法的算理問題82516105 1214661052146 2 181321461813 1 3331

2、813333 5 148333148 23714837 4 (8251,6105)(6105,2146)(6105,2146)(2146,1813)(2146,1813)(1813,333)(1813,333)(333,148)(333,148)(148,37)(148,37)37 所以所以(8251,6105)(148,37)37 (0)0,( , )0,( , )( , )mn qrrnrm nnrm nn r若則若則1. 關于輾轉相除法的算理問題關于輾轉相除法的算理問題, ,m n qrNN以上滿足：以上滿足：第二步，計算第二步，計算m除以除以n所得的余數所得的余數r . 第三步，第三步

3、，m=n，n=r.第四步，若第四步，若r=0，則，則m，n的最大公約數等于的最大公約數等于m；否則，返回第二步否則，返回第二步. 第一步，給定兩個正整數第一步，給定兩個正整數m，n .2. 設計算法之設計算法之 算法步驟算法步驟（1）確立循環(huán)體）確立循環(huán)體:求求m除以除以n的余數的余數 r, m=n, n=r（2）初始化變量：輸入）初始化變量：輸入m, n（3）設定循環(huán)控制條件：）設定循環(huán)控制條件：r=0？2. 設計算法之設計算法之 構造循環(huán)結構構造循環(huán)結構求求m除以除以n的余數的余數r開始開始輸入輸入m，nm=nn=rr=0？是是輸出輸出m結束結束否否例例1 用更相減損術求用更相減損術求98

4、與與63的最大公約數的最大公約數.解：由于解：由于63不是偶數，把不是偶數，把98和和63以大數減小數，并以大數減小數，并輾轉相減，如圖所示：輾轉相減，如圖所示： 98 9863633535 636335352828 353528287 7 28287 72121 21 217 71414 14147 77 7所以，所以，98與與63的最大公約數是的最大公約數是73. 3. 更相減損術更相減損術名稱名稱輾轉相除法輾轉相除法更相減損術更相減損術區(qū)別區(qū)別聯系聯系 （1）以除法為主）以除法為主. （2）兩個整數差值較）兩個整數差值較大時運算次數較少大時運算次數較少. （3）相除余數為零時）相除余數為

5、零時得結果得結果. （1）以減法為主）以減法為主. （2）兩個整數差值較大時）兩個整數差值較大時運算次數較多運算次數較多. （3）相減，兩數相等得結）相減，兩數相等得結果，相減前要做是否都是偶果，相減前要做是否都是偶數的判斷數的判斷. （1）都是求最大公約數的方法）都是求最大公約數的方法. （2）二者的實質都是遞推的過程）二者的實質都是遞推的過程. （3）二者都要用循環(huán)結構來實現）二者都要用循環(huán)結構來實現.開始開始i=m+1輸入：輸入：m,nm MOD i=0且且n MOD i=0?i=i-1輸出：輸出：i結束結束是是否否mn?t=m,m=n,n=t否否是是兩個正整數兩個正整數 的的最小公倍數的算法最小公倍數的算法, a b最小公倍數a b最大公約數求求m除以除以n的余數的余數r開始開始輸入輸入m，nm=nn0？否否輸出輸出是是n=r SmSm n1.必做題：用輾轉相除法求下列兩數的最大公約必做題：用輾轉相除法求下列兩數的最大公約數，并用更相減損術檢驗你的結果：數，并用更相減損術檢驗你的結果： （1）228，48；（；（2）185，98.2.選做題：求選做題：求225，135最小公倍數最小公