面向問題解決能力培養的算法課程教學設計

張立臣 王小明

摘? 要：問題解決能力是目前學生亟待提升的能力之一。圍繞動態規劃算法教學，介紹了一種以問題解決能力目標為導向的教學設計，通過調整教學內容和教學過程，突出學生問題解決能力的培養和訓練，為能力目標導向的課程改革提供了一種新思路。

關鍵詞：問題解決能力;動態規劃;算法設計;教學設計

中圖分類號：G642? ? ? ?文獻標志碼：A? ? ? ? ?文章編號：2096-000X（2021）11-0105-05

Abstract： Currently， it is urgent to promote students' problem solving ability. Focusing on the teaching mode on dynamic programming algorithm， a novel teaching design scheme is introduced oriented by the goal of problem solving ability. The proposed scheme tries to adjust the teaching contents and design process， in which the training and promotion process of the students' problem solving ability is emphasized， then providing a novel idea to the ability-oriented curriculum reform.

Keywords： problem-solving ability; Dynamic Programming; algorithm design; teaching design

目前，以學生為中心的教育改革，比如，OBE（Outcomes-Based Education， 成果導向教育）[1]、系統能力培養教育[2]、計算思維能力培養教育[3]、新工科背景下的教育改革等[4]，越來越突出學生的能力培養。根據學生現有能力水平和畢業應具備的能力要求，教育改革要求教師反向設計教學內容、教學模式、教學案例和教學評價方式。

算法設計與分析是計算機學科的一門專業核心課，主要培養學生計算思維能力以及實際計算問題解決能力[5]。這些能力對學生未來從事計算機相關的教學、科研和工程實踐活動具有重要作用。因此，算法課程的教學研究和改革得到了廣泛關注，已出版了眾多案例豐富的算法教材，開發了大量在線算法課程。本文主要以算法課程中的“動態規劃算法”教學為例，設計一種新的能力目標導向的教學設計案例，突出培養和訓練學生的問題解決能力，從而為能力目標導向的課程改革提供教學案例參考和教學設計思路。

一、動態規劃算法教學

動態規劃算法解決的問題是最優化問題，其基本思想是將待求解問題分解成若干子問題，通過對子問題的迭代求解，獲得待求解問題的最優解[5]。與分治法不同，動態規劃算法更適合那些經分解得到的子問題不互相獨立的情形。在動態規劃算法中，通過保存已解決子問題的解，可避免大量重復計算，進而提高算法效率。

動態規劃算法要求待求解問題具有2個重要性質，即最優子結構性質和子問題重疊性質。最優子結構性質是指，問題的最優解可通過其所包含的子問題的最優解計算得到;子問題重疊性質是指，分解后的問題包含很多重復的子問題。通過記錄不同的子問題的解，可以大大減少求解子問題的次數。動態規劃算法具有很多實際的應用，因此成為算法課程中的一個難點和重點。

二、動態規劃算法教學設計

通過動態規劃算法教學，我們將突出訓練和培養學生基于計算機解決問題的能力，主要包括：問題分析與建模能力、遞推方程的構建能力、基于遞推方程尋找最優解的能力、遞推方程的算法設計與編程實現能力、遞推方程的算法優化與復雜度分析能力、遞推方程的算法實驗分析能力。

（一）問題分析與建模

對實際問題進行分析并建立形式化模型是基于計算機求解問題的首要任務，對學生的未來職業發展具有重要作用。發現問題比解決問題更為重要。正確建立問題的形式化模型往往意味著完成了問題求解的一半工作。問題分析與建模的關鍵在于如何選擇數學符號并運用適當的公式描述問題，即定義問題的目標和約束條件。我們以如下兩個最優化問題作為動態規劃算法的教學案例。

問題1（數組不相鄰元素的最大和問題） 在具有n個元素的數組中取出一個或多個不相鄰的元素，使其和最大。

問題2（0-1背包問題） 給定1個背包和一組物品，已知背包的容量以及每個物品的重量和價值，如何選擇裝入背包的物品，在不超過背包容量的前提下，使得所裝入背包的物品的總價值最大。

一般采用3個步驟對給定的問題進行數學建模。步驟1. 確定問題中已知量和未知量的數學符號;步驟2. 確定問題的優化目標;步驟3. 確定問題的各個約束條件。

對于問題1，用符號a表示給定數組，n表示數組所含元素個數，a[i]則表示數組中第i個元素，i在1和n之間。用大小為n的數組x表示選擇了哪些元素，x[i]=1表示選擇了元素a[i]。然后，問題1的優化目標可表示為所選擇的元素的和最大，可用max？撞ia[i]·x[i]表示。該問題存在兩個約束，一是所選擇的元素互不相鄰，可用x[i]+x[i+1]？燮1表示， 其中，i∈{1，...，n-1}，另一個是x[i]的取值只能為0或1，以表示對應第i個元素是否被選取，即x[i]∈{0，1}，i∈{1，...，n}。綜上，問題1的形式化模型可表示為：

同理，問題2的形式化模型可表示為：

其中，w[i]和v[i]分別表示物品i的重量和價值，B表示背包的容量，x[i]表示是否將物品i放入背包，即x[i]=1表示選擇了物品i，其中，i∈{1，...，n}。顯然，該問題的目標是使得所選擇的物品的價值之和最大，約束1保證了裝入背包的物品的重量之和不超過背包的容量。

在此基礎上，繼續選擇一些代表性的問題作為課堂和課后練習，以訓練和培養學生的問題分析及形式化模型構建能力。常見的動態規劃問題包括：

問題3（矩陣連乘問題）有n個矩陣進行乘法運算，如何通過給矩陣連乘時加括號，使得總的乘法次數最少。

問題4（加權區間值調度問題） 給定n個時間區間，每個時間區間包括一個開始時間和一個結束時間，還包括一個權重，如何選擇一些時間不重疊的時間區間，使得所選擇的時間區間的權重之和最大。

問題5（最大連續子序列和問題） 給定一個含n個元素的序列，請確定一個連續的子序列，使得這個子序列的和最大。

（二）遞推方程的算法設計與編程實現

考慮到遞推方程的構建是動態規劃算法教學的重點和難點，我們將該內容放到最后重點講解。在此，我們將先給出一個遞推方程，然后，基于該遞推方程講解對應問題的算法設計與編程實現，從而培養和提高學生能夠基于所構建的遞推方程設計相應的算法并能夠編程實現的能力。事實上，通過之前學習程序設計語言課程，學生已接觸過基于遞推方程的算法設計和編程訓練。我們將通過兩個簡單示例對學生進行啟發式教學。

遞推方程1（數的階乘）整數n的階乘的遞推方程為：

其中，F（i）表示整數i的階乘，i∈{1，...，n}，因此，整數n的階乘為F（n）。

遞推方程2（最大值）n個元素中的最大值的遞推方程為：

其中，M（i）表示n個元素中的前i個元素的最大值，i∈{1，...，n}，因此，n個元素中的最大值為M（n）。

遞推方程3（斐波那契數列）遞推方程為：

其中，F（i）表示斐波那契數列的第i個元素的值，i∈{1，...，n}。

選擇以上簡單示例的原因是學生已在程序設計語言課程學習中掌握了求解這些問題的算法設計方案，從而通過總結這些方案，可以得出通用的基于遞推方程設計相應算法的方法和步驟。顯然，遞推方程一般存在兩個方案，一個采用遞歸策略，另一個采用迭代策略。通過分別給出并分析遞推方程的兩種算法設計方案，可以使學生加深這兩種策略的理解。遞推方程1、2和3的遞歸和迭代算法分別用表1、表2和表3描述。

（三）遞推方程的算法優化與復雜度分析

算法時間復雜度分析與算法優化能力是需要學生掌握的重要能力。我們將分別對上述遞推方程的兩種算法進行時間復雜度分析，得出：這三個算法的迭代算法的時間復雜度均為O（n），前兩個問題的遞歸算法的時間復雜度也為O（n），而第3個問題的遞歸算法的時間復雜度為O（2n），其中n是元素個數。

需要指出的是，（1）基于遞推方程設計遞歸算法較

為直接和簡單，但由于遞歸算法的調用需要消耗大量的系統資源而導致其效率較迭代算法低很多。特別地，對于斐波那契數列問題，雖然不同的子問題的個數只有n個，但遞歸算法卻需要計算很多重復的子問題（2n個）。比如，在計算F（n）時需要計算F（n-1）和F（n-2），而在計算F（n-1）的過程中，又需要再次計算F（n-2），導致算法時間復雜度極高。通過公式推導，可得出其算法時間復雜度為指數級的。（2） 遞歸算法是一種很自然的算法，對于包含很多重復子問題的計算問題，可引導學生通過“備忘錄方法”解決，即將計算的子問題的結果暫時保存在某個數據結構（一般是數組）中。每當需要計算時，首先檢索該子問題是否已保存，若是，則直接返回結果，否則，將進行計算并保存結果。經“備忘錄方法”改進的斐波那契數列的遞歸算法如表4所示（注：定義全局數組a，初始值將a[1]，a[2]設為1，其他元素設為0）。

經過深入分析，進一步得出如下結論。雖然表4中的“備忘錄方法”可以使得遞歸算法中的子問題計算次數減少至n，但其遞歸調用次數沒有得到改變。因此，我們還可以對上述算法進一步改進，以減少遞歸調用次數，其基本思路是在調用遞歸函數時，首先檢查是否以保存小問題的解。由此，得到如表5所示的較完美的遞歸算法，雖然該算法的被調用次數仍大于n（經分析，被調用次數約為n的2倍）。

通過上述3個遞推方程的算法設計、分析與優化，我們可得出對于遞推方程的兩種動態規劃算法解決方案：一種稱為“備忘錄方法”的基于遞歸算法解決方案，其存在設計簡單但效率較低的特點;一種為基于迭代算法的解決方案，其通過存儲小問題的解逐步構造和計算大問題的解，具有高效的優點。

（四）遞推方程的構建與算法設計

采用啟發式策略與學生一起尋找上述問題1和問題2的遞推方程，并依據上述知識進行算法設計、分析和優化。構造最優化問題的遞推方程的關鍵是確定大問題的最優解與其包含的某個或某些小問題的最優解之間的關系。因此，如何用符號描述某個子問題的最優解是構建遞推方程的前提。我們將引導學生采用試探方法描述子問題的最優解及其之間的遞推方程。例如，針對問題1，我們用F（i）表示n個元素中前i個元素所構成的子問題的最優解所對應的目標值，即，如何選擇前i個元素中的某些不相鄰的數，使得這些數的和最大，該和就是F（i）的值。顯然，原問題的優化目標可表示為F（n），而F（1）顯然就是a[1]的值。對于選擇問題的常見的遞推方程的構建方法是考慮是否選擇了某個數，在此問題中，可考慮F（i）的最優解中是否包括第i個元素。分析可知：（1）如果最優解中包括第i個元素，那么將導致其相鄰的左側（即第i-1個）元素不能被選取，此時，F（i）=a[i]+F（i-2），即前i-2個元素構成的子問題的最優解加上第i個元素就是前i個元素構成的子問題的最優解;（2）反之，如果不包括第i個元素，那么其相鄰的左側的第i-1元素可以被選取，因此，前i個元素構成的子問題的最優解就等于前i-1個元素構成的子問題的最優解。由于第i個元素是否在F（i）中只存在兩種情況，因此，可得出F（i）的如下遞推方程：

在此基礎上，可設計上述遞推方程的遞歸算法和迭代算法，如表6所示。

經過分析，可知基于迭代算法的時間和空間復雜度均為O（n），而基于遞歸的算法可采用備忘錄方法進一步改進，改進后的時間復雜度仍為O（n），但效率較低。

在此基礎上，啟發學生根據優化目標的計算過程尋找對應的最優解。需要強調的是，動態規劃的迭代算法的設計采用“自下而上計算最優解的目標值、自上而下尋找最優目標對應的最優解”思想。所謂“自下而上”是指通過小問題的最優解計算大問題的最優解，而“自上而下”是指通過大問題的最優解尋找小問題的最優解。對于問題1，最終的最優解存儲在v[n]中，而根據表6的迭代算法可知，v[n]的計算是通過比較a[j]+v[j-2]和v[j-1]的大小得到的，因此，通過構建一個循環可得出最優解所包含的元素，其對應的偽代碼如表7所示，數組x中等于1的元素的下標所對應的元素就是被選擇的元素。

問題2的遞推方程的構建過程較上述問題復雜一些。我們將首先嘗試簡單的解決方案，在發現問題的基礎上，尋找正確的遞推方程。具體過程包括：首先，以F（i）表示在不超過背包容量B的前提下，選擇前i個物品中的某些物品（i？燮n）所得到的最大價值，即F（i）對應的子問題是由前i個物品及容量為B的背包構成的。然后，分析F（i）所對應的最優解中是否包括第i個物品，根據前文敘述，初步構造的F（i）遞推方程為：

但是，上述遞推方程的第3個公式是錯誤的。因為F（i-1）顯然小于F（i-1）+v[i]，這意味著在第i個物品的重量不超過背包容量時，一定會裝入背包。導致出現該錯誤的原因在于，在第i個物品的重量不超過背包容量時，如果選擇將該物品裝入背包，實際上將導致背包的可用容量變小，即第i個物品的重量將消耗背包的部分容量。但是，上述遞推方程并沒有考慮背包容量的變化。因此，為解決該問題，應該將背包的容量考慮進去。基于上述考慮，我們以符號F（i，W）表示在不超過背包容量W的前提下，選擇前i個物品中的某些物品（i？燮n）所得到的最大價值，即F（i，W）對應的子問題是由前i個物品及容量為W的背包構成的。在此基礎上，可構造F（i，W）的正確的遞推方程為：

在此基礎上，采用二維數組a存儲中間結果，可設計上述遞推方程的遞歸算法和迭代算法，如表8所示。

顯然，函數F（n，B）將返回原背包問題的最優解對應的價值。在此基礎上，可引導學生構造如表9的算法偽代碼，以獲得背包問題的最優解，其中，數組x中等于1的元素的下標所對應的元素就是被選擇的元素。

經過分析，可知基于迭代算法的時間和空間復雜度均為O（n*B）。在此基礎上，可繼續分析0-1背包問題的動態規劃算法的優缺點，并可對算法進行改進，以進一步降低算法的空間復雜度。

三、結束語

本文以培養學生問題解決能力為目標，以算法課程中的動態規劃算法教學為例，提出了一種新的教學案例設計思路，以啟發式、探究式教學方法，從易到難，逐步解決實際問題，突出訓練和培養學生的問題分析與建模能力、遞推方程的構建能力、基于遞推方程尋找最優解的能力、遞推方程的算法設計與編程實現能力、遞推方程的算法優化與復雜度分析能力、遞推方程的算法實驗分析能力。這將為以能力目標導向的算法課程教學改革提供新思路，為培養學生未來職業發展所需問題解決能力提供教學設計案例。

參考文獻：

[1]吳勁，周帆，王瑞錦，等.OBE模式下的程序設計與算法基礎課程改革探索[J].計算機教育，2019（11）：86-90.

[2]張文宇，劉鵬，陳衛衛，等.面向系統能力培養的計算機專業課程教學評價研究[J].計算機教育，2019（2）：107-111.

[3]李玲.以培養計算思維為導向的高中《算法與程序設計》教學案例設計[D].沈陽師范大學，2016.

[4]王玉柱，張玉清，季曉慧，等.新工科理念下高性能計算導論課程內容與實踐教學的探索[J].教育教學論壇，2019（25）：97-98.

[5]王曉東.計算機算法設計與分析（第4版）[M].電子工業出版社，2012.