余克非

《算法與程序設(shè)計(jì)》的課程標(biāo)準(zhǔn)強(qiáng)調(diào)了學(xué)生能從簡(jiǎn)單問題出發(fā),設(shè)計(jì)算法解決問題,并能初步使用某種程序語(yǔ)言解決問題;強(qiáng)調(diào)的是實(shí)際問題的解決方法。

將數(shù)學(xué)歸納法的思想引入算法與程序設(shè)計(jì)的教學(xué)中可以結(jié)合數(shù)學(xué)和信息技術(shù)兩門課程優(yōu)勢(shì),使學(xué)生利用已有的知識(shí)和技能去設(shè)計(jì)正確的算法,達(dá)到培養(yǎng)信息素養(yǎng)的目的。同時(shí),可以開辟新的教學(xué)方法,從有別于傳統(tǒng)程序設(shè)計(jì)教學(xué)的角度,快速高效地在中學(xué)生中普及算法知識(shí)。

以下是數(shù)學(xué)歸納法教學(xué)思路與傳統(tǒng)程序設(shè)計(jì)思路的對(duì)比。

數(shù)學(xué)歸納法是一種數(shù)學(xué)證明方法,典型地用于確定一個(gè)表達(dá)式在所有自然數(shù)范圍內(nèi)是成立的或者用于確定一個(gè)其他的形式在一個(gè)無(wú)窮序列是成立的。

用數(shù)學(xué)歸納法進(jìn)行證明的步驟:

1.(歸納奠基)證明當(dāng)取第一個(gè)值時(shí)命題成立;證明了第一步,就獲得了遞推的基礎(chǔ)

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

3.下結(jié)論:從第一個(gè)值開始的所有后續(xù)命題都成立

數(shù)學(xué)歸納法的第二種形式:第二數(shù)學(xué)歸納法原理是設(shè)有一個(gè)與自然數(shù)n有關(guān)的命題,如果:

(1)當(dāng)n=1回時(shí),命題成立;

(2)假設(shè)當(dāng)n≤k時(shí)命題成立,則當(dāng)n=k+1時(shí),命題也成立。

從上可以看出數(shù)學(xué)歸納法有著很強(qiáng)的遞推關(guān)系,而計(jì)算機(jī)的很多算法都具備遞推關(guān)系。由此,我們可以考慮,在中學(xué)NOIP的教學(xué)過(guò)程中,可以利用數(shù)學(xué)歸納法來(lái)進(jìn)行教學(xué)。

一、用于遞歸的教學(xué)

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

一般來(lái)說(shuō),遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí),遞歸前進(jìn);當(dāng)邊界條件滿足時(shí),遞歸返回。

對(duì)比數(shù)學(xué)歸納法,我們可以這樣理解:遞歸的邊界條件即為數(shù)學(xué)歸納法的第一步,也就是當(dāng)取第一個(gè)值時(shí)命題成立。遞歸的過(guò)程就是歸納遞推的方法。即假設(shè)當(dāng)前命題成立,證明后續(xù)命題也成立。

例如:階乘計(jì)算

遞歸的思考方式:

1.邊界條件n=1時(shí):n!=1。

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

數(shù)學(xué)歸納法的思考方式:

1.n=1時(shí),1!=1成立

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

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

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

使用數(shù)學(xué)歸納法,除了可以引入解題的方法之外,還可以同時(shí)在數(shù)學(xué)上證明該思路是正確的?？梢约由畛鯇W(xué)者對(duì)遞歸的認(rèn)識(shí)并降低難度。

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

遞歸的思考方式:

1.邊界條件

只有一個(gè)盤子時(shí),盤子從A柱移到C柱

2.遞歸過(guò)程

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

數(shù)學(xué)歸納法的思考方式:

1.n=1時(shí)盤子可移,盤子從A柱移到C柱

2.假設(shè)n-1個(gè)盤子可以從一個(gè)柱子移動(dòng)到另一個(gè)柱子,尋找n個(gè)盤子從一個(gè)柱子移動(dòng)到另一個(gè)柱子的方法。

在初學(xué)遞歸的同學(xué)中,漢諾塔問題是學(xué)習(xí)的難點(diǎn)和重點(diǎn)。我們需要從棧、函數(shù)的調(diào)用原理、題目的思考方法來(lái)講述。從數(shù)學(xué)歸納法的思考方式來(lái)看,我們可以更好的加深學(xué)生對(duì)遞歸的理解。同時(shí)引入數(shù)學(xué)歸納法的思考方式可以更容易的證明解題的正確性。

二、用于分治的教學(xué)

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

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

例如:二分排序算法利用數(shù)學(xué)歸納法的講解思路

1.n=20=1時(shí),1個(gè)數(shù)據(jù)自然排序成功。

2.假設(shè)n=2k-1時(shí),2組2k-1個(gè)數(shù)據(jù)分別有序,則n=2k時(shí),可將兩組分別有序的數(shù)據(jù)通過(guò)歸并排序合并,使之有序。

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

(3)用于動(dòng)態(tài)規(guī)劃的教學(xué)

動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的,用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是,將原問題分解為相似的子問題,在求解的過(guò)程中通過(guò)子問題的解求出原問題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)。

動(dòng)態(tài)規(guī)劃思想中“將原問題分解為相似的子問題,在求解過(guò)程中通過(guò)子問題的解求出原問題的解”所具備的遞推性質(zhì),決定了動(dòng)態(tài)規(guī)劃的問題思考中也可以使用數(shù)學(xué)歸納法的思想。其中的狀態(tài)轉(zhuǎn)移方程,便是第二數(shù)學(xué)歸納法中當(dāng)n≤k時(shí)命題成立,推n=k+1時(shí),命題成立的步驟。這里的性質(zhì)決定了使用數(shù)學(xué)歸納法來(lái)思考,可以解決子結(jié)構(gòu)和多階段規(guī)劃(無(wú)后效性)問題。

如題:

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

請(qǐng)編一個(gè)程序計(jì)算從頂至底的某處的一條路徑,使該路徑所經(jīng)過(guò)的數(shù)字的總和最大。規(guī)定:

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

●1<三角形行數(shù)≤100;

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

在動(dòng)態(tài)規(guī)劃的題目中,數(shù)學(xué)歸納法的歸納奠基思想起到了尋找邊界條件的作用;其遞推思想則起到了劃分階段,定決策并寫出狀態(tài)轉(zhuǎn)移方程的作用。

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

在整個(gè)的教學(xué)過(guò)程中,學(xué)生所學(xué)的知識(shí)始終由原有的知識(shí)進(jìn)行遷移轉(zhuǎn)化,利于學(xué)生的理解和接受。可以大大簡(jiǎn)化動(dòng)態(tài)規(guī)劃的教學(xué)難度,加快學(xué)生入門的速度。

從這里可以看到,凡是具備分層和遞推形式的問題都可以使用數(shù)學(xué)歸納法的思想。所以在進(jìn)行算法教學(xué)中,可以將數(shù)學(xué)歸納法思想作為主線,貫穿于遞歸、分治和動(dòng)態(tài)規(guī)劃的教學(xué)中。使學(xué)生從縱向上加深對(duì)算法的理解。學(xué)生在學(xué)習(xí)過(guò)程中,整合了數(shù)學(xué)和程序設(shè)計(jì)。

作者單位:深圳中學(xué)