李茜
什么是計算思維?
所謂“計算思維”,也就是計算機解決問題的思維,計算思維是人解決問題思維的一種抽象化。例如,計算機把我們?nèi)粘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é)校)