算法的案例教學(xué)探析

劉曉慶+陳仕鴻

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

關(guān)鍵詞：算法；案例；計(jì)算思維；教學(xué)

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）21-0134-02

1 引言

隨著信息化的進(jìn)展，計(jì)算機(jī)已經(jīng)逐漸成為人們?nèi)粘Ｉ詈凸ぷ鞑豢扇鄙俚墓ぞ?。?jì)算機(jī)科學(xué)將從前沿高新技術(shù)學(xué)科變成各專(zhuān)業(yè)、各行業(yè)均需要普及的基礎(chǔ)學(xué)科。算法是計(jì)算機(jī)科學(xué)基礎(chǔ)內(nèi)容，也是計(jì)算思維培養(yǎng)的核心內(nèi)容之一。計(jì)算機(jī)算法的學(xué)習(xí)，不僅可以讓學(xué)生體會(huì)到計(jì)算機(jī)的計(jì)算能力的強(qiáng)大性，還能夠增加學(xué)生的解決問(wèn)題的技能。例如現(xiàn)今新聞、金融、語(yǔ)言等，幾乎每個(gè)領(lǐng)域都有很多的大數(shù)據(jù)，挖掘大數(shù)據(jù)的工作不僅僅屬于計(jì)算機(jī)專(zhuān)業(yè)的人員，相關(guān)專(zhuān)業(yè)的人員也要參與進(jìn)來(lái)，因此掌握計(jì)算機(jī)算法，對(duì)解決類(lèi)似大數(shù)據(jù)這類(lèi)的大規(guī)模的、或者很復(fù)雜的問(wèn)題有很大的幫助。

然而算法的學(xué)習(xí)需要有編程語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)等課程的學(xué)習(xí)基礎(chǔ)，算法內(nèi)容生澀難懂，枯燥乏味，非計(jì)算機(jī)類(lèi)的專(zhuān)業(yè)，特別是文科類(lèi)專(zhuān)業(yè)的計(jì)算機(jī)教學(xué)都避開(kāi)它。這導(dǎo)致學(xué)生無(wú)法接觸到算法的學(xué)習(xí)。本文將以生活案例的形式，避開(kāi)編程語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)等專(zhuān)業(yè)知識(shí)，生動(dòng)形象的介紹算法和算法的思維，以提高學(xué)生的學(xué)習(xí)興趣，增強(qiáng)學(xué)生的計(jì)算思維能力。

2 算法的含義

什么是算法呢？簡(jiǎn)單來(lái)說(shuō)，算法就是解決問(wèn)題方法。算法處理的內(nèi)容必然是問(wèn)題所涉及的數(shù)據(jù)，算法和數(shù)據(jù)是程序設(shè)計(jì)中的核心內(nèi)容。因此有這一說(shuō)法：程序=算法+數(shù)據(jù)結(jié)構(gòu)。

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

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

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

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

3 排序的應(yīng)用

排序在生活中是很常見(jiàn)的。比如人員列隊(duì)時(shí)按高矮排列；電影中的票房排行榜；字典或詞典里的字詞條排序；網(wǎng)上購(gòu)物時(shí)多個(gè)推薦商品的前后排序等。

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

由上述可知，數(shù)據(jù)的有序?qū)Σ僮鞯闹匾?。那么如何?duì)數(shù)據(jù)進(jìn)行排序呢？排序的算法有很多，如選擇排序法、冒泡法、直接插入排序法、歸并排序法、快速排序法、希爾排序法等。

4 窮舉法

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

生活中也存在許多窮舉法的案例。例如，小明是新來(lái)的機(jī)房管理員，他要管理的是n間機(jī)房，有n把鑰匙，但他不清楚哪條鑰匙對(duì)應(yīng)哪間機(jī)房，那么他便每扇門(mén)逐條鑰匙的去試，直到確認(rèn)每把鑰匙對(duì)應(yīng)的機(jī)房。

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

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