一個增強算法學習興趣的算法實驗設計

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

摘要：算法是計算機科學領域最重要的基石之一，但卻受到了國內高校相關專業及學生的冷落。他們認為學習計算機就是學習各種編程語言，對算法學習沒有興趣。但是算法的學習更加重要，因為計算機語言和開發平臺日新月異，但萬變不離其宗的是那些算法。本文論述一個增強學生算法學習興趣的算法實驗設計方法。讓學生在實驗中體驗算法學習的重要性，通過實驗發現問題，分析問題出現的原因，尋找解決問題的辦法，從而將原來的被動學習轉化為主動學習。

關鍵字：算法；實驗設計；動態規劃

中圖分類號：G642.4 文獻標志碼：A 文章編號：1674-9324（2017）16-0215-02

一、引言

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

本文論述一種利用實驗增強學生算法學習興趣的方法。在實驗中，讓學生體驗算法學習的重要性，明白改進算法比升級計算機重要得多；讓學生通過實驗發現問題，分析問題出現的原因，尋找解決問題的辦法，從而將原來的被動學習轉化為主動學習[3]。

二、實驗設計

有的學生覺得算法不重要，因為他們平時編寫的程序都能在幾秒時間內完成，甚至認為他們現有的計算機足夠的快，根本就沒有改進算法的必要。因而第一實驗，我讓學生首先實現Fibonacci數列的遞歸算法（以及插入排序算法），并統計程序運行時間與問題的規模即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

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

然后我讓學生編程實現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，則循環不執行。

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

根據算法1可得

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

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

而算法2采用自底向上的方式進行計算，并用數組FA把求得的解存儲起來，避免了重復計算，算法而的時間復雜度是線性的，為O（n），因而算法執行的速度很快。當n=90時在I3計算機上運行只需要0.056秒的時間。算法2是一種用空間換時間的動態規劃的設計方法，從算法1和算法2的比較中，學生體會了設計高效的算法比升級計算機重要得多。同時，該實驗也為動態規劃的引入做了鋪墊。

三、結論

本文用簡單的Fibonacci遞歸算法與非遞歸算法設計了一個算法實驗。通過該實驗，讓學生體驗了指數時間復雜度算法運行時間與數據規模的關系，讓學生明白，對于規模稍大的問題，指數時間復雜度算法是不可接受的；通過對比兩個算法，讓學生體驗了改進算法比升級計算機要重要得多，而算法設計策略是改進算法的關鍵；通過該實驗，學生對算法產生濃厚的興趣，從原來的被動學習轉變化了主動學習。

參考文獻：

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

[2]M.H.Alsuwaiyel.算法設計技巧與分析[M].電子工業出版社，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，著.算法導論（原書第3版）[M].殷建平，徐云，王剛，等，譯.北京：機械工業出版社，2013.