演算法的概念教學設計案例

演算法的概念教學設計案例

　　目標：

　　1、知識目標：瞭解演算法。分析演算法。

　　2、能力目標：體驗程式的獨特魅力，瞭解程式設計加工的內在機制，培養學生的創新能力。

　　3、情感目標：透過程式設計實現資訊的加工，激發學生的興趣，增加學生的成就感。

　　重點：如何分析演算法，演算法的概念 ，演算法的表示

　　難點： 如何寫演算法。理解用演算法描述實際問題，理解人的思維在計算機工作中發揮的作用。

　　方法：講授法，演示法，歸納法

　　教學反思：

　　教 學 過 程

　　一、匯入

　　在學習程式設計時，既要掌握所使用的某種計算機計算機語言如PASCAL語言，更好掌握解題的方法和步驟，這是程式設計中的關鍵。語言只是一個工具，只懂得語言的規則並不能編制出有效的高質量的程式，下面所講座的演算法，就是研究解題的步驟和方法，這是程式設計的基礎，同時也是我們解數理化題的基礎。

　　著名計算機科學家沃思提出一個公式:

　　資料結構 + 演算法 = 程式

　　二、新授

　　什麼是演算法：廣義地說，為解決一個問題而採取的方法和步驟，就稱為“演算法”。或者說：演算法是解題方法的精確描述。解決一個問題的過程，就是實現一個演算法的過程。

　　1．做任何事情都有一定的步驟。例如要計算的值，無論手算，心算，或用算盤，計算器計算，都要經過有限的事先設計好的步驟。

　　2、對同一個問題，往往有不同的解題方法和步驟

　　如

　　方法1：順序計算1-1/2+1/3-1/4+1/5……+1/99-1/100，一直加到100 加99次

　　方法2：先計算+，再計算減，即1+1/3+1/5……+1/99，1/2+1/4+1/6……+1/100當然各種方法有優劣之分。

　　3、不僅數值計算的問題要研究演算法，實際上，做任何事情。都需要事先設想好的步驟和方法，這就是演算法。

　　計算機演算法可分為兩大類別：

　　數值運算

　　非數值運算

　　數值運算舉例：求數值解，例如求方程的根、求函式的定積分等。

　　非數值運算舉例：人名排序，圖書資料檢索等.

　　三、簡單演算法舉例

　　為了理解如何設計算法，下面舉幾個演算法的簡單例子。

　　[例1] 有兩個杯子A和B，分別盛有果汁和酒，要求將這兩個杯子進行互換。

　　（請學生回答，並要求說清楚明確的步驟）

　　學生所回答的步驟就是演算法的描述：

　　根據常識，必須增加一個空杯C作為過渡。

　　其演算法表示

　　步驟1：先將A杯中的果汁倒在C杯中；

　　步驟2：再講B杯中的酒倒在A杯中；

　　步驟3：最後將C杯中的果汁倒在B杯中。

　　此問題可以抽象為數值運算中的交換兩個變數的值，簡化為：

　　①A → C

　　②B → A

　　③C → B

　　[例2] 從十個數中挑選出最大的數。

　　創設情景：這個問題的思路可以用“打描臺”來比喻。第一個同學先上講臺，然後第二個同學上去比試，勝者（個子高的）留在講臺上，依次輪流，一直到第十個人比完為止（）一共九次）最後留在講臺上的同學就是勝者（個子最高的同學）。

　　演算法描述：

　　1．先任選一個數放在變數A中；

　　2．將第二個數與變數A中的數進行比較，大者放在變數A中；

　　3．再將第三個數與變數A中的數進行比較，大者放在變數A中；

　　10．最後將第十個數與變數A中的數進行比較，大者放在變數A中。

　　這樣寫演算法雖然正確，但是太煩瑣了，可以簡化為如下：

　　1．數X → A，計數器 0 → N；

　　2．下一個數Y與A比較，大者→ A；

　　3．N + 1 → N；（增加一次比較次數）

　　4．若N ? 9，執行第2步，否則停止迴圈，此時A中的數最大。

　　顯然，用“迴圈”表示的演算法比較簡練。

　　如果題目要求改為“從1000個數中挑選最大者”，只許需要將演算法裡面的第4步中的“9”改為“999”即可。

　　[例3] 求兩個正整數m和n的最大公約數。

　　解題之前介紹“輾轉相除法”求最大公約數的方法。“輾轉”就字面意思來講是翻來覆去的意思，因此“輾轉相除法”的.格式可以形象地表示為：

　　將m和n賦具體值，m = 60，n = 14，板書具體求解方法。

　　用m 作被除數， n 作除數，r 做餘數。

　　具體方法（演算法）為：

　　①求m/n的餘數r；

　　②若r = 0 ，則n為最大公約數，若r ≠ 0，執行第③步；

　　③將n → m，將r → n中；

　　④返回重新執行第①步。

　　注意：如果事先不知道M,N兩個數誰大誰小，應（可）在第一步之前增加一個步驟，比較一下兩個數的大小，大數在m中，小數在n中。

　　四、演算法的特性

　　1、有窮性：一個演算法應該包含有限個操作步驟，而不能是無限的。

　　2、確定性：演算法的每個步驟都應該是明確無誤的，不能含義模糊，使執行者無所適從。

　　3、有零個或者多個輸入

　　4、有一個或者多個輸出

　　5、有效性：演算法中的每一步都應該能有效地執行，執行演算法最後應該能得到確定的結果。

　　五、歸納總結

　　演算法的概念；

　　演算法的描述；

　　演算法的特性：

　　有窮性：包含有限的操作步驟

　　確定性：演算法中的每一個步驟都應當是確定的

　　有零個或多個輸入：輸入是指在執行演算法時需要從外界取得必要的資訊

　　有一個或多個輸出：演算法的目的是為了求解，“解” 就是輸出

　　有效性：演算法中的每一個步驟都應當能有效地執行，並得到確定的結果 。

　　對於程式設計人員來說，我們不僅要會使用現成的演算法，還要會設計算法，即要設計出演算法中的每一個步驟。

　　六、 練習

　　①用輾轉相除法求324和180的最大公約數。

　　七、板書設計