算法設計與分析課程案例教學模式的探討

秦敏，王井陽，喬世權

（河北科技大學 信息科學與工程學院，河北石家莊 050018）

作為問題求解和程序設計的重要基礎——算法設計與分析在計算機科學與技術專業的課程體系中是一門重要的必修課，通過該課程的學習，不但為學習其他專業課程奠定了扎實的基礎，也對培養學生的邏輯思維和創造性起著不可替代的作用[1]。算法課程作為計算機學科的一門專業核心課程，尤其注重培養學生算法基本理論知識和計算思維、問題建模、算法設計與分析能力[2]。

1 教學目標

本課程是計算機科學與技術專業的重要課程，由于課程的難度比較大，那么課程要達到什么目標，如何講授好這門課就是值得探討的課題。目標定得太高和太低都不可行，在這里給出本學校關于這門課的教學目標，希望和大家探討。本課程是為讓學生掌握經典算法，學會用算法編程解決實際問題而設立。通過本課程的學習，使學生能夠掌握經典算法，并且能夠使用C 語言編程實現算法，以案例為驅動，理解算法開發過程，最終達到能夠進行問題建模并用算法進行分析和設計的目標。

2 基于COID 的討論式案例教學模式

為了充分發揮學生的主動性，讓學生成為主體，并不斷提高學生解決問題的能力和編程能力，借鑒CDIO 思想進行了教學模式的設計，稱為“基于COID的討論式案例教學模式”。CDIO 思想是國際工程教育的通用思想，即構思（Conceive）、設計（Design）、實現（Implement）、運作（Operate）[3]。在這個模式里教師提出案例問題，學生思考解決問題的算法策略，并編程實現，最后教師主持學生討論，比如從案例中發現的算法間的區別，以及比較誰的方法最優，即哪種算法具有最小的時間復雜度或空間復雜度。在這個過程中，教師和學生的任務如表1所示。

表1 基于CDIO 的討論式案例教學模式表

每一個案例都經過上述四個過程，經過幾個案例之后，學生的編程能力顯著提高。在案例的指導和討論中，主要注意以下幾個方面：比較算法策略之間的關系，討論誰的方法最優，以及思維方法的滲透。

2.1 比較算法策略之間的關系

由于課本重點是講算法策略，對策略之間的關系并沒有特別說明。如何才能讓學生更好地理解算法策略，這里采用了通過案例來進行算法策略比較的方法。例如分治策略是將原問題分解為若干個規模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。因為在求解大問題時，需要遞歸地求解小問題，因此一般用遞歸的方法實現，即自頂向下。動態規劃把求解過程變成一個多步判斷的過程，每一步都對應某個子問題，算法細心地劃分子問題的邊界，從小的子問題開始，逐層向上求解，通過子問題之間的依賴關系，有效利用前面已經得到的結果，最大限度減少重復工作，以提高算法效率[1]。

分治策略和動態規劃都是將原問題分解為若干個規模較小的子問題，求解這些子問題（Conquer），然后再合并這些子問題的解來建立原問題的解，那么這兩個算法策略之間的區別是什么呢？是否所有能用動態規劃解決的問題都可以用分治策略解決呢？區別在于這些子問題是否會有依賴，子問題在求解后，可能會再次求解，于是需要將這些子問題的解存儲起來，當下次再次求解這個子問題時，可以直接使用。動態規劃所解決的問題是分治策略所解決問題的一個子集，只是這個子集更適合用動態規劃來解決，從而只需更少的運行時間。即用動態規劃能解決的問題，分治策略肯定能解決，只是運行時間更長。因此，分治策略一般用來解決子問題相互獨立的情況，各個子問題之間不能有依賴關系，稱為標準分治，而動態規劃用來解決子問題之間有依賴的情況。為了讓學生理解這一點，設計了兩個案例。案例“安排比賽日程表”要求按某種規則安排n 個選手的比賽日程表，當n 比較大時，手動已無法安排，只能采用分治策略，安排n 個選手分成安排兩個n/2 的選手，依次類推直到人數少到可以安排為止，這是一個分治策略的案例。“求圖中兩點間的最短路徑”是一個動態規劃的案例，通過這兩個案例來讓學生體會兩個算法策略的區別。

再比如動態規劃一般由兩種方法來實現，一種為自頂向下的備忘錄方式，用遞歸實現，一種為自底向上的方式，用遞推實現。“求圖中兩點間的最短路徑”要求學生用兩種方法編程，體會其中的區別。并用動態規劃和分治策略兩種算法策略求解“求圖中兩點間的最短路徑”，比較哪種更合適，進而思考什么情況下更適合用動態規劃策略，什么情況下更適合用分治策略？再比如既然動態規劃通常用遞推來實現，那么它與遞推之間是什么關系？動態規劃求解的多階段決策問題必須滿足最優子結構特性，而遞推所求解的問題則無須滿足。動態規劃求解的是最優化問題，遞推求解的是判定性問題、構造性或計數性問題。比如“整幣兌零”若求解最少零幣個數屬于求最優解，可以采用動態規劃算法，如果求解的是不同的兌換種數則是計數性問題，只能采用遞推算法。再比如“0-1 背包問題”，是算法課程中動態規劃策略教學的重要內容。0-1 背包問題可描述為：存在1 個有限容量的背包和一組有限個數的物品，已知背包的容量以及每個物品的重量和價值，如何選擇裝入背包的物品，使得在不超過背包容量的前提下裝入背包的物品的總價值最大[4]。這是一個典型的動態規劃算法策略的問題，而動態規劃算法隨著背包容量增大、物品數量增加，其運行時間逐漸增加。貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解，是一種近似算法。從求解效率來說，貪心算法比動態規劃更高，可以使用“0-1 背包問題”案例讓學生比較兩種算法的運行時間，進而讓學生理解當求解最優解時間太長的話那么接受一個近似解也是可以的。

2.2 討論誰的方法最優

在案例評價階段，要組織學生討論比較誰的方法最優，比如“韓信點兵”這個案例，韓信在點兵的時候，為了知道有多少個士兵，同時又能保住軍事機密，便讓士兵排隊報數。按從1 至5 報數，記下最末一個士兵的數為1；再按從1 至6 報數，記下最末一個士兵的數為5；再按從1 至7 報數，記下最末一個士兵的數為4；再按從1 至11 報數，記下最末一個士兵的數為10。韓信至少有多少兵？韓信點兵是一個典型的枚舉算法的案例，但并不是一個一個數值地枚舉，如何枚舉才能枚舉次數最少，運行時間最短，學生提出了各種各樣的方案。

方案1：初始值40，步長30 的方案，程序結果顯示枚舉次數為70 次。

方案2：初始值65，步長66 的方案，程序結果顯示枚舉次數為32 次。

方案3：初始值32，步長77 的方案，程序結果顯示枚舉次數為28 次。

還有各種其他方案，通過對這些方案的比較，學生對枚舉的認識進一步提高。再比如“求圖中兩點間的最短路徑”，就圖的存儲，有的學生存儲了圖中所有的點和所有的邊，有的學生則知道這是一個鄰接矩陣。鄰接矩陣是一個對稱的矩陣，因為A 點到B 點的距離為X，B 點到A 點的距離也為X，所以只保存上三角就可以了，減少了空間復雜度。而在算法上有的學生采用“Dijkstra”算法，有的學生采用動態規劃算法，可以就不同的圖，比較兩種算法的運行時間。總之通過設置案例讓學生編程，然后互相討論互相比較，一方面教學相長，另一方面也提高了學生的編程能力。

2.3 思維方法的滲透

國內教材大部分都是按照基本算法策略進行章節劃分，它們主要以分治法、貪心法、動態規劃法、回溯法、分枝限界法等算法策略來組織內容，這樣有利于學生著重體會各種算法的思想[5]。這種教學方式的優點是學生在遇到具體問題時往往能夠較快地選擇合適的算法策略作為解題思路，然后根據現有算法作一定的變換后找到新問題的解決方法；缺點是對于那些無法明確歸類為某種算法策略的問題則可能無法迅速找到解題思路。所以在教學過程中有意識滲透一些科學思維方法，比如比較與分類方法、順向思維與逆向思維方法、分析與整合方法、發散與收斂方法、搭橋過河方法和模糊性思維方法等。如果遇到無法明確歸類為某種算法策略的問題，學生可以從更高一級的思維方法出發，來找到解題的思路。在教學中有意識地講解科學的思維方法，不但有助于學生學習，而且有助于學生開闊思路，對于學生以后的人生也有幫助。

比較與分類方法是貫穿始終的，比如回溯法與枚舉法的比較、遞推與遞歸的比較、遞歸與動態規劃的比較、動態規劃與分治策略之間的比較等[6]。枚舉法和回溯法都屬于搜索技術，動態規劃和分治策略都屬于分析與整合方法，諸如此類的分類有助于學生的總結和理解。順向思維與逆向思維方法也是經常用到的，比如遞推有順推有逆推，采用哪種遞推須根據實際情況來定。在編程中更是經常把乘法變成除法或者除法變成乘法、開方變成平方或者平方變成開方等。分析與整合方法，整個程序設計是結構化的、是分模塊的，很多算法也體現了分析和整合方法，比如遞推、動態規劃和分治策略。發散與收斂方法，教學中采用的討論式案例教學法就是一種發散與收斂方法，把案例布置下去，學生提出不同的解決方案，這屬于發散，再討論比較找出最佳方案，這屬于收斂。模糊性思維方法，在自然界與日常生活中，許多現象帶有不確定性，很難建立確切的數學模型，也不是所有問題都要求最優解，這時就用到了模擬算法和貪心算法。表2給出了部分算法和思維方法之間的分類聯系。

表2 算法和思維方法之間的分類聯系

3 結語

算法作為一門比較難學的課程，如何才能講授好這門課是很多教師需要討論的問題。案例式教學可以發揮學生的主動性，提高學生分析問題和解決問題的能力。本文根據COID 思想提出了一種討論式案例教學法供大家探討，強調在教學過程中對算法的比較和程序的優化，并建議從更高一級的思維方法入手，進一步開闊學生的思路。