中職計算機專業算法學習七要素

劉光　裴鵬飛

（宣城市信息工程學校　宣城　242000）

中職計算機專業算法學習七要素

劉光裴鵬飛

（宣城市信息工程學校宣城242000）

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

算法步驟編程

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

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

一、算法是程序設計的“熟語”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、要點3：了解并應用典型算法

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

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

表1　主要的典型算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面還是通過例題來思考吧。假設有100個箱子，里面分別裝有一個寫有任意數字的紙條，箱子上面標有1～100的序號。現在要從這100個箱子當中查找是否有箱子裝有寫著要查找數字的紙條。

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

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

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

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

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

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

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

七、要點6：找出數字間的規律

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

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

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

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

接下來就試著在此之上稍微加入些技巧吧。請仔細觀察表2并找出數字間的一種規律，這個規律可以簡單地判定出是玩家A獲勝，玩家B獲勝，還是平局這三種結果。可能需要習慣一下思維上的轉變，但最終應該都可以發現如下的規律：

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

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

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

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

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

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

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

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

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

在紙上畫完或寫完流程以后，再把具體的數據代入以踉蹤流程的處理，確認是否能得到預期的結果。在驗算的時候，建議使用簡單的數據，這樣即使是用心算也能得出正確的結果。例如，要確認輾轉相除法的流程，就可以使用數值較小的數做驗算，這樣就算是用小學所學的求解步驟也能求出最大公約數。如果使用的是數值較大的數，比如123456789和987654321（最大公約數是9），那么就難跟蹤流程的處理了。

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

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

［3］徐士良.數據與算法［M］.清華大學出版社.2014.12.

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

［5］Frank Nielsen.程序設計與算法［M］.清華大學出版社. 2012.1.

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

裴鵬飛，男，1976年2月出生，1998年6月本科畢業於安徽科技學院；現任教於宣城市信息工程學校，教務處主任，中學高級計算機教師；2005年獲得宣城市第三屆“骨干教師”榮譽稱號；2007年獲得宣城市第四屆“教壇新星”榮譽稱號；2011年獲得宣城市第四屆“學科帶頭人”榮譽稱號；2012年獲得安徽省“教壇之星”榮譽稱號；2013年獲得安徽省“專業帶頭人”榮譽稱號；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