什麼是演算法——問題、計算模型與正確性

讀懂虛擬碼(reading pseudocode)

虛擬碼是我們把演算法寫給「人」看、而非寫給編譯器看的方式。它是一種折衷語言:比一段散文更精確,卻擺脫了真實程式語言的標點與繁文縟節。重點是把方法清楚地呈現出來,讓讀者能理解並推理它,而不被「少了個分號沒」這類問題纏住。如果真實程式碼是一份法律合約,虛擬碼就是抓住每個重要條款的白話摘要。

虛擬碼沒有嚴格規定,但慣例廣為共享、容易閱讀。指派用左箭頭或等號表示,如 x = x + 1(「把 x 換成它的舊值加一」)。縮排顯示哪些敘述屬於某個迴圈或 if。「for i = 1 to n」讓 i 依序取 1、2、一直到 n 重複;「while 條件」只要條件成立就重複;「if ... then ... else ...」選一個分支。陣列元素寫成 A[i],而且我們常從索引 1 開始。這裡有個完整的閱讀範例:要找最大值,設 m = A[1];接著 for i = 2 to n,若 A[i] > m 則 m = A[i];最後 return m。一行一行讀下去,你能對任何輸入追蹤 m 究竟發生了什麼,並說服自己它最終握著最大的元素。

虛擬碼刻意省略不影響方法的部分:到底用哪種資料型別存一個數、記憶體如何配置、錯誤如何回報。這是優點,不是草率——它讓點子能在語言間移植,也讓你能在不分心的情況下分析成本(數迴圈跑幾次、數比較次數)。讀虛擬碼時,目標不是像機器那樣在腦中跑它,而是理解它為何行得通:每個迴圈維持著什麼、它停下時為何正確,以及它大約做了多少工作。

MAX(A, n):m = A[1];for i = 2 to n:若 A[i] > m 則 m = A[i];return m。對 A = [4,1,7,3],變數 m 依序取 4、7,最後回傳 7。

用手追蹤變數,這就是讀虛擬碼的方法。

留意索引慣例。許多教科書的陣列從 1 開始編號;大多數真實語言從 0 開始。若忽略這點,同一段虛擬碼在翻譯時可能差一格。

又称
pseudocode虛擬碼偽代碼