第1章 啟程

計算機能且只能做兩件事，執行計算與保存計算結果，但它把這兩件事都做到了極致。常見的臺式機或筆記本電腦每秒鐘大概可以執行10億次計算，快得難以置信。想象一下，讓一個離地面1米高的球自由落體到地面上，這么短暫的時間，你的計算機已經執行了超過10億條指令。至于存儲，一臺普通計算機可以有幾千億字節的存儲空間。這是什么概念呢？打個比方，如果1字節（byte，表示一個字符所需的位數，通常是8位）的重量是1克（實際上當然不是），那么100GB的重量就相當于10000噸，這幾乎是15000頭非洲象的重量。

在人類歷史的大部分時間里，計算受限于人類大腦的計算速度以及人類雙手記錄計算結果的能力，這意味著通過計算只能解決一些最簡單的問題。即使現代計算機具備如此快的速度，它在很多問題上依然無能為力（例如，搞清楚氣候變化），但越來越多的問題已經被證明可以通過計算解決。我們希望你學習完本書之后，可以熟練地將計算思維應用到解決工作、學習、生活問題的過程中。

那么，計算思維到底指什么呢？

所有知識都可以歸結為兩類：陳述性知識和程序性知識。陳述性知識由對事實的描述組成。例如：“如果滿足y×y=x，那么x的平方根就是數值y。”這就是對事實的描述。遺憾的是，它沒有告訴我們怎樣求出平方根。

程序性知識說明“如何做”，描述的是信息演繹的過程。亞歷山大的海倫（Heron of Alexandria）第一次提出如何計算一個數的平方根。他的方法可以總結如下：

(1) 隨機選擇一個數g；

(2) 如果g×g足夠接近x，那么停止計算，將g作為答案；

(3) 否則，將g和x/g的平均數作為新數，也就是(g+x/g)/2；

(4) 使用新選擇的數——還是稱其為g——重復這個過程，直到g×g足夠接近x。

思考下面這個例子，求出25的平方根。

(1) 為g設置一個任意值，例如3；

(2) 我們確定3×3=9，沒有足夠接近25；

(3) 設置g為(3+25/3)/2=5.67;

(4) 我們確定5.67×5.67=32.15還是不夠接近25；

(5) 設置g為(5.67+25/5.67)/2=5.04；

(6) 我們確定5.04×5.04=25.4已經足夠接近25了，所以停止計算，宣布5.04就是25的平方根的一個合適的近似值。

請注意，這個方法描述的是一系列簡單的步驟，以及一個控制流，用來確定某個步驟在什么情況下得以執行。這種描述稱為算法。這個例子是一個猜測與檢驗算法。它基于這樣一個事實：我們很容易驗證一個猜測是否合理。

更加正式的定義是：算法是一個有窮指令序列，描述了這樣一種計算過程，即在給定的輸入集合中執行時，會按照一系列定義明確的狀態進行，最終產生一個輸出結果。

算法有點像菜譜：

(1) 將蛋奶糊加熱；

(2) 攪拌；

(3) 將調羹浸入蛋奶糊；

(4) 拿出調羹，用手指劃一下調羹背面；

(5) 如果留下明顯痕跡，則停止加熱并冷卻；

(6) 否則重復以上步驟。

算法包含一些測試指令，用來確定整個過程何時結束；還包含一些順序指令，用來確定指令執行的順序。有些時候，還會根據測試結果跳轉到某些指令。

那么，如何將菜譜的思想應用到機械過程中呢？一種方法就是，專門設計一臺用來計算平方根的機器。這聽起來有點奇怪，但實際上，最早用來計算的機器就是這種固定程序計算機。顧名思義，它們的設計目的就是做非常具體的事情，而且大多數情況下用來解決具體的數學問題，如計算炮彈的彈道。阿塔納索夫和貝里在1941年建造的機器算是最早的計算機之一，它可以用來解線性方程組，但其他什么都不會。阿蘭·圖靈在二戰期間設計Bombe計算機器的目的就是，專門破解納粹德國的Enigma密碼。現在，一些非常簡單的計算機還在使用這種方法。例如，四功能計算器就是一種固定程序計算機，它只能做簡單的算術，不能用作文字處理器，也不能運行視頻游戲。要改變這種機器的程序，只能更換電路。

第一臺真正的現代計算機是Manchester Mark 1。相比于那些先驅者，它有本質上的改進，即它是一臺存儲程序計算機。這種計算機存儲（并操作）一個指令序列，并具有一個可以執行序列中任何指令的元素集合。通過創建指令集結構，并將計算過程詳細劃分為一個指令序列（也就是一個程序），我們可以制造高度靈活的機器。存儲程序計算機可以對指令進行處理，就像處理數據一樣，這樣就能夠輕松修改程序，并且可以在程序的控制之下做這些事情。實際上，計算機—— — — — —的核心變成了可以執行任意合法指令集的程序（稱為解釋器），這樣計算機就能夠計算任何可以使用基本指令集描述的問題。

計算機操作的程序和數據都存儲在內存中。通常都有一個程序計數器指向內存中的特定位置，通過執行這個位置上的指令，計算過程得以開始。大多數情況下，解釋器只是簡單地按照順序執行序列中的下一條指令，但并不總是如此。在某些情況下，解釋器執行一個測試，然后根據測試結果可能跳到指令序列的其他位置繼續執行。這稱為控制流，是允許我們編寫可執行復雜任務的程序的必備條件。

再回到菜譜這個比喻，如果給定一組固定原料，那么一位優秀的廚師通過各種方式的搭配，可以做出非常多的美味佳肴。同樣地，如果給定一個小規模的固定初始元素組合，那么一位優秀的程序員也可以創造出非常多的有用程序。這就是編程如此引人入勝的原因。

要創建“菜譜”，即指令序列，我們需要能夠描述這些指令的編程語言，從而向計算機發號施令。

1936年，英國數學家阿蘭·圖靈提出了一種抽象的計算設備，后來稱為通用圖靈機。這種機器具有無限的存儲容量，即一條無限長的紙帶。可以在紙帶上面寫入0和1，以及一些非常簡單的初始指令，從而對紙帶進行移動、讀出和寫入等操作。邱奇-圖靈論題表明，如果一個函數是可計算的，那么一定可以通過對圖靈機進行編程實現這種計算。

邱奇-圖靈論題中的“如果”非常重要，并非所有問題都可以通過計算求解。舉例來說，圖靈就曾經證明，不存在這樣一個程序：對于給定的任意程序P，當且僅當P永遠運行時輸出true。這就是著名的停機問題。

邱奇-圖靈論題可以直接推導出圖靈完備性這個概念。如果一門編程語言可以模擬通用圖靈機，才可以說它是圖靈完備的。所有現代編程語言都是圖靈完備的。因此，任何可以被一門編程語言（例如Python）實現的程序，都可以被另一門編程語言（例如Java）實現。當然，有些事情用某種語言實現起來更容易，但就計算能力而言，所有語言從根本上說都是相等的。

幸運的是，程序員不必在圖靈初始指令集的基礎上構建程序，現代編程語言提供了更大、更方便的初始指令集。但是，編程基本思想的核心仍然是組裝操作序列的過程。

不管具有什么樣的初始指令集，也不管如何使用初始指令集，關于編程的最美妙的事情也同時是最糟糕的事情：計算機會嚴格按照你的指令去做。這很美妙，因為這意味著你可以使用計算機做各種各樣既有趣又有用的事情；這很糟糕，因為如果計算機沒有按照你的期望去做，那么你不能怨天尤人，只能自怨自艾。

當今世界中存在著幾百種編程語言，沒有哪一門語言是最好的（盡管你可以數出一些最差的）。術業有專攻，每種語言都有自己的用武之地。舉例來說，MATLAB是一門非常優秀的語言，適合操作向量和矩陣；C也是一門優秀的語言，適合開發控制數據網絡的程序；PHP是建立網站的理想選擇；Python則以良好的通用性著稱。

每種編程語言都有基本結構、語法、靜態語義和語義。如果用一門自然語言類比，例如英語，那么基本結構就是單詞，語法則用來描述哪些單詞放在一起可以組成通順的句子，靜態語義定義了哪些句子是有意義的，語義則定義了句子的實際含義。Python語言中的基本結構包括字面量（例如，數值3.2和字符串’abc'）和中綴操作符（例如，+和/）。

語言中的語法定義了字符和符號組成句子的正確形式。例如，英語中的Cat dog boy這個句子在語法上是錯誤的，因為英語語法不接受<名詞><名詞><名詞>這樣的句子形式。在Python中，3.2+3.2這樣的基本結構序列在語法上是良好的，但3.2 3.2這個序列則不是。

靜態語義定義了哪些語法有效的句子是有意義的。例如，英語中I are big這個句子是<代詞><系動詞><形容詞>的形式，在語法上是有效的。然而它不是有效的英語句子，因為代詞I是單數，而系動詞are是復數。這就是典型的靜態語義錯誤。在Python中，序列3.2/'abc’在語法上沒有問題（<字面量><操作符><字面量>），但會產生一個靜態語義錯誤，因為數值除以字符串是沒有意義的。

在一門語言中，語義為每個語法正確又沒有靜態語義錯誤的句子關聯一個含義。在自然語言中，句子的語義可以是模棱兩可的。例如，句子I cannot praise this student too highly可以是一種恭維，也可以是一種批評。編程語言是被精心設計過的，所以每個程序都只有一種確切的含義。

盡管語法錯誤是最常見的錯誤（特別是學習一門新的編程語言時），它的危害性卻最小。每種嚴謹的編程語言都會盡力檢查語法錯誤，絕不允許用戶運行有語法錯誤的程序。而且，大多數情況下，語言系統都會給出足夠明確的提示，指出錯誤的位置，讓用戶明確得知如何修復錯誤。

至于靜態語義錯誤，情況就有點復雜了。有些語言，比如Java，運行程序之前會做很多靜態語義檢查。但其他一些語言，比如C和Python，靜態語義檢查就比較少。Python在運行程序時確實會做相當數量的靜態語義檢查，但不會捕獲所有靜態語義錯誤。如果這些錯誤沒有被檢測出，程序的行為往往將是不可預知的。后面會看到一些這樣的例子。

通常我們并不會說程序具有語義錯誤。如果一個程序沒有語法錯誤，也沒有靜態語義錯誤，那么它就有某種含義。也就是說，它具有語義。當然，這并不是說它具有的語義就是程序員想表達的含義。如果程序的含義與程序員想表達的含義不同，那就糟糕了。

如果程序有錯誤且沒有按照你的期望運行，那會發生什么呢？

? 它可能崩潰，也就是說，停止運行并表現出某種明顯的崩潰跡象。在設計合理的計算系統中，一個程序的崩潰不會殃及整個系統。當然，某些非常流行的計算機系統并沒有這種良好的特性。幾乎所有的個人計算機用戶都有過這種體驗：某個程序出現問題時，必須重啟計算機才能解決。

? 它也可能繼續運行、運行、運行，永不停止。如果你不清楚程序完成任務大概需要多少時間，那么就很難識別這種異常情況。

? 它也可能運行結束，并產生一個可能正確也可能不正確的結果。

以上每種情況都不是我們想要的，特別是最后一種。當一個程序看上去正確運行而實際上沒有時，接下來的事情就很糟糕了。財產可能損失，患者可能受到致命劑量的放射治療，飛機可能會墜毀，等等。

程序如果沒有正確運行，就應該表現出明顯的錯誤。只要有可能，我們都應該以這種方式編寫程序。如何實現這一點將貫穿本書始終。

實際練習：計算機有時候過于咬文嚼字。如果你沒有準確告訴它應該怎么做，那么它一般都會做錯。試著實現一個兩地之間的駕駛算法，假設為某人而寫。然后想象一下，如果這個人嚴格按照你的指示來做，會發生什么情況？例如，他會收到多少違章罰單？