算法編程在計算思維能力培養(yǎng)中的應(yīng)用

李茜

什么是計算思維？

所謂“計算思維”，也就是計算機解決問題的思維，計算思維是人解決問題思維的一種抽象化。例如，計算機把我們?nèi)粘Ｉ钪行枰罁?jù)條件判斷進而做出決定的問題抽象為分支結(jié)構(gòu)，將需要重復(fù)做的事情抽象為循環(huán)結(jié)構(gòu)，這樣一來，許多現(xiàn)實生活中我們所遇到的問題，或者種類相似的問題，都可以通過計算思維的轉(zhuǎn)換，抽象為計算機語言所編寫出來的程序。

為什么要學(xué)習(xí)算法？

算法是計算機解決特定問題的確定的、有限的步驟的集合，無論學(xué)習(xí)哪門計算機語言，學(xué)習(xí)算法都是非常重要的，不同的算法體現(xiàn)了計算機思維的不同呈現(xiàn)方式，學(xué)習(xí)算法，對于學(xué)生理解計算思維，應(yīng)用計算思維解決問題都是非常有幫助的。

算法舉例

遞歸算法 遞歸算法是常用的編程技術(shù)，其基本思想就是“自己調(diào)用自己”，它可以用簡單的程序來解決某些復(fù)雜的計算問題。在程序設(shè)計中，應(yīng)用遞歸算法的關(guān)鍵即是找到遞歸的規(guī)律和遞歸終止的條件。

案例：數(shù)字黑洞153

任意取一個是3的倍數(shù)的自然數(shù)。求出這個數(shù)各個數(shù)位上數(shù)字的立方和，得到一個新數(shù)；然后再求出這個新數(shù)各個數(shù)位上數(shù)字的立方和，又得到一個新數(shù)，如此重復(fù)運算下去，最后一定會掉入數(shù)字黑洞153之中。例如：69是3的倍數(shù)，63+93=945，93+43+53=918，93+13+83=1242，13+23+43+23=81，83+13= 513，53+13+33=153。

接下來，我們來看，如何通過算法描述來說明計算機解決問題的思維方式。

算法如下：一是提示用戶輸入一個3的倍數(shù)。二是求這個數(shù)各個數(shù)位的立方和。三是判斷結(jié)果是否等于153？四是如果不等于153則重復(fù)2、3兩步，如果等于153，則證明其掉入黑洞153，程序結(jié)束。

這個過程和我們?nèi)四X判斷這個問題的過程非常相似，而以上描述的算法就是一個從人的思維到計算思維轉(zhuǎn)換的過程。

枚舉算法 枚舉算法是我們在日常中常用一個算法，它的核心思想就是嘗試所有的可能。它的本質(zhì)就是從所有候選答案中去搜索正確的解，使用該算法需要滿足兩個條件：一是可預(yù)先確定候選答案的數(shù)量。二是候選答案的范圍是已知的、明確的。

案例：韓信點兵

秦朝末年，楚漢相爭。一次，韓信率1500名將士與楚王大將李鋒交戰(zhàn)后返回大本營。當(dāng)行至一山坡，忽有后軍來報，說有楚軍騎兵追來。韓信兵馬到坡頂，見來敵不足500騎，便急速點兵迎敵。他命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士，敵人不足500，我們居高臨下，以眾擊寡，一定能打敗敵人。

這是一個典型的枚舉算法的案例。從對韓信點兵這個問題分析得出：

枚舉的范圍是：1000—1500。

條件是：一是士兵數(shù)除3的余數(shù)為2；二是士兵數(shù)除5的余數(shù)為3；三是士兵數(shù)除7的余數(shù)為2。三個條件必須同時滿足。

算法如下：一是列舉1000—1500范圍內(nèi)的所有數(shù)字。二是按照“兵除3的余數(shù)為2；兵除5的余數(shù)為3；兵除7的余數(shù)為2”的條件逐一判斷。三是找到符合條件的數(shù)字立即停止判斷。

枚舉法的應(yīng)用非常廣泛，很多數(shù)學(xué)問題都可以用枚舉法來實現(xiàn)，例如雞兔同籠等等。

邏輯推理 在計算思維的世界里，除了算術(shù)運算、關(guān)系運算，還有一種運算叫“邏輯運算”，邏輯運算符有三種：非、與、或。計算機在處理問題時，除了要處理和運算有關(guān)的問題，還要處理邏輯判斷類的問題。

案例：誰是殺手

日本某地發(fā)生了一起謀殺案，被控制的四個犯罪嫌疑人分別說了如下供詞：

甲說：“不是我?！币艺f：“是丙?！北f：“是丁?！倍≌f：“丙在胡說。”已知三個人說了真話，一個人說的是假話?，F(xiàn)在根據(jù)這些信息，請你找出到底誰是兇手。

現(xiàn)在，我們需要編寫一個程序，讓程序幫我們判斷出“誰是兇手”。那么，我們需要將問題轉(zhuǎn)化為計算機可以理解的形式。

首先，我們將嫌犯的陳述，對應(yīng)為下方的邏輯表達式：

已知條件：甲說：“不是我?！北磉_式：<殺手=1>不成立。

已知條件：乙說：“是丙?！北磉_式：<殺手=3>。

已知條件：丙說：“是丁。”表達式：<殺手=4>。

已知條件：丁說：“丙在胡說?！北磉_式：<殺手=4>不成立。

接下來，是如何表達四個人中有三個人說了真話，也就是以上的四個表達式返回值之和等于3。

算法如下：一是假設(shè)兇手=1。二是判斷上方表達式中4個表達式的和是否為3。三是如果成立，則找到兇手，說出兇手。四是如果不成立，則兇手值加1，重復(fù)步驟2、3。五是當(dāng)兇手=4，四個嫌犯都判斷完畢，兇手就在其中。

遇到類似的問題，我們需要做的，就是把已知條件和條件之間的關(guān)系表達清楚，其他的問題就交給計算機來處理。

筆者的話

生活中的很多問題都可以通過計算思維抽象成為具體的形式：如不斷變化的數(shù)值可以抽象為變量；能否滿足條件可以抽象為邏輯表達式；對事物的判斷可以抽象為分支結(jié)構(gòu)，反復(fù)做的事情可以抽象為循環(huán)結(jié)構(gòu)等等。擁有較強計算思維能力的學(xué)生，具備更強大的解決問題的能力，當(dāng)在生活中遇到一些難以解決的問題時，往往會想到借助計算機編寫程序的方式來找到問題的答案。本文中筆者以算法編程為背景，通過幾個編程案例，呈現(xiàn)了分析問題→思維轉(zhuǎn)換→程序?qū)崿F(xiàn)的過程，體會現(xiàn)實生活中的問題如何抽象并轉(zhuǎn)換成為能夠為計算機理解的應(yīng)用程序的過程，進而感受計算思維的魅力。

（作者單位：首都師范大學(xué)附屬育新學(xué)校）