董世都++劉智++張宜浩++朱常鵬

摘要：算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一，但卻受到了國內(nèi)高校相關(guān)專業(yè)及學(xué)生的冷落。他們認(rèn)為學(xué)習(xí)計(jì)算機(jī)就是學(xué)習(xí)各種編程語言，對(duì)算法學(xué)習(xí)沒有興趣。但是算法的學(xué)習(xí)更加重要，因?yàn)橛?jì)算機(jī)語言和開發(fā)平臺(tái)日新月異，但萬變不離其宗的是那些算法。本文論述一個(gè)增強(qiáng)學(xué)生算法學(xué)習(xí)興趣的算法實(shí)驗(yàn)設(shè)計(jì)方法。讓學(xué)生在實(shí)驗(yàn)中體驗(yàn)算法學(xué)習(xí)的重要性，通過實(shí)驗(yàn)發(fā)現(xiàn)問題，分析問題出現(xiàn)的原因，尋找解決問題的辦法，從而將原來的被動(dòng)學(xué)習(xí)轉(zhuǎn)化為主動(dòng)學(xué)習(xí)。

關(guān)鍵字：算法；實(shí)驗(yàn)設(shè)計(jì)；動(dòng)態(tài)規(guī)劃

中圖分類號(hào)：G642.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2017）16-0215-02

一、引言

算法是計(jì)算機(jī)科學(xué)領(lǐng)域的最重要的基石之一，但在國內(nèi)卻受到了高校及學(xué)生的冷落[1]。許多公司招聘往往要求Java，C#及C++等相關(guān)語言及相關(guān)平臺(tái)。因而許多學(xué)生認(rèn)為，學(xué)習(xí)計(jì)算機(jī)就是學(xué)習(xí)各種編程語言及相關(guān)平臺(tái)，對(duì)算法的學(xué)習(xí)不感興趣。計(jì)算機(jī)語言和開發(fā)平臺(tái)日新月異，PowerBuilder，Visual Basic，Dephi及Visual Foxpro都曾經(jīng)很流行，但現(xiàn)在使用的人很少?，F(xiàn)在流行的是Java，C#，C++等語言，十幾年后他們是否還流行？實(shí)際上，不管編程語言及相關(guān)平臺(tái)如何變化，萬變不離其宗的是算法。許多計(jì)算機(jī)領(lǐng)域的創(chuàng)新實(shí)質(zhì)是算法的創(chuàng)新。真正學(xué)懂計(jì)算機(jī)的人，不只是“編程匠”，他們既能用科學(xué)家的嚴(yán)謹(jǐn)思維來求證，也能用工程師的務(wù)實(shí)手段來解決問題——而這種思維和手段的最佳演繹就是“算法”[1]。因而，有人地把算法等基本課程比擬為“內(nèi)功”，把語言、平臺(tái)及相關(guān)技術(shù)與標(biāo)準(zhǔn)比擬為“外功”。整天趕時(shí)髦的人最后只懂得招式，沒有功力，是不可能成為高手的[1]。

本文論述一種利用實(shí)驗(yàn)增強(qiáng)學(xué)生算法學(xué)習(xí)興趣的方法。在實(shí)驗(yàn)中，讓學(xué)生體驗(yàn)算法學(xué)習(xí)的重要性，明白改進(jìn)算法比升級(jí)計(jì)算機(jī)重要得多；讓學(xué)生通過實(shí)驗(yàn)發(fā)現(xiàn)問題，分析問題出現(xiàn)的原因，尋找解決問題的辦法，從而將原來的被動(dòng)學(xué)習(xí)轉(zhuǎn)化為主動(dòng)學(xué)習(xí)[3]。

二、實(shí)驗(yàn)設(shè)計(jì)

有的學(xué)生覺得算法不重要，因?yàn)樗麄兤綍r(shí)編寫的程序都能在幾秒時(shí)間內(nèi)完成，甚至認(rèn)為他們現(xiàn)有的計(jì)算機(jī)足夠的快，根本就沒有改進(jìn)算法的必要。因而第一實(shí)驗(yàn)，我讓學(xué)生首先實(shí)現(xiàn)Fibonacci數(shù)列的遞歸算法（以及插入排序算法），并統(tǒng)計(jì)程序運(yùn)行時(shí)間與問題的規(guī)模即n的關(guān)系（n～100）。其算法如算法1[2]：

算法1

過程 FibonacciRec（n）

1.if （n=1） or （n=2） then

2. return 1

3.else

4. return FibonacciRec（n-1）+FibonacciRec（n-2）

5.end if

學(xué)生們非常高興，覺得實(shí)驗(yàn)足夠簡(jiǎn)單，還給出了算法。他們很快就編寫好程序，并開始運(yùn)行，剛開始程序運(yùn)行很快，當(dāng)n為42以下，基本能在1秒內(nèi)完成。并觀察到，運(yùn)行時(shí)間隨n增長很快。當(dāng)n為60時(shí)需要1個(gè)多小時(shí)才能完成，圖1為學(xué)生統(tǒng)計(jì)的Fibnonacci運(yùn)行時(shí)間與n之間的關(guān)系。由此可以推算當(dāng)n為70時(shí)需要約3天的時(shí)間，n為80時(shí)需要計(jì)算約250天，n為90時(shí)，需要約203年才能完成。顯然，即使把你的計(jì)算機(jī)速度升級(jí)100倍對(duì)，當(dāng)n>80時(shí)，也是不可接受的。

然后我讓學(xué)生編程實(shí)現(xiàn)Fibonacci的非遞歸算法，算法2[2，4]：

算法2

1.input n

2.FA[1]←1

3.FA[2]←1

4.for i←3 to n

5. FA[i]←FA[i-1]+FA[i-2]

6.end for

7.output FA[n]

//若n=1或n=2，則循環(huán)不執(zhí)行。

學(xué)生發(fā)現(xiàn)，算法2執(zhí)行速很快，當(dāng)n=90時(shí)，在I3計(jì)算機(jī)運(yùn)行只需要0.056秒的時(shí)間。然后我引導(dǎo)學(xué)生尋找為什么算法2運(yùn)行速度快，而算法1運(yùn)行速慢的原因。剛開始學(xué)生認(rèn)為，算法1慢是因遞歸的原因。確實(shí)遞歸對(duì)程序速度有影響，但是影響不是太大。這是我讓學(xué)生對(duì)比遞歸與非遞歸的插入排序?qū)W生自己得出的結(jié)論。學(xué)生經(jīng)過深入的分析發(fā)現(xiàn)，算法1中隱藏著大量的重復(fù)計(jì)算，例如求7的Fibonacci數(shù)（Fibonacci（7），以下Fibonacci函數(shù)簡(jiǎn)稱F（7））需要求2次F（5），3次F（4），5次F（3），8次F（2）的計(jì)算，如圖2。因而算法1運(yùn)行的速度較慢。然后讓學(xué)生分析算法的時(shí)間復(fù)雜度，設(shè)求F（n）所需的時(shí)間為T（n）。

根據(jù)算法1可得

T（n）= 1 n=1 or n=2T（n-1）+T（n-2） n>2 （1）

求解該遞歸方程可得T（n）=（■）n=1.61803n。由此可知算1是指數(shù)時(shí)間復(fù)雜度算法，算法運(yùn)行的時(shí)間隨n增長非常快，當(dāng)n為90時(shí)，需要幾百年的時(shí)間才求出他的解，這顯然是無法接受的。

而算法2采用自底向上的方式進(jìn)行計(jì)算，并用數(shù)組FA把求得的解存儲(chǔ)起來，避免了重復(fù)計(jì)算，算法而的時(shí)間復(fù)雜度是線性的，為O（n），因而算法執(zhí)行的速度很快。當(dāng)n=90時(shí)在I3計(jì)算機(jī)上運(yùn)行只需要0.056秒的時(shí)間。算法2是一種用空間換時(shí)間的動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法，從算法1和算法2的比較中，學(xué)生體會(huì)了設(shè)計(jì)高效的算法比升級(jí)計(jì)算機(jī)重要得多。同時(shí)，該實(shí)驗(yàn)也為動(dòng)態(tài)規(guī)劃的引入做了鋪墊。

三、結(jié)論

本文用簡(jiǎn)單的Fibonacci遞歸算法與非遞歸算法設(shè)計(jì)了一個(gè)算法實(shí)驗(yàn)。通過該實(shí)驗(yàn)，讓學(xué)生體驗(yàn)了指數(shù)時(shí)間復(fù)雜度算法運(yùn)行時(shí)間與數(shù)據(jù)規(guī)模的關(guān)系，讓學(xué)生明白，對(duì)于規(guī)模稍大的問題，指數(shù)時(shí)間復(fù)雜度算法是不可接受的；通過對(duì)比兩個(gè)算法，讓學(xué)生體驗(yàn)了改進(jìn)算法比升級(jí)計(jì)算機(jī)要重要得多，而算法設(shè)計(jì)策略是改進(jìn)算法的關(guān)鍵；通過該實(shí)驗(yàn)，學(xué)生對(duì)算法產(chǎn)生濃厚的興趣，從原來的被動(dòng)學(xué)習(xí)轉(zhuǎn)變化了主動(dòng)學(xué)習(xí)。

參考文獻(xiàn)：

[1]李開復(fù).算法的力量[J].程序員，2006，（2）.

[2]M.H.Alsuwaiyel.算法設(shè)計(jì)技巧與分析[M].電子工業(yè)出版社，2012.

[3]Alfieri，L.，Brooks，P. J.，Aldrich，N.J.，& Tenenbaum，H. R.. Does discovery-based instruction enhance learning？. Journal of Educational Psychology，2011，103（1）.

[4]Thomas H.Cormen，Charles E.Leiserson，Ronald，L.Rivest，Clifford Stein，著.算法導(dǎo)論（原書第3版）[M].殷建平，徐云，王剛，等，譯.北京：機(jī)械工業(yè)出版社，2013.