將數學歸納法的思想引入算法與程序設計的教學中

余克非

《算法與程序設計》的課程標準強調了學生能從簡單問題出發,設計算法解決問題,并能初步使用某種程序語言解決問題;強調的是實際問題的解決方法。

將數學歸納法的思想引入算法與程序設計的教學中可以結合數學和信息技術兩門課程優勢,使學生利用已有的知識和技能去設計正確的算法,達到培養信息素養的目的。同時,可以開辟新的教學方法,從有別于傳統程序設計教學的角度,快速高效地在中學生中普及算法知識。

以下是數學歸納法教學思路與傳統程序設計思路的對比。

數學歸納法是一種數學證明方法,典型地用于確定一個表達式在所有自然數范圍內是成立的或者用于確定一個其他的形式在一個無窮序列是成立的。

用數學歸納法進行證明的步驟:

1.(歸納奠基)證明當取第一個值時命題成立;證明了第一步,就獲得了遞推的基礎

2.(歸納遞推)假設當前命題成立,證明后續命題也成立;證明了第二步,就獲得了遞推的依據,但沒有第一步就失去了遞推的基礎。只有把第一步和第二步結合在一起,才能獲得普遍性的結論;

3.下結論:從第一個值開始的所有后續命題都成立

數學歸納法的第二種形式:第二數學歸納法原理是設有一個與自然數n有關的命題,如果:

(1)當n=1回時,命題成立;

(2)假設當n≤k時命題成立,則當n=k+1時,命題也成立。

從上可以看出數學歸納法有著很強的遞推關系,而計算機的很多算法都具備遞推關系。由此,我們可以考慮,在中學NOIP的教學過程中,可以利用數學歸納法來進行教學。

一、用于遞歸的教學

程序調用自身的編程技巧稱為遞歸。這種編程技巧可以解決很多算法問題。它也是算法的核心思想和描述方法。

一般來說,遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時,遞歸前進;當邊界條件滿足時,遞歸返回。

對比數學歸納法,我們可以這樣理解:遞歸的邊界條件即為數學歸納法的第一步,也就是當取第一個值時命題成立。遞歸的過程就是歸納遞推的方法。即假設當前命題成立,證明后續命題也成立。

例如:階乘計算

遞歸的思考方式:

1.邊界條件n=1時:n!=1。

2.遞歸過程n!=n*(n-1)!

數學歸納法的思考方式:

1.n=1時,1!=1成立

2.假設(n-1)!可以求出,則n!=

n*(n-1)!必定可以求出。

我們可以看出,遞歸的思考方式和數學歸納法是有一定相似之處的。

使用數學歸納法,除了可以引入解題的方法之外,還可以同時在數學上證明該思路是正確的。可以加深初學者對遞歸的認識并降低難度。

又例如漢諾塔問題的思考:

遞歸的思考方式:

1.邊界條件

只有一個盤子時,盤子從A柱移到C柱

2.遞歸過程

n-1個盤子從A柱移到B柱,剩下的盤子從A柱移到C柱,n-1個盤子從B柱移到C柱

數學歸納法的思考方式:

1.n=1時盤子可移,盤子從A柱移到C柱

2.假設n-1個盤子可以從一個柱子移動到另一個柱子,尋找n個盤子從一個柱子移動到另一個柱子的方法。

在初學遞歸的同學中,漢諾塔問題是學習的難點和重點。我們需要從棧、函數的調用原理、題目的思考方法來講述。從數學歸納法的思考方式來看,我們可以更好的加深學生對遞歸的理解。同時引入數學歸納法的思考方式可以更容易的證明解題的正確性。

二、用于分治的教學

一個復雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解,原問題的解即子問題的解的合并。這是分治算法的核心思想。

我們也可以看到:“最后子問題可以簡單的直接求解”即為數學歸納法中命題n=1時的階段,“問題的解的合并”即為數學歸納法中當n≤k時命題成立推n=k+1時命題成立的階段。

例如:二分排序算法利用數學歸納法的講解思路

1.n=20=1時,1個數據自然排序成功。

2.假設n=2k-1時,2組2k-1個數據分別有序,則n=2k時,可將兩組分別有序的數據通過歸并排序合并,使之有序。

可以看到,數學歸納法的講解思路不同于普通的分治排序的思考方式。但這可以激發學生從多方面思考算法的求解思路。

(3)用于動態規劃的教學

動態規劃是一種在數學和計算機科學中使用的,用于求解包含重疊子問題的最優化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎。

動態規劃思想中“將原問題分解為相似的子問題,在求解過程中通過子問題的解求出原問題的解”所具備的遞推性質,決定了動態規劃的問題思考中也可以使用數學歸納法的思想。其中的狀態轉移方程,便是第二數學歸納法中當n≤k時命題成立,推n=k+1時,命題成立的步驟。這里的性質決定了使用數學歸納法來思考,可以解決子結構和多階段規劃(無后效性)問題。

如題:

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

請編一個程序計算從頂至底的某處的一條路徑,使該路徑所經過的數字的總和最大。規定:

●每一步可沿直線向下或右斜線向下走;

●1<三角形行數≤100;

●三角形中的數字為整數0,1,…,99;

在動態規劃的題目中,數學歸納法的歸納奠基思想起到了尋找邊界條件的作用;其遞推思想則起到了劃分階段,定決策并寫出狀態轉移方程的作用。

從這里可以想到,當三角形只有一個結點時,問題自然解決。需要解決的命題是從已知1個結點的三角形結果推出具有3個結點的三角形的結果。從已知3個結點的三角形結果推出具有6個結點的三角形的結果,以此類推;即由n=k-1時命題成立推出n=k時命題成立。這樣,我們就可以引入順推和逆推的方法。最終得到該題的狀態轉移方程。

在整個的教學過程中,學生所學的知識始終由原有的知識進行遷移轉化,利于學生的理解和接受?？梢源蟠蠛喕瘎討B規劃的教學難度,加快學生入門的速度。

從這里可以看到,凡是具備分層和遞推形式的問題都可以使用數學歸納法的思想。所以在進行算法教學中,可以將數學歸納法思想作為主線,貫穿于遞歸、分治和動態規劃的教學中。使學生從縱向上加深對算法的理解。學生在學習過程中,整合了數學和程序設計。

作者單位:深圳中學