算法教學(xué)問題的探討

石少儉 徐乙富

摘要：算法是計算機程序員必備的技術(shù)之一。大學(xué)的計算機算法課一般講授經(jīng)典的算法，主要是分治算法、動態(tài)規(guī)劃算法、貪心算法等。算法就是解決問題的方法。

關(guān)鍵詞：算法;分治算法;動態(tài)規(guī)劃算法;貪心算法

中圖分類號：TP319 文獻標(biāo)識碼：A

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

1引言

算法，晦澀難懂，卻又是IT領(lǐng)域最受重視的素養(yǎng)之一?？梢哉f，算法能力往往決定了一個程序員能夠走多遠。國內(nèi)外各大名企非常喜歡在面試環(huán)節(jié)考核求職者的算法編程，這也成為無數(shù)準(zhǔn)程序員們過不去的一道“坎”。

大學(xué)的計算機算法課一般講授經(jīng)典的算法，主要是分治算法、動態(tài)規(guī)劃算法、貪心算法等。對算法的定義，一般都是給出了計算機算法的特性，但作為算法的定義不太合適?？梢杂盟惴ň褪墙鉀Q問題的方法作為算法的定義。下面通過幾個例子來解釋這個定義。

2算法的一般問題

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

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

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

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

3分治法的問題

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

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

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

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

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

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

4動態(tài)規(guī)劃算法的問題

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

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

5貪心算法的例子

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

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

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

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

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

6總結(jié)

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

解題思路：該題只是要求所有能夠被5整除的整數(shù)放在表的后半段，其他的整數(shù)放在表的前半段，沒要求整數(shù)需要保持原來的順序?？梢杂每焖倥判虻乃枷雭斫鉀Q。設(shè)兩個指針，一個指針從表頭開始向后掃描，找到第一個能夠被5整除的整數(shù);一個指針從表尾開始向前掃描，找到第一個不能被5整除的整數(shù)。兩個指針對應(yīng)的整數(shù)對調(diào)。然后兩個指針繼續(xù)掃描，直到都掃描到一個整數(shù)為止。此算法的時間復(fù)雜度為0（n）和空間復(fù)雜度0（1）。

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