### 1.2.2 計算思維的具體例子 基于計算機的能力和局限，計算機科學家提出了很多關于計算的思想和方法，從而建立 了利用計算機解決問題的一整套思維工具。下面我們簡要介紹計算機科學家在計算的不同階 段所采用的常見思想和方法。 問題表示 用計算機解決問題，首先要建立問題的計算機表示。問題表示與問題求解是緊密相關的， 如果問題的表示合適，那么問題的解法就可能如水到渠成一般容易得到，否則可能如逆水行 舟一般難以得到解法。 抽象（abstraction）是用于問題表示的重要思維工具。例如，小學生經過學習都知道將 應用題“原來有五個蘋果，吃掉兩個后還剩幾個”抽象表示成“5 - 2”，這里顯然只抽取了 問題中的數量特性，完全忽略了蘋果的顏色或吃法等不相關特性。一般意義上的抽象，就是 指這種忽略研究對象的具體的或無關的特性，而抽取其一般的或相關的特性。計算機科學中 的抽象包括數據抽象和控制抽象，簡言之就是將現實世界中的各種數量關系、空間關系、邏 輯關系和處理過程等表示成計算機世界中的數據結構（數值、字符串、列表、堆棧、樹等） 和控制結構（基本指令、順序執行、分支、循環、模塊等），或者說建立實際問題的計算模型。 另外，抽象還用于在不改變意義的前提下隱去或減少過多的具體細節，以便每次只關注少數 幾個特性，從而有利于理解和處理復雜系統。顯然，通過抽象還能發現一些看似不同的問題 的共性，從而建立相同的計算模型。總之，抽象是計算機科學中廣泛使用的思維方式，只要 有可能并且合適，程序員就應當使用抽象。 可以在不同層次上對數據和控制進行抽象，不同抽象級對問題進行不同顆粒度或詳細程 度的描述。我們經常在較低抽象級之上再建立一個較高的抽象級，以便隱藏低抽象級的復雜 細節，提供更簡單的求解方法。例如，對計算本身的理解就可以形成“電子電路?門邏輯? 二進制?機器語言指令?高級語言程序”這樣一個由低到高的抽象層次，我們之所以在高級 語言程序這個層次上學習計算，當然是為了隱藏那些低抽象級的繁瑣細節。又如，在互聯網 上發送一封電子郵件實際上要經過不同抽象級的多層網絡協議才得以實現，寫郵件的人肯定 不希望先掌握網絡低層知識才能發送郵件。再如，我們經常在現有軟件系統之上搭建新的軟 件層，目的是隱藏低層系統的觀點或功能，提供更便于理解或使用的新觀點或新功能。 算法設計 問題得到表示之后，接下來的關鍵是找到問題的解法——算法。算法設計是計算思維大 顯身手的領域，計算機科學家采用多種思維方式和方法來發現有效的算法。例如，利用分治 法的思想找到了高效的排序算法，利用遞歸思想輕松地解決了 Hanoi 塔問題，利用貪心法尋 求復雜路網中的最短路徑，利用動態規劃方法構造決策樹，等等。前面說過，計算機在各個 領域中的成功應用，都有賴于高效算法的發現。而為了找到高效算法，又依賴于各種算法設 計方法的巧妙運用。 對于大型問題和復雜系統，很難得到直接的解法，這時計算機科學家會設法將原問題重 新表述，降低問題難度，常用的方法包括分解、化簡、轉換、嵌入、模擬等。如果一個問題 過于復雜難以得到精確解法，或者根本就不存在精確解法，計算機科學家不介意退而求其次， 尋求能得到近似解的解法，通過犧牲精確性來換取有效性和可行性，盡管這樣做的結果可能 導致問題解是不完全的，或者結果中混有錯誤。例如搜索引擎，它們一方面不可能搜出與用 戶搜索關鍵詞相關的所有網頁，另一方面還可能搜出與用戶搜索關鍵詞不相關的網頁。作為 對比，很難想象數學家在解決數學問題時會尋求什么近似證明或對錯參雜的解。 編程技術 找到了解決問題的算法，接下來就要用編程語言來實現算法，這個領域同樣是各種思想 和方法的寶庫。例如類型化與類型檢查方法將待處理的數據劃分為不同的數據類型，編譯器 或解釋器借此可以發現很多編程錯誤，這和自然科學中的量綱分析的思想是一致的。又如結 構化編程方法使用規范的控制流程來組織程序的處理步驟，形成層次清晰、邊界分明的結構 化構造，每個構造具有單一的入口和出口，從而使程序易于理解、排錯、維護和驗證正確性。 又如模塊化編程方法采取從全局到局部的自頂向下設計方法，將復雜程序分解成許多較小的 模塊，解決了所有底層模塊后，將模塊組裝起來即構成最終程序。又如面向對象編程方法以 數據和操作融為一體的對象為基本單位來描述復雜系統，通過對象之間的相互協作和交互實 現系統的功能。還有，程序設計不能只關注程序的正確性和執行效率，還要考慮良好的編碼 風格（包括變量命名、注釋、代碼縮進等提高程序易讀性的要素）和程序美學問題。 編程范型（programming paradigm）是指計算機編程的總體風格，不同范型對編程要素（如數據、語句、函數等）有不同的概念，計算的流程控制也是不同的。早期的命令式（或 稱過程式）語言催生了過程式（procedural）范型，即一步一步地描述解決問題的過程。后來 發明了面向對象語言，數據和操作數據的方法融為一體（對象），對象間進行交互而實現系統 功能，這就形成了面向對象（object-oriented）范型。邏輯式語言、函數式語言的發明催生了 聲明式（declarative）范型——只告訴計算機“做什么”，而不告訴計算機“怎么做”。有的語 言只支持一種特定范型，有的語言則支持多種范型。本書采用的 Python 就是支持多種編程范 型的語言，Python 程序可以是純過程式的，也可以是面向對象的，甚至可以是函數式的。 可計算性與算法復雜性 在用計算機解決問題時，不僅要找出正確的解法，還要考慮解法的復雜度。這和數學思維不同，因為數學家可以滿足于找到正確的解法，決不會因為該解法過于復雜而拋棄不用。 但對計算機來說，如果一個解法太復雜，導致計算機要耗費幾年幾十年乃至更久才能算出結 果，那么這種“解法”只能拋棄，問題等于沒有解決。有時即使一個問題已經有了可行的算 法，計算機科學家仍然會去尋求更有效的算法。 有些問題是可解的但算法復雜度太高，而另一些問題則根本不可解，不存在任何算法過 程。計算機科學的根本任務可以說是從本質上研究問題的可計算性。例如，科幻電影里的計 算機似乎都像人類一樣擁有智能，從計算的本質來說，這意味著人類智能能夠用算法過程描 述出來。雖然現代計算機已經能夠從事定理證明、自主學習、自動推理等“智能”活動，但 是人類做這些事情并非采用一步一步的算法過程，像阿基米德大叫“尤里卡”那樣的智能活 動至少目前的計算機是沒有可能做到的。 雖然很多問題對于計算機來說難度太高甚至是不可能的任務，但計算思維具有靈活、變 通、實用的特點，對這樣的問題可以去尋求不那么嚴格但現實可行的實用解法。例如，計算 機所做的一切都是由確定性的程序決定的，以同樣的輸入執行程序必然得到同樣的結果，因 此不可能實現真正的“隨機性”。但這并不妨礙我們利用確定性的“偽隨機數”生成函數來模 擬現實世界的不確定性、隨機性。 又如，當計算機有限的內存無法容納復雜問題中的海量數據時，這個問題是否就不可解 了呢？當然不是，計算機科學家設計出了緩沖方法來分批處理數據。當許多用戶共享并競爭 某些系統資源時，計算機科學家又利用同步、并發控制等技術來避免競態和僵局。