1.3 算法案例第一、二課時輾轉相除法與更相減損術（ 1）教學目標（ a）知識與技能1. 理解輾轉相除法與更相減損術中蘊含的數學原理，并能根據這些原理進行算法分析。2. 基本能根據算法語句與程序框圖的知識設計完整的程序框圖并寫出算法程序。（ b）過程與方法在輾轉相除法與更相減損術求最大公約數的學習過程中對比我們常見的約分求公因式的方法，比較它們在算法上的區(qū)別，并從程序的學習中體會數學的嚴謹，領會數學算法計算機處理的結合方式，初步掌握把數學算法轉化成計算機語言的一般步驟。（ c）情態(tài)與價值1. 通過閱讀中國古代數學中的算法案例，體會中國古代數學對世界數學發(fā)展的貢獻。2. 在學習古代數學家解決數學問題的方法的過程中培養(yǎng)嚴謹的邏輯思維能力，在利用算法解決數學問題的過程中培養(yǎng)理性的精神和動手實踐的能力。（ 2）教學重難點重點：理解輾轉相除法與更相減損術求最大公約數的方法。難點：把輾轉相除法與更相減損術的方法轉換成程序框圖與程序語言。（ 3）學法與教學用具學法：在理解最大公約數的基礎上去發(fā)現輾轉相除法與更相減損術中的數學規(guī)律，并能模仿已經學過的程序框圖與算法語句設計出輾轉相除法與更相減損術的程序框圖與算法程序 。教學用具：電腦，計算器，圖形計算器（ 4）教學設想（一）創(chuàng)設情景，揭示課題1. 教師首先提出問題：在初中，我們已經學過求最大公約數的知識，你能求出18 與 30的公約數嗎？2. 接著教師進一步提出問題，我們都是利用找公約數的方法來求最大公約數，如果公約數比較大而且根據我們的觀察又不能得到一些公約數，我們又應該怎樣求它們的最大公約數？比如求8251 與 6105 的最大公約數？這就是我們這一堂課所要探討的內容。（二）研探新知1. 輾轉相除法例 1 求兩個正數8251 和 6105 的最大公約數。（分析： 8251 與 6105 兩數都比較大， 而且沒有明顯的公約數，如能把它們都變小一點，根據已有的知識即可求出最大公約數）解： 8251 6105 1 2146顯然 8251 的最大公約數也必是2146 的約數，同樣6105 與 2146 的公約數也必是8251的約數，所以8251 與 6105 的最大公約數也是6105 與 2146 的最大公約數。6105 21462 18132146 18131 3331813 333 5 148333148 23714837 401則 37 為 8251 與 6105 的最大公 數。以上我 求最大公 數的方法就是 相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300 年左右首先提出的。利用 相除法求最大公 數的步 如下：第一步：用 大的數m除以 小的數 n 得到一個商 q和一個余數r ；00第二步：若 r 0 0， n 為 m， n 的最大公 數；若r 0 0， 用除數 n 除以余數 r 0 得到一個商 q1 和一個余 數 r 1；第三步：若 r10， r為 m，n 的最大公 數；若r 0， 用除數 r0除以余數 r得到111一個商 q和一個余數 r；22依 次 算直至 r n 0，此 所得到的 r n 1 即 所求的最大公 數。 ：利用 相除法求兩數4081 與 20723 的最大公 數（答案：53）2. 更相減 我國早期也有解決求最大公 數 的算法，就是更相減 。更相減 求最大公 數的步 如下：可半者半之，不可半者，副置分母子之數，以少減多，更相減 ，求其等也，以等數 之。翻 出來 ：第一步：任意 出兩個正數；判斷它 是否都是偶數。若是，用2 ；若不是， 行第二步。第二步：以 大的數減去 小的數，接著把 小的數與所得的差比 ，并以大數減小數。 個操作，直到所得的數相等 止， 個數（等數）就是所求的最大公 數。例 2 用更相減 求98 與 63 的最大公 數 .解：由于 63 不是偶數，把98 和 63 以大數減小數，并 相減，即： 98 63 356335 283528 7287 21217 14147 7所以， 98 與 63 的最大公 數是7。 ：用更相 減 求兩個正數84與 72 的最大公 數。 （答案： 12）3. 比 相除法與更相減 的區(qū) （ 1）都是求最大公 數的方法， 算上 相除法以除法 主，更相減 以減法 主， 算次數上 相除法 算次數相 少， 特 當兩個數字大小區(qū) 大 算次數的區(qū) 明 。（ 2）從 果體 形式來看， 相除法體 果是以相除余數 0 得到，而更相減 以減數與差相等而得到4. 相除法與更相減 算的程序框 及程序利用 相除法與更相減 的 算算法，我 可以 出程序框 以及BSAIC 程序來在 算機上 相除法與更相減 求最大公 數，下面由同學 相 框 并相互之 框 與程序的正確性，并在 算機上 自己的 果。（ 1） 相除法的程序框 及程序程序框 ：2開始輸入兩個正整數 m， nm>n?否是r=m MOD n否r=0?是輸出 n結束程序：INPUT “ m=”;mINPUT “ n=”;nIF m<n THEN x=mm=nn=xEND IFr=m MOD nWHILE r< >0r=m MOD nm=nn=rWENDPRINT mEND5. 課堂練習一 . 用輾轉相除法求下列各組數的最大x=nn=mm=xn=rm=n公約數，并在自己編寫的BASIC 程序中驗證。3（ 1）225； 135 （ 2）98； 196 （ 3） 72； 168 （4） 153；119二 . 思考：用求質因數的方法可否求上述 4 組數的最大公約數？可否利用求質因數的算法設計出程序框圖及程序？若能，在電腦上測試自己的程序；若不能說明無法實現的理由。三。思考：利用輾轉相除法是否可以求兩數的最大公倍數？試設計程序框圖并轉換成程序在 BASIC中實現。6. 小結：輾轉相除法與更相減損術求最大公約數的計算方法及完整算法程序的編寫。（ 5）評價設計作業(yè)： P38 A （1） B（ 2）補充：設計更相減損術求最大公約數的程序框圖4