《趣題學算法》—第0章0.3節算法的僞代碼描述

本節書摘來自異步社群《趣題學算法》一書中的第0章0.3節算法的僞代碼描述，作者徐子珊,更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

0.3　算法的僞代碼描述

上一節最後一段使用自然語言（漢語）描述了解決“計算逆序數”問題的算法。即如何将輸入資料轉換為輸出資料的過程。在需要解決的問題很簡單的情況下（例如“計算逆序數”問題），用自然語言描述解決這個問題的算法是不錯的選擇。但是，自然語言有一個重要特色——語義二岐性。語義二岐性在文學藝術方面有着非凡的作用：正話反說、雙關語……。由此引起的誤會、感情沖突……帶給我們多少故事、小說、戲劇……。但是，在算法描述方面，語義二岐性卻是我們必須避免的。因為，如果對資料的某一處理操作的表述上有二岐性，會使不同的讀者做出不同的操作。對同一輸入，兩個貌似相同的算法的運作，将可能得出不同的結果。這樣的情況對問題的解決可能是災難性的。是以，自然語言不是最好的描述算法的工具。

在計算機上，算法過程是由一系列有序的基本操作描述的。不同的計算機系統，同樣的操作，指令的表達形式不必相同。本書并不針對特殊的計算機平台描述解決計算問題的算法，我們需要一個通用的、簡潔的形式描述算法，并且能友善地轉換成各種計算機系統上特殊表達形式（計算機程式設計語言）所描述的程式。描述算法的通用工具之一叫僞代碼。例如，解決上述問題資料輸入/輸出的僞代碼過程可描述如下。

其中，第8行調用計算序列a[1..n]的逆序數過程get-the-inversion(a)是解決一個案例的關鍵，其僞代碼過程如下。

算法0-1　解決“計算逆序數”問題的一個案例的算法僞代碼過程

僞代碼是一種有着類似于程式設計語言的嚴格外部文法（用if-then-else表示分支結構，用for-do、while-do或repeat-until表示循環結構），且有着内部寬松的數學語言表述方式的代碼表示方法。它既沒有二歧性的缺陷（嚴格的外部文法），又能用高度抽象的數學語言簡練地描述操作細節。

本書所使用的僞代碼書寫規則如下。

① 用分層縮進來訓示塊結構。例如，從第3行開始的for循環的循環體由第4～6行的3行組成，分層縮進風格也應用于if-then-else語句，如第5～6行的if-then語句。

② 對for循環，循環計數器在退出循環後仍然保留。是以，一個for循環剛結束時，循環計數器的值首次超過for循環上界。例如在算法0-1中，當第3～6行的for循環結束時，j = n+1；而第4～6行的for循環結束時，i=1−1=0。

③ 符号“ ▷”表示本行的注釋部分。例如，算法0-1的開頭對參數a的意義進行了解釋，第5行說明檢測到一個逆序（ia[j]），而第6行說明将此逆序累加到逆序數count（count自增1）。

④ 多重指派形式i ← j← e對變量i和j同賦予表達式e的值；它應當被了解為在指派操作j ← e之後緊接着指派操作i ← j。

⑤ 變量（如i，j，及count）都局部于給定的過程。除非特别需求，我們将避免使用全局變量。

⑥ 數組元素是通過數組名後跟括在方括号内的下标來通路。例如，a[i]表示數組a的第i個元素。記号“…”用來表示數組中取值的範圍。是以，a[1…i]表示數組a的取值由a[1]到a[i]，i個元素構成的子序列。

⑦ 組合資料通常組織在對象中，其中組合了若幹個屬性。用域名[對象名]的形式來通路一個具體的域。例如，我們把一個數組a當成一個對象，它具有說明其所包含的元素個數的屬性length。為通路數組a的元素個數，我們寫length[a]。

表示數組或對象的變量被當成一個指向表示數組或對象的指針。對一個對象x的所有域f，設y ← x将導緻f[y] = f[x]。此外，若設f[x]← 3，則不僅有f[x] = 3，且有f[y] = 3。換句話說，指派y ← x後，x和y指向同一個對象。

有時，一個指針不指向任何對象，此時，我們給它一個特殊的值nil。

⑧ 過程的參數是按值傳遞的：被調用的過程以複制的方式接收參數，若對參數指派，則主調過程不能看到這一變化。

⑨ 布爾運算符“and”和“or”都是短回路的。也就是說，當我們計算表達式“x and y”時，先計算x。若x為false，則整個表達式不可能為true，是以我們不再計算y。另一方面，若x為true，我們必須計算y以确定整個表達式的值。相仿地，在表達式“x or y”中，我們計算表達式y當且僅當x為false。短回路操作符使得我們能夠寫出諸如“x ≠ nil and f [x] = y”這樣的布爾表達式而不必擔心當x為nil時去計算f [x]。