劉光　裴鵬飛

（宣城市信息工程學(xué)?！⌒恰?42000）

中職計算機專業(yè)算法學(xué)習(xí)七要素

劉光裴鵬飛

（宣城市信息工程學(xué)校宣城242000）

中職計算機應(yīng)用專業(yè)學(xué)生，學(xué)習(xí)編程語言的難點是算法基礎(chǔ)差。因此如何提高中職計算機應(yīng)用專業(yè)的學(xué)生在校期間的算法學(xué)習(xí)，就是重中之重了。本文淺談了中職學(xué)生學(xué)習(xí)算法的方法、思路以及注意事項。

算法步驟編程

程序是用來在計算機上實現(xiàn)現(xiàn)實世界中的業(yè)務(wù)和娛樂活動的。為了達(dá)到這個目的，程序員們需要結(jié)合計算機的特性，用程序來表示現(xiàn)實世界中對問題的處理步驟，即處理流程。在絕大多數(shù)情況下，為了達(dá)到某個目的需要進行若干步處理。例如為了達(dá)到“計算出兩個數(shù)相加的結(jié)果”這個目的，就需要依次完成以下三個步驟，即“輸入數(shù)值”“執(zhí)行加法運算”“展示結(jié)果”。像這樣的處理步驟，就被稱為算法。

在算法中，有表示程序整體大流程的算法，也有表示程序局部小流程的算法。

一、算法是程序設(shè)計的“熟語”

學(xué)習(xí)編程語言與學(xué)習(xí)外語很像。為了將自己的想法完整地傳達(dá)給對方，僅僅死記硬背單詞和語法是不夠的，只有學(xué)會了對話中常用的熟語，才能流利地對話。學(xué)習(xí)C語言、Java和BASIC等編程語言也是如此。僅僅囫圇吞棗地把關(guān)鍵詞和語法記下來，是無法流利地和計算機對話的，可是一旦了解了算法就能將自己的想法完整地傳達(dá)給計算機了。因為算法就相當(dāng)于是程序設(shè)計中的熟語。

“令人生畏且難以掌握”“和自己無緣”，這是中職計算機專業(yè)學(xué)生對算法留下的印象。誠然，有那種無法輕松理解、難以掌握的算法，但是并不是說只有把那種由智慧超群的學(xué)者才能想出的算法全部牢記心中才能編寫程序，簡單的算法也是有的。而且學(xué)生自己也不妨去思考一些原創(chuàng)的算法。只要理清在現(xiàn)實世界解決問題的步驟，再結(jié)合計算機的特性，就一定能想出算法。思考算法也可以是一件非常有趣的事。下面，筆者將介紹中職計算機專業(yè)學(xué)生學(xué)習(xí)、思考算法時的要點。

二、要點1：算法中解決問題的步驟是明確且有限的

百度中關(guān)于“算法”的定義是這樣描述的：算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。這個定義雖然看起來晦澀，但是正確地解釋了什么是算法。

如果用通俗易懂的語言來說，算法就是“把解決問題的步驟無一遺漏地用文字或圖表示出來”。要是把這里的“用文字或圖表示”替換為“用編程語言表達(dá)”，算法就變成了程序。而且請學(xué)生注意這樣一個條件，那就是“步驟必須是明確的并且步驟數(shù)必須是有限的”。

接下來先舉一個具體的例子，請同學(xué)們想一想解決“求出12和42的最大公約數(shù)”這個問題的算法。最大公約數(shù)是指兩個整數(shù)的公共約數(shù)（能整除被除數(shù)的數(shù)）中最大的數(shù)。最大公約數(shù)的求解方法應(yīng)該在小學(xué)的數(shù)學(xué)課上學(xué)過了。把兩個數(shù)寫在一排，不斷地尋找能夠同時整除這兩個整數(shù)的除數(shù)。最后把這些除數(shù)相乘就得到了最大公約數(shù)（如圖1所示）。

用這個方法求出了6是最大公約數(shù)，結(jié)果正確。但是這些步驟能夠稱為算法嗎？答案是不能，因為步驟不夠明確。

步驟1的“用2整除12和42”和步驟2的“用3整除6 和21”，是怎么知道要這樣做的呢？尋找能夠整除的數(shù)字的方法，在這兩步中并沒有體現(xiàn)。步驟3的“沒有能同時整除2和7的除數(shù)”，又是怎么知道的呢？而且，到此為止無需后續(xù)步驟（即步驟數(shù)是有限的）的原因也是不明確的。

其實這些都是憑借人類的“直覺”判斷的。在解決問題的步驟中，有了與直覺相關(guān)的因素，就不是算法了。既然不是算法，也就不能用程序表示了。

三、要點2：計算機不靠直覺而是機械地解決問題

計算不能自發(fā)地思考。因此計算機所執(zhí)行的由程序表示的算法必須是由機械的步驟所構(gòu)成。所謂“機械的步驟”，就是不用動任何腦筋，只要按照這個步驟做就一定能完成的意思。眾多的學(xué)者和前輩程序員們已經(jīng)發(fā)明創(chuàng)造出了很多機械地解決問題的步驟，這些步驟并不依賴人類的直覺。由此所構(gòu)成的算法被稱為“典型算法”。

輾轉(zhuǎn)相除法（又稱歐幾里得算法）就是一個機械地求解最大公約數(shù)問題的算法。在輾轉(zhuǎn)相除法中分為使用除法運算和使用減法運算兩種方法。使用減法運算簡單易懂，步驟如圖2所示。用兩個數(shù)中較大的數(shù)減去較小的數(shù)（步驟），反復(fù)進行上述步驟，直到兩個數(shù)的值相等（步驟的終止）。如果最終這兩個數(shù)相同，那么這個數(shù)就是最大公約數(shù)。請學(xué)生注意以下三點：1.步驟是明確的、完全不依賴直覺的；2.步驟是機械的、不需要動腦筋就能完成的；3.使步驟終止的原因是明確的。

使用輾轉(zhuǎn)相減法求解12和42的最大公約數(shù)的程序代碼如代碼清單-1所示。本文展示的程序都是用VB編程語言編寫的（如圖3所示）。學(xué)生即使讀不懂這段程序代碼的內(nèi)容也沒有關(guān)系，這里需要學(xué)生注意的是該算法所描述的步驟是可以直接轉(zhuǎn)換成程序的。

代碼清單-1：求解12和42最大公約數(shù)的程序

四、要點3：了解并應(yīng)用典型算法

筆者建議希望從事編程工作的學(xué)生手中要有一本能作為算法典籍的書。雖然算法應(yīng)該由學(xué)生自己思考，但是如果遇到了不知道從哪里下手才好的問題，也可以利用這類典籍查查已經(jīng)發(fā)明出來的算法。

作為程序員的修養(yǎng)，表1中列出了筆者認(rèn)為最低限度應(yīng)該了解的典型算法。這些算法包括剛剛介紹過的求解最大公約數(shù)的“輾轉(zhuǎn)相除法”，判定素數(shù)的“埃拉托斯特尼篩法”（將在后面介紹），檢索數(shù)據(jù)的三種算法以及排列數(shù)據(jù)的兩種算法。記住了這些典型算法固然好，但是請學(xué)生注意絕不要丟掉自己思考算法的習(xí)慣。

表1　主要的典型算法

讓學(xué)生再試著思考一個具體問題。這次請思考一下解決“求解12和42的最小公倍數(shù)”這個問題的算法。所謂最小公倍數(shù)就是指兩個整數(shù)的公共倍數(shù)（是一個數(shù)幾倍的數(shù)）中最小的那個數(shù)。最小公倍數(shù)的求解方法學(xué)生在小學(xué)的數(shù)學(xué)課上也應(yīng)該學(xué)過了，但是很可惜求解步驟也是依賴人類的直覺的。請再思考一個適用于計算機的機械的算法。學(xué)生說不定會想“反正會有典型算法的吧，比如‘某某氏的某某法’”，然后就糾結(jié)于是否還要自己思考。

但是即使查了算法典籍之類的書，也還是找不到求解最小公倍數(shù)的算法。為什么呢？因為我們可以通過以下方法求解最小公倍數(shù)——用兩個整數(shù)的乘積除以這兩個整數(shù)的最大公約數(shù)。因此12和42的最小公倍數(shù)就是12×42÷ 6=84了。如此簡單的算法不能算作典型算法。這個例子說明先自己思考算法，再去應(yīng)用典型算法這一點很重要。

五、要點4：利用計算機的處理速度

接下來再請學(xué)生思考求解“判定91是否是素數(shù)”這一問題的算法。在用于判定素數(shù)的典型算法中，有一個被稱為“埃拉托斯特尼篩法”的算法。在學(xué)習(xí)這個算法之前，先請學(xué)生思考如果是在考試中碰到了這道題，要如何解答呢？

也許有的學(xué)生會這樣想：用91分別除以比它小的所有正整數(shù)，如果沒有找到能夠整除的數(shù)，那么91就是素數(shù)。但是，如此繁瑣的步驟可行嗎？實際上這就是正確答案。埃拉托斯特尼篩法是一種用于把某個范圍內(nèi)的所有素數(shù)都篩選出來的算法，比如篩選100以內(nèi)的所有素數(shù)，其基本思路就是用待判定的數(shù)除以比它小的所有正整數(shù)。例如要判定91是否是素數(shù)，只要分別除以2～90之間的每個數(shù)就可以了（因為1肯定能夠整除任何數(shù)，所以從2開始檢測）。這個步驟用程序表示的話，就變成了如代碼清單-2所示的代碼。Mod是用于求除法運算中余數(shù)的運算符。如果余數(shù)為0則表示可以整除，因此也就知道待判定的數(shù)不是素數(shù)了。程序執(zhí)行結(jié)果如圖4所示。

代碼清單-2：判定是否是素數(shù)的程序

無論是多么冗長繁瑣的步驟，只要明確并且機械就能構(gòu)成優(yōu)秀的算法。諸位把算法用程序表示出來讓計算機去執(zhí)行，而計算機會用令人吃驚的速度為我們執(zhí)行。為了判定91是否是素數(shù)，用91除以2～90這89個數(shù)的操作一瞬間就可以完成。在思考算法時不防時刻記著，解決問題時是可以利用計算機的處理速度的。

作為利用計算機的處理速度解決問題的另一個例子，請試著求解以下聯(lián)立方程組。題目是雞兔同籠問題：雞和兔子共計10只，把它們的腳加起來共計32只，問雞和兔子分別有多少只？設(shè)有x只雞，y只兔子，那么就可以列出如下的聯(lián)立方程組。

六、要點5：：使用編程技巧握升程序執(zhí)行速度

解決一個問題的算法未必只有一種。在考量用于解決同一個問題的多種算法的優(yōu)劣時，可以認(rèn)為轉(zhuǎn)化為程序后，執(zhí)行時間較短的算法更為優(yōu)秀。雖然計算機的處理速度快得驚人，但是當(dāng)處理的數(shù)據(jù)數(shù)值巨大或是數(shù)量繁多時還是要花費大量的時間。例如，判定91是否是素數(shù)的過程一下子就有結(jié)果了，可是要去判定999999937的話'筆者的電腦就要花費大約20分鐘之久（言外之意999999937是素數(shù)）。

有時稍微往算法中加入一些技巧，就能大幅度地縮短處理時間。在判定素數(shù)上，原先的過程是用待判定的數(shù)除以比它小的所有正整數(shù)，只要在此之上加入一些技巧，改成用待判定的數(shù)除以比它的1/2小的所有數(shù)，處理時間就會縮短。之所以改成這樣是因為沒有必要去除以比它的1/2還大的數(shù)。通過這一點改進，除法運算的處理時間就能夠縮短1/2。

在算法技巧中有個著名的技巧叫作“哨兵”。這個技巧多用在線性搜索（從若干個數(shù)據(jù)中查找目標(biāo)數(shù)據(jù)）等算法中。線性搜索的基本過程是將若干個數(shù)據(jù)從頭到尾，依次逐個比對，直到找到目標(biāo)數(shù)據(jù)。

因為雞和兔子的只數(shù)應(yīng)該都在0～10這個范圍內(nèi)，所以就試著把0～10中的每個數(shù)依次代入x和y，只要能夠找到使這兩個方程同時成立的數(shù)值也就求出了答案。利用計算機的處理速度，答案一瞬間就出來了（如代碼清單-3和圖5所示）。

代碼清單-3：求解雞兔同籠問題的程序

下面還是通過例題來思考吧。假設(shè)有100個箱子，里面分別裝有一個寫有任意數(shù)字的紙條，箱子上面標(biāo)有1～100的序號。現(xiàn)在要從這100個箱子當(dāng)中查找是否有箱子裝有寫著要查找數(shù)字的紙條。

首先看看不使用哨兵的方法。從第一個箱子開始依次檢查每個箱子中的紙條。每檢查完一個紙條，還要再檢查箱子的編號（用變量N表示），并進一步確認(rèn)編號是否已超過最后一個編號了。這個過程用流程圖表示后如圖6所示。

圖6所示的過程，雖然看起來似乎沒什么問題，但是實際上含有不必要的處理——每回都要檢查箱子的編號有沒有到100。

為了消除這種不必要的處理，于是添加了一個101號箱子，其中預(yù)先放入的紙條上寫有正要查找的數(shù)字。這種數(shù)據(jù)就被稱為“哨兵”。

通過放入哨兵，就一定能找到要找的數(shù)據(jù)了。找到要找的數(shù)據(jù)后，如果該箱子的編號還沒有到101就意味著找到了實際的數(shù)據(jù)；如果該箱子的編號是101，則意味著找到的是哨兵，而沒有找到實際的數(shù)據(jù)。使用了哨兵的流程圖如圖7所示。需要多次反復(fù)檢查的就只剩下“第N個箱子中包含要找的數(shù)字嗎？”這一點了，程序的執(zhí)行時間也因此大幅度地縮減了。

當(dāng)筆者第一次得知哨兵的作用時，對其巧妙性感到驚嘆，興奮異常。有些學(xué)生會感到“不太明白巧妙在哪里”，那么就講一個故事來解釋哨兵的概念吧。假設(shè)某個漆黑的夜晚，學(xué)生們在海岸的懸崖邊上玩一個游戲（請勿親身嘗試）。諸位站在距懸崖邊緣100米的地方，地上每隔1米就任意放1件物品。請找出這些物品中有沒有蘋果。

學(xué)生每前進1米就要撿起地上的物品，檢查是否拿到了蘋果，同時還要檢查有沒有到達(dá)懸崖的邊緣（不檢查的話就有可能掉到海里）。也就是說要對這兩種檢查反復(fù)若干次。

使用了哨兵以后，就要先把起點挪到距懸崖邊緣101米的地方，再在懸崖的邊緣放置一個蘋果。這個蘋果就是哨兵。通過放置哨兵，學(xué)生就一定能找到蘋果了。每前進1米時只需檢查撿到的物品是不是蘋果就可以了。發(fā)現(xiàn)是蘋果以后，只需站在原地再檢查一步開外的情況。如果還沒有到達(dá)懸崖邊緣，就意味著找到了真正要找的蘋果。已經(jīng)達(dá)到了懸崖邊緣，則說明現(xiàn)在手中的蘋果是哨兵，而沒有找到真正要找的蘋果。

七、要點6：找出數(shù)字間的規(guī)律

所有的信息都可以用數(shù)字表示——這是計算機的特性之一。因此為了構(gòu)造算法，經(jīng)常會利用到存在于數(shù)字間的規(guī)律。例如，請思考一下判定石頭剪刀布游戲勝負(fù)的算法。如果把石頭、剪刀、布分別用數(shù)字0、1、2表示，把玩家A做出的手勢用變量A表示，玩家B做出的手勢用變量B表示，那么變量A和B中所存儲的值就是這三個數(shù)中的某一個。請以此判斷玩家A和B的輸贏。

如果算法沒有使用任何技巧，也許就會通過枚舉表 2中所列出的 3x3=9種組合來判斷輸贏吧。把這個表格轉(zhuǎn)換成程序后就得到了代碼清單-4中的代碼?？梢钥闯鲞@是一種冗長而又枯燥的判斷方法（代碼清單-4和代碼清單-5列出的都只是程序的一部分，因此不能直接運行）。

表2　判定石頭剪刀布輸贏的表

代碼清單-4：判斷石頭剪刀布輸贏的程序（方法一）

接下來就試著在此之上稍微加入些技巧吧。請仔細(xì)觀察表2并找出數(shù)字間的一種規(guī)律，這個規(guī)律可以簡單地判定出是玩家A獲勝，玩家B獲勝，還是平局這三種結(jié)果?？赡苄枰?xí)慣一下思維上的轉(zhuǎn)變，但最終應(yīng)該都可以發(fā)現(xiàn)如下的規(guī)律：

1、如果變量A和B相等就是“平局”；

2、如果用B+1除以3得到的余數(shù)與變量A相等就是“玩家B獲勝”；

3、其余的情況都是“玩家A獲勝”。

用程序來表示這個規(guī)律就得到了如代碼清單-5所示的代碼。與沒有使用任何技巧的代碼清單-4中的代碼相比，可以發(fā)現(xiàn)處理過程簡單并且代碼短小精焊。當(dāng)然程序的執(zhí)行速度也會隨之提升。

代碼清單-5：判斷石頭剪刀布輸贏的程序（方法二）

構(gòu)造算法時需要找出數(shù)字間的規(guī)律不僅適用于數(shù)學(xué)游戲，編寫用于計算工資的應(yīng)用程序時，計算工資的規(guī)則也可以說是一種數(shù)字上的規(guī)律。如果能夠發(fā)現(xiàn)“工資=底薪+加班補貼+交通補貼-預(yù)扣稅款”這樣的規(guī)律，那么解決問題的步驟就是明確的，步驟數(shù)也是有限的，因此構(gòu)造出的算法也就是優(yōu)秀的了。

八、要點7：先在紙上考慮算法

最后介紹最為重要的一點，那就是思考算法的時候，要先在紙上用文字或圖表描述出解決問題的步驟，而不要立刻開始編寫代碼。

畫流程圖就可以方便地把算法用圖表示出來，因此請學(xué)生大量地、靈活地運用它。如果不想畫流程圖，也可以用語言把算法描述出來，寫成文書。總之先寫到紙上這一點很重要。

在紙上畫完或?qū)懲炅鞒桃院?，再把具體的數(shù)據(jù)代入以踉蹤流程的處理，確認(rèn)是否能得到預(yù)期的結(jié)果。在驗算的時候，建議使用簡單的數(shù)據(jù)，這樣即使是用心算也能得出正確的結(jié)果。例如，要確認(rèn)輾轉(zhuǎn)相除法的流程，就可以使用數(shù)值較小的數(shù)做驗算，這樣就算是用小學(xué)所學(xué)的求解步驟也能求出最大公約數(shù)。如果使用的是數(shù)值較大的數(shù)，比如123456789和987654321（最大公約數(shù)是9），那么就難跟蹤流程的處理了。

［1］Donald E.Knuth.計算機程序設(shè)計藝術(shù)卷1基本算法［M］.人民郵電出版社.2016.1.

［2］王曉華.算法的樂趣［M］.人民郵電出版社.2015.3.

［3］徐士良.數(shù)據(jù)與算法［M］.清華大學(xué)出版社.2014.12.

［4］吳偉昶（韓）.算法設(shè)計技巧與分析［M］.電子工業(yè)出版社.2010.10.

［5］Frank Nielsen.程序設(shè)計與算法［M］.清華大學(xué)出版社. 2012.1.

劉 光，男，1968年11月出生，1992年6月本科畢業(yè)於安徽師范大學(xué)；現(xiàn)任教於宣城市信息工程學(xué)校，微機教研組組長，中學(xué)一級計算機教師；多次輔導(dǎo)學(xué)生參加宣城市技能大賽獲一、二等獎，2015年輔導(dǎo)學(xué)生參加安徽省技能大賽獲計算機檢測三等獎。

裴鵬飛，男，1976年2月出生，1998年6月本科畢業(yè)於安徽科技學(xué)院；現(xiàn)任教於宣城市信息工程學(xué)校，教務(wù)處主任，中學(xué)高級計算機教師；2005年獲得宣城市第三屆“骨干教師”榮譽稱號；2007年獲得宣城市第四屆“教壇新星”榮譽稱號；2011年獲得宣城市第四屆“學(xué)科帶頭人”榮譽稱號；2012年獲得安徽省“教壇之星”榮譽稱號；2013年獲得安徽省“專業(yè)帶頭人”榮譽稱號；2016年成立安徽省“裴鵬飛名師工作坊”。）

Seven Elements of Learning to the Algorithm of Computer Specialty in Secondary Vocational Schools

Liu GuangPei Pengfei
（Xuancheng School of Information EngineeringXuancheng242000）

Vocational students majoring in computer applications,the difficulty in learning a programming language is based is poor.Therefore,how to improve vocational students majoring in computer during school learning algorithm,is a top priority.This article talking about vocational students in learning algorithm of methods,ideas and instructions.

AlgorithmStepProgramming

G633.67

A

160615-7311