算法教學問題的探討

石少儉 徐乙富

摘要：算法是計算機程序員必備的技術之一。大學的計算機算法課一般講授經典的算法，主要是分治算法、動態規劃算法、貪心算法等。算法就是解決問題的方法。

關鍵詞：算法;分治算法;動態規劃算法;貪心算法

中圖分類號：TP319 文獻標識碼：A

文章編號：1009-3044（2019）27-0164-02

1引言

算法，晦澀難懂，卻又是IT領域最受重視的素養之一。可以說，算法能力往往決定了一個程序員能夠走多遠。國內外各大名企非常喜歡在面試環節考核求職者的算法編程，這也成為無數準程序員們過不去的一道“坎”。

大學的計算機算法課一般講授經典的算法，主要是分治算法、動態規劃算法、貪心算法等。對算法的定義，一般都是給出了計算機算法的特性，但作為算法的定義不太合適。可以用算法就是解決問題的方法作為算法的定義。下面通過幾個例子來解釋這個定義。

2算法的一般問題

1）分蘋果問題：有n個蘋果，兩個人分。規定：兩人依次取，每次最多取1～m個，最后取到蘋果者獲勝，給出具體的獲勝策略。

這是一個運籌學方面的例子。解題思路：從最后結果向前倒推。具體實例n=10，m=3。

一個人如果想獲勝，倒數第二次取后，需要給對方剩4個蘋果。以此倒推，結論是先取者獲勝。一般的情況下結論是整除問題。設n=a（m+1）+b，a是偶數，b=O后取者獲勝Ib≠0，先取者獲勝。a是奇數，b=0后取者獲勝Ib≠0，先取者獲勝。算法就是給出了解題的方法。

2）已知A={1，2，3，4，5，6，7，8，9，10}，求A的所有子集的元素之和。

3分治法的問題

分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規模足夠小，很容易求出其解為止。

將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

已知有n個硬幣，其中有可能有一個是偽造的，并且已知偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，利用這臺儀器，可以知道兩組硬幣的重量是否相同。問題1：用最少次數確定是否存在偽幣？問題2：如存在偽幣，用最少次數確定之。

解題思路：用分治法的思路。

問題1確定是否存在偽幣：n為偶數，把硬幣分成數量相等的2份，用儀器一次即可確定是否存在偽幣;n為奇數，把n-1個硬幣分成數量相等的2份，用儀器一次即可確定是否存在偽幣。如果存在偽幣，則結束，如果不確定，從這n-1個硬幣中取一個與原來剩余的1個硬幣，用儀器一次即可確定是否存在偽幣。所以問題1至多2次即可確定是否存在偽幣。

問題2存在偽幣：把2個硬幣的情況作為可解決的小問題，在一個小問題中，只用1次即可確定偽幣，總的比較次數為log2n。實際上這個問題中，可以通過1次比較確定偽幣的個數可以是3個，所以，最少的比較次數為log3n。

4動態規劃算法的問題

動態規劃算法基本思想也是將待求解問題分解成若干個子問題。但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。動態規劃算法的重點是找到求解問題個子問題的遞歸方程。

背包問題：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。1.物品允許拆分;2.物品不允許拆分。問應如何選擇背包中物品的總價值最大？

5貪心算法的例子

顧名思義，貪心算法總是做出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所做出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的，如果不是整體最優的，說明這個問題不適合用貪心算法來解決。

最優合并問題：給定k個排好序的序列s1，s2，……，sk，用2路合并算法將這k個序列合并成一個序列。假設所采用的2路合并算法合并2個長度分別為m和n的序列需要m+n-1次比較。試設計一個算法確定合并這個序列的最優合并順序，使所需的總比較次數最少。為了進行比較，還需要確定合并這個序列的最差合并順序，使所需的總比較次數最多。對于給定的k個待合并序列，計算最多比較次數和最少比較次數。

解題思路：用貪心算法解題，貪心策略：最少比較次數和最多比較次數分別為每次選最小（大）的序列合并，2個長度分別為m和n的序列需要m+n-1次比較。對于問題的一個實例，4個排好序的序列4，5，11，12的最多比較次數和最少比較次數分別為：

最多比較次數=（12+11-1）+（（12+11）+5-1）+（（（12+11+5）+4-1）=80

最少比較次數=（4+5-1）+（（4+5）+11-1）+（（4+5）+11）+12-1）=58

6總結

給出某高校計算機研究生初試一道題。順序表中共存放n個整數。設計一個算法調整這些整數在順序表中的位置，使得原表中所有能夠被5整除的整數放在表的后半段，其他的整數放在表的前半段。要求用盡量少的時間與空間，并給出算法的時間復雜度和空間復雜度。

解題思路：該題只是要求所有能夠被5整除的整數放在表的后半段，其他的整數放在表的前半段，沒要求整數需要保持原來的順序。可以用快速排序的思想來解決。設兩個指針，一個指針從表頭開始向后掃描，找到第一個能夠被5整除的整數;一個指針從表尾開始向前掃描，找到第一個不能被5整除的整數。兩個指針對應的整數對調。然后兩個指針繼續掃描，直到都掃描到一個整數為止。此算法的時間復雜度為0（n）和空間復雜度0（1）。

通過上面的討論，可以對算法的概念更加明確，加深學生對算法的理解，提高了學生學習算法積極性。