高二上冊數學算法案例教學計劃

【課程分析】：

在前面的兩節裏，我們已經學習了一些簡單的算法，對算法已經有了一個初步的瞭解。這節課的內

容是繼續加深對算法的認識，體會算法的思想。這節課所學習的輾轉相除法與更相減損術是第三節我們所要學習的四種算法案例裏的第一種。學生們透過本節課對中國古代數學中的算法案例——輾轉相除法與更相減損術學習，體會中國古代數學對世界數學發展的貢獻。教學重點是理解輾轉相除法與更相減損術求最大公約數的'方法。難點是把輾轉相除法與更相減損術的方法轉換成程序框圖與程序語言。

【學情分析】：

在理解最大公約數的基礎上去發現輾轉相除法與更相減損術中的數學規律，並能模仿已經學過的程序框

圖與算法語句設計出輾轉相除法與更相減損術的程序框圖與算法程序。

【設計思路】

採用啓發式，並遵循循序漸進的教學原則。這有利於學生掌握從現象到本質，從已知到未知逐步

形成唸的學習方法，有利於發展學生抽象思維能力和邏輯推理能力。

【學習目標】

(1)理解輾轉相除法與更相減損術中蘊含的數學原理，並能根據這些原理進行算法分析。

(2)基本能根據算法語句與程序框圖的知識設計完整的程序框圖並寫出算法程序。

(3)領會數學算法與計算機處理的結合方式，初步掌握把數學算法轉化成計算機語言的一般步驟。

【教學流程】

一、創設情景，揭示課題

1.教師首先提出問題：在初中，我們已經學過求最大公約數的知識，你能求出18與30的公約數嗎?

2.接着教師進一步提出問題，我們都是利用找公約數的方法來求最大公約數，如果公約數比較大而且根據我們的觀察又不能得到一些公約數，我們又應該怎樣求它們的最大公約數?比如求8251與6105的最大公約數?這就是我們這一堂課所要探討的內容。

二、研探新知，發現規律

1.輾轉相除法

例1 求兩個正數8251和6105的最大公約數。

解：8251=6105×1+2146

顯然8251的最大公約數也必是2146的約數，同樣6105與2146的公約數也必是8251的約數，所以8251與6105的最大公約數也是6105與2146的最大公約數。

6105=2146×2+1813 2146=1813×1+333

1813=333×5+148 333=148×2+37

148=37×4+0

則37爲8251與6105的最大公約數。

以上我們求最大公約數的方法就是輾轉相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉相除法求最大公約數的步驟如下：

第一步：用較大的數m除以較小的數n得到一個商q0和一個餘數r0;

第二步：若r0=0，則n爲m，n的最大公約數;若r0≠0，則用除數n除以餘數r0得到一個商q1和一個餘數r1;

第三步：若r1=0，則r1爲m，n的最大公約數;若r1≠0，則用除數r0除以餘數r1得到一個商q2和一個餘數r2;

依次計算直至rn=0，此時所得到的rn-1即爲所求的最大公約數。

(1)輾轉相除法的程序框圖及程序

程序框圖：(略)

程序：(當循環結構) 直到型結構見書37面。

INPUT “m=”;m

INPUT “n=”;n

IF m

m=n

n=x

END IF

r=m MOD n

WHILE r<>0

r=m MOD n

m=n

n=r

WEND

PRINT m

END

練習：利用輾轉相除法求兩數4081與20723的最大公約數(答案：53)

2.更相減損術

我國早期也有解決求最大公約數問題的算法，就是更相減損術。

更相減損術求最大公約數的步驟如下：可半者半之，不可半者，副置分母·子之數，以少減多，更相減損，求其等也，以等數約之。

翻譯出來爲：

第一步：任意給出兩個正數;判斷它們是否都是偶數。若是，用2約簡;若不是，執行第二步。 第二步：以較大的數減去較小的數，接着把較小的數與所得的差比較，並以大數減小數。繼續這個操作，直到所得的數相等爲止，則這個數(等數)就是所求的最大公約數。

例2 用更相減損術求98與63的最大公約數.

解：由於63不是偶數，把98和63以大數減小數，並輾轉相減，即：98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98與63的最大公約數是7。

練習：用更相減損術求兩個正數84與72的最大公約數。(答案：12)

三、對比歸納，得出結論

3.比較輾轉相除法與更相減損術的區別

(1)都是求最大公約數的方法，計算上輾轉相除法以除法爲主，更相減損術以減法爲主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。

(2)從結果體現形式來看，輾轉相除法體現結果是以相除餘數爲0則得到，而更相減損術則以減數與差相等而得到