[技術雜談] 如何撰寫虛擬碼 (Pseudocode)

前言

直接使用程式碼來呈現 (資料結構和) 演算法，往往需注意過多細節，像是型別、陣列長度、存取權限、記憶體管理等，而且程式語言很多，單一語言能滿足的客群相對小。

有許多演算法的書籍會轉而使用虛擬碼 (pseudocode) 來表示，由讀者自行將其轉為可用的程式碼。虛擬碼不需在意程式語言的細節，敘述上比較簡潔。

在虛擬碼和程式碼之間的轉換，需要一段時間的學習才能上手。但學過一段時間的程式設計後，反而會覺得程式碼比虛擬碼簡單，因為編譯器或直譯器會協助我們找出程式碼中的錯誤，而虛擬碼沒有固定的格式，只能由人工閱讀來確認是否正確。

有時候我們需要撰寫虛擬碼而非程式碼，像是學校考試、學術報告、技術文件等；因此，除了能讀懂別人寫的虛擬碼，最好還是要能自己寫虛擬碼。

虛擬碼面對的情境

虛擬碼的風格差異很大，有些會用數學表示法 (mathematical notation)，有些會用口語敘述，有些會接近真正的程式碼。沒有那一種風格是最好的，要看當下的需求來決定。

學習虛擬碼就像學習程式語言，只要針對不同情境撰寫相對應的虛擬碼，再將其組合起來即可。一般來說，程式設計常見的情境如下：

• 宣告 (declaration)
• 指派 (assignment)
• 代數運算 (algebraic operations)
• 選擇 (selection)
• 迭代 (iteration)
• 函式 (function)
• 類別 (class)
• 陣列 (array)
• 集合 (collections)

我們只要針對這些情境撰寫相對應的虛擬碼，大概就可以抓到虛擬碼的寫法。學習其他人的虛擬碼也是用相同的要訣去拆解各種不同的情境即可。

[Update on 2020/02/26] 參考 Fortran 的語法略為修改虛擬碼。

[Update on 2018/12/23] 對本文進行小幅度修改。

[Update on 2018/04/25] 略為修改虛擬碼寫法，希望能更加直觀。

注意事項

既然要寫虛擬碼，就不能直接寫出程式碼，頂多只能風格上接近程式碼。以考試的情境來說，該寫虛擬碼卻直接寫程式碼會讓考官覺得考生沒有抓到演算法的抽象思維，無法跳脫特定程式語言的實作方式；所以平常最好還是練習一下。

筆者以為，比較接近程式碼的虛擬碼會比較好寫，建議不熟虛擬碼的讀者可由這個方向下手；如果仔細觀察本文，也會發現這個現象。

由於虛擬碼沒有嚴謹的格式，不會有什麼虛擬碼的編譯器或直譯器，僅能由人工檢閱，一開始時其實不太好上手。如果沒辦法直接寫虛擬碼，可以先寫程式碼，再將其手動轉為虛擬碼，來回對照幾次後，慢慢就會抓到寫虛擬碼的要訣。

一開始練習時，可以先從很簡單的演算法開始，像是求最大公因數、求 Fibonacci 數、找質數、基本的排序等，慢慢再寫更長的虛擬碼。通常練習演算法會搭配 C、C++、Java 三者之一，一開始覺得太難可暫時先用 Python 來練習演算法。

筆者在這裡展示一種看似口語但偏實際程式碼的虛擬碼，參考 Ruby 和 Lua 等語言的語法轉換而來，這套方法並不是什麼標準，僅供參考。閱讀本文的重點並不是記憶這套虛擬碼，許多教科書有更經典的虛擬碼寫法，而是藉由觀察他人的虛擬碼來建立自己習慣的書寫方式並熟練之。

宣告 (Declaration)

宣告用於某個變數第一次出現時。如果想用偏文字敘述的寫法，可以用 let ... be ... 來寫宣告：

let n be 3

let 是來自 JavaScript 等函數式程式的語法；如果想用接近程式碼的寫法，建議用 <- (箭號)；較不建議用 = (等號)，後者太像程式碼：

n <- 3

指派 (Assignment)

指派用於更動某個已知的變數。如果想用偏文字敘述的寫法，可以用 set ... to ... 來寫指派：

set n to 3 + 2

set 是偏函數式程式的寫法，也可用先前提到的 <- (箭號) 來寫。

像 n++ 等遞增 (或減) 之類的其實可以直接寫出來，或是寫成

n <- n + 1

的形式。

代數運算 (Algebraic operations)

代數運算建議保留原本的代數符號，不用刻意寫成 add、subtract 等，因為後者較不直觀，會更難閱讀。如果需要一些數理公式，像是指對數或三角函數等，直接寫出即可，像 log(n)，一般情形下不會要求這些數理公式的內部實作，除非在學數值方法。

選擇 (Selection)

if 是最常見的選擇區塊，可參考以下虛擬碼：

if n > 0 then
  print("n is larger than zero")
else if n < 0 then
  print("n is smaller than zero")
else
  print("n is zero")
end if

switch 是 if 的語法糖，適時使用可簡省程式碼。此虛以類似 C 風格的方式來撰寫：

switch (n)
  case a:
    do something here
  case b:
    do something here
  case c:
    do something here
  default:
    do something here
end switch

迭代 (Iteration)

while 用於次數未定的迭代。此處參考 Lua 的語法來寫：

let n be 10

while n > 0 do
  print("count down n to " + n)
  n <- n - 1
end while

for 用於次數固定的迭代，不建議寫成 C 風格的，太像程式碼；對於使用計數器 (counter) 的可改寫如下：

for i (0 to n - 1) do
  do something here
end for

如果每次跳動不為 1，可加上 step 或 by：

for i (n to 0 by -2) do
  do something here
end for

如果想走訪某個集合 (collection) 可參考以下虛擬碼：

L is a list.

for e (L) do
  do something here
end for

有些程式人會刻意用 foreach 來走訪集合：

L is a list.

foreach e (L) do
  do something here
end foreach

這不是必要的，依個人喜好調整即可

函式 (Function)

在程式設計中，函式包住一段指令，並以有意義的名稱命名該函式，之後就可以重覆呼叫。

函式可以用 sub (subroutine)、func (function) 或 proc (procedure) 開頭來宣告：

sub GCD(a, b): n, n is int
  if x * y != 0 then
    return GCD(b, a % b)
  end if

  return x + y
end sub

結構體 (Structure) 或類別 (Class)

結構體或類別是使用者自訂型態。大部分語言只提供其中一種保留字，C++ 為了相容於 C，同時提供兩種保留字。可以用 class 或 struct 來宣告：

P is a Point struct.

struct Point:
  x <- 0
  y <- 0
end struct

sub X(P): scalar
  return P.x
end sub

sub SetX(P, data): void
  P.x <- data
end sub

sub Y(P): scalar
  return P.y
end sub

sub SetY(P, data): void
  P.y <- data
end sub

這裡用偏向 C 風格的物件語法，其實是從某位補習班老師的參考書修改而來。

陣列 (Array)

在主流的語言，像是 C、C++、Java、C# 等，陣列都是內建的功能，所以可以將陣列視為程式的基本模塊：

arr <- an array from 1 to n

由於大部分主流的程式語言的陣列是以零為基準 (zero-based)，如果擔心以 1 為底的陣列會寫錯索引號碼，也可宣告以 0 為底的陣列：

arr <- a zero-based array from 0 to n - 1

存取陣列元素參考 C 語言的方式撰寫即可：

arr[3] <- 10

集合 (Collections)

除了陣列以外，許多主流語言會提供一些基本集合的函式庫，像是串列等，我們是否可以在虛擬碼中直接宣稱我們要建立一個集合呢？這要看當下的情境而定，如果要呈現資料結構的內部實作，當然就不能宣稱使用現成的集合；如果是要呈現某個演算法，我們就會把集合視為已知的模塊來使用。以下虛擬碼建立一個空的佇列：

Q <- an empty queue

實例：以串列 (list) 實作的堆疊 (stack)

這裡我們用以串列實作的堆疊為實例，來看虛擬碼怎麼寫，因為堆疊的實作很簡單，重點不是演算法本身，而是感受一下虛擬碼寫起來整體的感覺：

N is Node struct
S is Stack struct

struct Node:
  data <- epmty
  next <- null
end class

sub Node(data): Node
  N <- allocate a new Node

  N.data <- data
  N.next <- null

  return N
end sub

struct Stack:
  top <- null
end struct

sub IsEmpty(S): bool
  return S.top == null
end sub

sub Peek(S): data
  assert not IsEmpty(S)

  return S.top.data
end sub

sub Push(S, data): void
  N <- Node(data)

  N.next <- S.top
  S.top <- N
end sub

sub Pop(S): data
  assert not IsEmpty(S)

  curr <- S.top
  popped <- curr.data

  top <- curr.next
  delete curr

  return popped
end sub