算法教學中的幾點思考

摘要：算法是程序的核心，如何讓計算機專業的學生學好算法設計與分析這門課，提出了算法實現，第一個問題以及子集樹和排列樹三個方面的重要性。

關鍵詞：算法；程序；教學

中圖分類號：G642文獻標識碼：A文章編號：1009-3044(2008)36-2799-01

Several Thought of Algorithm Teaching

WU Su-ping

(School of Mathematics and Computer Science， Ningxia University， Yinchuan 750021， China)

Abstract: Algorithm is the core of programme， How to learn the Algorithm design and analysis for computer students， the important of algorithm implement， the frist question and subset tree and permutation tree is provided in this paper.

Key words: Algorithm; Programme; Teaching

1 引言

程序=算法+數據結構，如果想通過計算機完成一項任務，必須通過程序來實現，而程序的核心、靈魂是算法，因此，算法的設計與分析的重要性可見一斑。算法設計與分析是一門理論性與實踐性相結合的課程，是一門面向應用，在計算機科學與技術學科中處于核心地位的課程。通過該課程學習學生應掌握常用算法設計策略，提高軟件開發設計和解決計算機科學與工程領域中較復雜的實際問題的能力；同時通過學習算法復雜性分析，培養學生在軟件開發中注重效率的理念[1]。計算機專業的學生學習算法的設計與分析的最重要的目標之一，應當是在程序開發中的應用。因此，計算機專業的學生學好算法設計與分析這門課是非常重要的。文獻[1-4]分別就算法教材建設以及算法教學中的教學方法，教學內容，教學手段以及教學改革方面做了論述。如何讓計算機專業的學生能夠學好這門課，本文結合教學實踐經驗，提出了算法實現、第一個問題以及子集樹和排列樹三個方面的重要性。

2 算法實現的重要性

算法設計與分析的書籍很多[5-8]，但是，大多教材沒有從計算機專業教學的角度來考慮內容的選擇。很多算法設計與分析的教材中，忽視了算法實現。

算法教學一般按照從算法設計的思想到算法效率的分析兩個步驟來講，往往也輕視了算法實現這一環節。對計算機專業的學生，這一環節應是非常重要的。在算法的教學過程中，學生最頭痛的不是算法思想的理解，而是算法實現讀不懂。算法設計策略的講授，算法設計及算法分析的講授都較容易，學生也容易接受，但在講授算法實現時，尤其是一些復雜算法的實現，卻需煞費苦心，大費口舌。算法思想和實現往往相差甚遠，經常會使學生摸不著頭腦，如何把一個設計思想，用程序實現，如何進行過度？在教學過程中需要精心設計。

例如矩陣連乘問題：給定n個矩陣{A1，A2，…，An}，其中Ai與Ai+1是可乘的，i=1，2，…，n-1?？疾爝@n個矩陣的連乘積A1A2…An，提出矩陣連乘積的最優計算次序問題。用動態規劃法解矩陣連乘積的最優計算次序問題，可遞歸地定義最優值。

其中m[i][j] 為計算A[i，j]，1≤i≤j≤n，所需的最少數乘次數[9]。

用動態規劃法解此問題，可依據其遞歸式以自底向上的方式進行計算。在計算過程中保存以解決的子問題答案，每個子問題只計算一次，而在后面需要時只需簡單查一下，從而避免大量的重復計算，最終得到多項式時間算法[9]。

實現時如何保存已解決的子問題的答案？如何完成自底向上？講授時引導學生思考，引導學生思考數組有什么特性？利用數組可重復使用的特性，將m[i][j]用數組實現，解決保存已解決子問題答案。m[i][j]，1≤i≤j≤n，實際上是矩陣m[i][j]，1≤i≤j≤n主對角線以上的元素。讓學生用m[i][j]一條一條表示出主對角線以上每條次對角線上的元素，引導學生發現每一條次對角線上的元素實際上是表示了同一矩陣鏈長的矩陣連乘積的信息。將m[i][j]，1≤i≤j≤n，自底向上，從左向右對一條一條次對角線上元素求解，最終求得的m[i][j]，即是問題的答案。搞清了自底向上的含義，如何實現自底向上？引導學生思考，可用一個循環控制矩陣鏈長，其次內嵌一個循環求一條次對角線上的各個m[i][j]。在遞歸式中每個 ，其中i

為了鞏固應用所學內容，算法實現的上機環節非常重要，要求學生必須上機實現一些經典算法，體會經典算法的經典實現。

3 每一章的第一個問題的重要性

每一章開始的第一個問題應是該章重點講授的內容，要講清，講透該章的第一個問題的算法的設計思想及實現過程。

例如，在講授分治策略這一章時，通過透徹講授二分搜索算法的設計與實現，讓學生掌握分治法的基本思想和算法設計的基本步驟。讓學生通過該問題的學習學會對一個問題如何進行分解，如何遞歸求解及如何進行合并，并要求學生掌握算法的實現。在講授動態規劃這一章時，通過透徹講授矩陣連乘問題的算法設計與實現，讓學生掌握動態規劃法的基本思想和算法設計的基本步驟。通過學習該問題，讓學生理解最優子結構的概念，重疊子問題等，以及如何建立遞歸關系，尤其是如何實現遞歸過程，以及與分治法實現的區別，等等。總之，講透每一章的第一個問題的算法設計與實現，是學好每一章的關鍵所在。

4 子集樹和排列樹的重要性

用回溯法和分支限界法進行算法設計時，首先要分析該問題屬于子集樹問題還是排列樹問題，構造出其解空間樹，寫出解向量結構，據此條件設計出其算法。因此，講清子集樹和排列樹是非常重要的。教材中一般對具體問題都沒有畫出問題的解空間樹，在教學過程中，通過實例讓學生學會如何構造出子集樹或排列樹，比如，要求學生構造出0-1背包問題，最大團問題，n后問題，旅行售貨員問題，批處理作業調度問題等等問題解空間樹，讓學生區分哪些問題的解空間樹屬于子集樹，哪些又屬于排列樹。歸納出它們的特點。在此基礎上學習用回溯法和分支限界法進行算法設計，學生會更加容易理解算法的設計與實現過程。

5 結束語

算法是程序設計的核心，對計算機專業的學生，講清算法的設計思想與實現是同等重要的。另外，為了讓學生順利地學好每一章的全部內容，每一章的第一個問題的算法設計思想與實現必須講透。子集樹和排列樹是回溯法和分支限界法進行算法設計時的核心，因此，講清子集樹和排列樹，要求學生能構造出所給問題的解空間是學生學好這兩章的根本所在。

參考文獻：

[1] 呂國英.“算法設計與分析”教材建設實施[J]. 計算機教育，2007(10):92-93.

[2] 陸向艷.“算法設計與分析”教學方法探討[J]. 廣西大學學報（哲學社會科學版），2006(28):99-100.

[3] 劉波.“算法設計與分析”教學探討[J].高等理科教育，2007(4):78-80.

[4] 宋文，嚴兵，等. 算法設計與分析課程改革實施方案[J].高等教育研究，2008，25(1):34-35.

[5] 盧開澄.計算機算法導引——設計與分析[M]. 北京：清華大學出版社，2003.

[6] 鄭宗漢，鄭曉明.算法設計與分析[M].北京:清華大學出版社，2005.

[7] T H Cormen，CE Leisersen，R LRivest，C Stein.Introduction to Algorithms[M]，2nd ed.NewYork:McGraw-Hill，2001.

[8] Kunth D E. The art of computer programming[M] . volume 1/Fundamental Algorithms， volume3/Sorting and Searching ，Addison2Wesley Publishing Company ， Inc. ，1993.

[9] 王曉東. 算法設計與分析[M].北京：清華大學出版社，2002.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”