劉曉慶+陳仕鴻

摘要：算法是計算思維培養(yǎng)的核心內容之一，但目前因各種原因并未在非計算機專業(yè)的計算機教學中普及。該文將生活案例引入到算法教學中，這些生活案例分別對應動態(tài)規(guī)劃、并行計算等類別的算法問題，生動形象的展示算法的思維，解決了算法教學需要多門課程基礎的問題。

關鍵詞：算法；案例；計算思維；教學

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）21-0134-02

1 引言

隨著信息化的進展，計算機已經逐漸成為人們日常生活和工作不可缺少的工具。計算機科學將從前沿高新技術學科變成各專業(yè)、各行業(yè)均需要普及的基礎學科。算法是計算機科學基礎內容，也是計算思維培養(yǎng)的核心內容之一。計算機算法的學習，不僅可以讓學生體會到計算機的計算能力的強大性，還能夠增加學生的解決問題的技能。例如現(xiàn)今新聞、金融、語言等，幾乎每個領域都有很多的大數(shù)據，挖掘大數(shù)據的工作不僅僅屬于計算機專業(yè)的人員，相關專業(yè)的人員也要參與進來，因此掌握計算機算法，對解決類似大數(shù)據這類的大規(guī)模的、或者很復雜的問題有很大的幫助。

然而算法的學習需要有編程語言、數(shù)據結構等課程的學習基礎，算法內容生澀難懂，枯燥乏味，非計算機類的專業(yè)，特別是文科類專業(yè)的計算機教學都避開它。這導致學生無法接觸到算法的學習。本文將以生活案例的形式，避開編程語言、數(shù)據結構等專業(yè)知識，生動形象的介紹算法和算法的思維，以提高學生的學習興趣，增強學生的計算思維能力。

2 算法的含義

什么是算法呢？簡單來說，算法就是解決問題方法。算法處理的內容必然是問題所涉及的數(shù)據，算法和數(shù)據是程序設計中的核心內容。因此有這一說法：程序=算法+數(shù)據結構。

我們生活中也存在許多“算法”。舉一例來說，煎一個蛋，廚師首先鍋里滴上幾滴油，雞蛋磕破直接把蛋液倒入鍋內，用勺子稍稍往雞蛋上分散撒些食鹽，小火等蛋清蛋黃凝固，然后，翻面再煎另一面，這樣就做好了煎蛋。這個事例中，雞蛋、食鹽等食材是“數(shù)據結構”的話，廚師的烹飪過程便是“算法”。

針對同一問題，很有可能有多種不同的算法。例如，著名的數(shù)學家高斯在他小學的時候發(fā)生了一件很有名的故事，就是小學老師出于懲罰目的，出了一道算術難題：“計算1+2+3…+100=？”。作為初學算術的學生，高斯的同學都是被難住了，因為他們的解題思路是把這100個數(shù)做99次加法運算，需要大量的計算。但是高斯卻在幾秒后將答案解了出來，他所使用的方法是：對50對構造成和101的數(shù)列求和（1+100，2+99，3+98…），同時得到結果：5050。

高斯在小小年紀便能運用巧妙的解題方法，使得他的故事廣為流傳。人對解決問題與計算機在思維方法上的差異。那么，同樣針對這個問題，用計算機程序算法來完成，又應該如何實現(xiàn)呢？

設1～100的累加和放在變量s中，那么讓程序重復累加執(zhí)行：s=s+i，讓加數(shù)項從1逐步增加到100。這在計算機程序很容易實現(xiàn)。算法的流程和圖1所示。

3 排序的應用

排序在生活中是很常見的。比如人員列隊時按高矮排列；電影中的票房排行榜；字典或詞典里的字詞條排序；網上購物時多個推薦商品的前后排序等。

排序對于數(shù)據操作來說非常重要。例如：表1中有兩組1～10的數(shù)字，A組數(shù)字是無序的，而B組是有序的。那么隨機查找A組中的一個數(shù)字，查找方法是從頭到尾依次查找，平均要查找5.5次。如果是查找1～10以外的數(shù)字，例如-5，則需要查找10次后才能確認它不在表中。而針對B組中有序的數(shù)字，我們可以采用折半查找法進行查找，即不是從頭到尾依次查找，而是從中間開始查找。中點m=（s+e）/2，s和e分別為數(shù)組序號的上限和下限。例如，要查找數(shù)字4，一開始，s為1，e為10，m為5，B組中第5個數(shù)是5，沒有找到4，但是這一次查找，我們可以確定的是，中點的數(shù)字是5，我們要找的數(shù)字4小于5，所示，它不可能會在數(shù)組的后半部分，那么我們可以排隊第5～10的數(shù)字，只要在前4個數(shù)字中查找就可以了。于是第二步，在前4個數(shù)中，再次從中間找，s，e，m的值分別為1，4，2。中間的數(shù)字是2，也是沒有找到，但可以排隊第1、2個數(shù)字；接著第三步，在剩下的第3、4個數(shù)中找，s，e，m的值分別為3，4，3，查到的數(shù)字是3，也沒找到，剩下只有第4個數(shù)了；最后一步，比較第4個數(shù)，當然，就找到了我們要查找的數(shù)字4。如果要查找1～10以外的數(shù)字，則最多4次便可以確定查找失敗。因此可以確定，B組有序的數(shù)字查找快于A組。

由上述可知，數(shù)據的有序對操作的重要性。那么如何對數(shù)據進行排序呢？排序的算法有很多，如選擇排序法、冒泡法、直接插入排序法、歸并排序法、快速排序法、希爾排序法等。

4 窮舉法

窮舉法也稱為枚舉算法，其基本思想是根據題目的部分條件確定答案的大致范圍，并在此范圍內對所有可能情況逐一驗證，直到全部情況驗證完畢。若全部情況驗證后都不符合題目的全部條件，則本題無解[1]。

生活中也存在許多窮舉法的案例。例如，小明是新來的機房管理員，他要管理的是n間機房，有n把鑰匙，但他不清楚哪條鑰匙對應哪間機房，那么他便每扇門逐條鑰匙的去試，直到確認每把鑰匙對應的機房。

用窮舉法來破解密碼，也稱暴力破解法，是密碼破解技術中最基本的方法。簡單來說就是將密碼進行逐個推算直到找出真正的密碼為止。比如一個四位并且全部由數(shù)字組成其密碼共有10000種組合，也就是說最多我們會嘗試9999次才能找到真正的密碼。利用這種方法我們可以運用計算機來進行逐個推算，也就是說用我們破解任何一個密碼也都只是一個時間問題。破解過程可以用網上免費的暴力破解軟件演示給學生看。

窮舉法在求解一個較小規(guī)模的問題時，可以根據問題中的約束條件把可能的情況一一列舉出來，然后注意嘗試從中找到滿足約束條件的解。若該問題規(guī)模較大，比如破譯一個有位數(shù)很長，且有多種符號可能的密碼，其組合方法可能有萬億種組合。用普通的電腦可能會用掉幾年甚至更多的時間去計算，這樣長的時間顯然是不能接受的。因此規(guī)模太大的求解問題窮舉法并不適合，應考慮用其他效率更高的算法。