1.3 計算思維概述

1.3.1 計算思維的概念

2006年3月，時任美國卡內基-梅隆大學計算機科學系主任的周以真（Jeannette M.Wing）教授，在美國計算機權威期刊Communications of the ACM上給出了計算思維（computational thinking）的概念。周以真教授認為，計算思維是運用計算機科學的基礎概念進行問題求解、系統設計，以及理解人類行為等涵蓋計算機科學廣度的一系列思維活動。更進一步，周以真對計算思維的概念做了如下闡釋：“計算思維就是把一個看起來困難的問題重新闡述成一個人們知道怎樣解決的問題，如通過約簡、嵌入、轉化和仿真的方法。”

國際教育技術協會（ISTE）和計算機科學教師協會（CSTA）在2011年給計算思維下了一個可操作性的定義，即計算思維是一個問題求解的過程，該過程包括以下特點：

●擬定問題，并能夠利用計算機和其他工具的幫助來解決問題。

●要符合邏輯地組織和分析數據。

●通過抽象（如模型、仿真等）再現數據。

●通過算法思想（一系列有序的步驟），支持自動化的解決方案。

●分析可能的方案，找到最有效的方案，并且有效地應用這些方案和資源。

●推廣該問題的求解過程，并移植到更廣泛的問題中。

1.3.2 計算思維的本質

計算思維的本質是抽象（abstract）和自動化（automation）。它反映了計算的根本問題，即什么能被有效地自動執行。從操作層面上講，計算思維就是要確定合適的抽象，并選擇合適的計算方法和計算工具去解釋和執行該抽象。

計算工具利用某種方法求解問題的過程是自動執行的，即計算思維的自動化特征。計算思維建立在計算工具的能力和限制之上，由人控制機器自動執行。程序自動執行的特性使原本無法由人類完成的問題求解和系統設計成為可能。

抽象的概念在計算思維中非常重要，對計算思維中的抽象有如下解釋。

抽象是指對事物的性質、狀態及其變化過程（規律）進行符號化描述。與數學相比，計算思維中的抽象顯得更為豐富，也更為復雜。數學抽象的特點是拋開現實事物的物理、化學和生物等特性，僅保留其量的關系和空間的形式。例如，將應用題“原來有五個蘋果，吃掉兩個后還剩下幾個？”抽象表示成“5-2”。而計算思維中的抽象卻不僅僅如此。計算思維利用啟發式推理來尋求解答，就是在不確定情況下的規劃、學習和調度。它的計算結果可能是一系列的網頁，一個贏得游戲的策略，或者一個反例。計算思維的數據類型也比較復雜，譬如，堆棧是計算機學科中常見的一種抽象數據類型，這種數據類型的基本操作是入棧、出棧等，而不是簡單的加減法。算法也是一種抽象，但不能將兩個算法簡單地放在一起去實現并行算法。另外，數學抽象通常要解決一個具體的問題。而計算思維是通過抽象實現對一類問題的系統描述，以保證計算對該類問題的有效性，即需要將思維從實例計算推演到類的普適計算。

計算思維的抽象有不同的層次，即人們可以根據不同的抽象層次，進而有選擇地忽視某些細節，控制系統的復雜性。這樣，研究對象及其變換的抽象表示使問題具有可計算的復雜度。計算思維中的抽象最終要能夠一步一步機械地自動執行，為了確保機械的自動化，就需要在抽象過程中進行精確和嚴格的符號標記和建模，同時也要求計算機系統或軟件系統生產廠家能夠向用戶提供各種不同抽象層次之間的翻譯工具。作為抽象的較高層次，可以使用模型化方法，建立抽象水平較高的模型，然后依據抽象模型實現計算機表示和處理。

下面通過三個計算思維示例了解計算思維的本質。

1.七橋問題

哥尼斯堡城地處東普魯士，位于普雷格爾河的兩岸及河中心的兩個島上，城市各部分由七座橋與兩岸連接起來。多年來，當地居民總有一個愿望：從家里出去散步，能否通過每座橋恰好一次，再返回家中？但是任何人也沒有找到這樣一條理想的路徑。

1736年，瑞士數學家歐拉（見圖1-2）對此問題進行了研究，他把陸地抽象為一個點，用連接兩個點的線段表示橋梁，將該問題抽象成點、線連接的數學問題（見圖1-3），并給出結論：人們的愿望無法實現。同時，他發表了“一筆畫定理”：一個圖形要能一筆畫完成必須符合兩個條件，即圖形是封閉連通的和圖形中的奇點（與奇數條邊相連的點）個數為0或2。歐拉的研究開創了數學上的新分支——拓撲學。很顯然，七橋問題的解決過程體現了計算思維的抽象本質。

2.取咖啡問題

在咖啡店，物品的擺放如圖1-4所示，從左至右分別是杯蓋、杯子、咖啡、糖、牛奶、咖啡壺。現在，想取一杯咖啡，行動軌跡應該是：先取杯子，然后加入咖啡、糖、牛奶、水，再返回來蓋上杯蓋。但這條路徑很低效，需要折返取杯蓋。如何提高效率呢？很顯然，可以將杯蓋放到水壺的右側，構成流水線。這似乎不太符合邏輯，但從工程的角度來說，將杯蓋放到水壺的右側是最高效的方法。很顯然，這體現了計算思維的自動化本質。

3.求 n 的階乘

任何大于等于1的自然數n的階乘表示方法可以有兩種：

第一種：

第二種：

可以看出，在不同的思維下，階乘有不同的解題（抽象）方式。不同的抽象方法和自動求解思路表明計算思維的靈活性和多樣性。

1.3.3 計算思維的特征

計算思維是人類科學思維中以抽象和自動化，或者說以形式化、程序化和機械化為特征的思維形式。

1.計算思維是人的思維，而非機器的思維

計算思維是人類求解問題的一條途徑，是人的思維，而非機器的思維。AlphaGo戰勝了多名圍棋大師，并不是機器具有思維，而是人類賦予了機器“人的思維”，從而實現了“只有想不到，沒有做不到”的境界。所以，計算思維的重點是如何用計算機幫助人類解決問題，而非要像計算機那樣枯燥地思考問題。

2.計算思維是能力，而非技能

計算思維是分析并解決問題的能力，而非刻板的操作技能，因此重點是培養分析問題和解決問題的能力，而不是學習某一個軟件的使用。

3.計算思維是概念化的思考方式，而非程序化的

計算機科學不是計算機編程。像計算機科學家那樣去思維意味著不僅要進行計算機編程，還要在抽象的多個層次上思考。所以，計算思維的重點是算法設計，即解決問題的方法和步驟，而不涉及具體的編程。

4.計算思維是一種思想，而非人造品

目前，軟件、硬件等人造物以物理形式呈現在我們周圍，并時時刻刻影響我們的生活。但計算思維體現的是我們用以解決問題、管理日常生活、與他人交流和互動的一種與計算有關的思想。當計算思維真正融入人類活動的整體，不再表現為一種顯式哲學的時候，就成為人類一種特有的思想。

1.3.4 身邊的計算思維

計算思維可以被看作一種高效解決問題的思考方式。人們在日常生活中的很多做法其實都和計算思維不謀而合，也可以說計算思維從生活中吸收了很多有用的思想和方法。下面舉例介紹生活中的計算思維。

最短路徑問題：如果你是郵遞員，會怎樣投遞物品呢？通常郵遞員不會盲目地挨家挨戶去投遞，更不會隨意投遞，一般會規劃好自己的投遞路線，按照最短路徑進行優化。

分類：如果要在一堆文件中找一份重要資料，應該怎么做？一般不會隨機拿一份，找不到放回，再隨機拿一份找，更不會一份文件一份文件地找。通常會把文件按照內容先分類，然后再在與資料相關的文件類中找。

背包問題：用卡車運送物品到外地，能帶走的物品有4種，每種物品重量不同，價值不同，由于卡車能運送的重量有限，不能把所有的物品運走，如何處理才能讓卡車運走的物品價值最高？可以把所有物品的組合列出來，如果該組合卡車能裝下，并且價值最高，就選擇這種物品運送方案。

查找：如果要在英漢詞典中查找一個英文單詞，讀者不會從第一頁開始逐頁翻看，而是會根據字典是有序排列的事實，快速地定位單詞詞條。

回溯：人們在路上遺失了東西之后，會沿原路邊往回走邊尋找。或者在一個岔路口，人們會選擇沿一條路走下去，如果最后發現此路不通就會原路返回，到岔路口選擇另外一條路繼續尋找。

緩沖：假如將學生用的教科書視為數據，將上課視為對數據的處理，那么學生的書包就可以被視為緩沖存儲。學生隨身攜帶所有的教科書是不可能的，因此每天只能把當天要用的教科書放入書包，第二天再換入新的教科書。

并發：比如要完成三門功課的作業，在寫作業的時候，可以交替完成，即寫A作業，累了的時候就換B作業或C作業。從宏觀上看，A、B、C作業是并發完成的，即一天“同時”完成了三門功課的作業，從微觀上看，在同一時間點上，A、B、C作業又是各自獨立地交替完成的。

博弈：經濟學上有個“海盜分金”模型，5個海盜搶得100枚金幣，他們按抽簽的順序依次提出方案，首先由1號提出分配方案，然后5人投票表決，超過半數同意方案才被通過，否則提出方案的人將被扔入大海喂鯊魚，依此類推。在“海盜分金”模型中，“分配者”想讓自己的方案獲得通過的關鍵是事先考慮清楚“挑戰者”的分配方案是什么，并用最小代價獲取最大收益，拉攏“挑戰者”分配方案中最不得意的人。“海盜分金”其實是一個高度簡化和抽象的模型，體現了博弈的思想。

上述例子都涉及計算思維的應用。同樣，在利用計算機解決問題的時候，應用計算思維的方法去設計求解，會提高問題求解的質量與效率。