如何撰寫虛擬碼 (Pseudocode)

直接使用程式碼來呈現 (資料結構和) 演算法,往往需注意過多細節,像是型別、陣列長度、存取權限、記憶體管理等,而且程式語言很多,單一語言能滿足的客群相對小。有許多演算法的書籍會轉而使用虛擬碼 (pseudocode) 來表示,由讀者自行將其轉為可用的程式碼。虛擬碼不需在意程式語言的細節,敘述上比較簡潔。

在虛擬碼和程式碼之間的轉換,需要一段時間的學習才能上手。但學過一段時間的程式設計後,反而會覺得程式碼比虛擬碼簡單,因為編譯器或直譯器會協助我們找出程式碼中的錯誤,而虛擬碼沒有固定的格式,只能由人工閱讀來確認是否正確。有時候我們需要撰寫虛擬碼而非程式碼,像是學校考試、學術報告、技術文件等;因此,除了能讀懂別人寫的虛擬碼,最好還是要能自己寫虛擬碼。

虛擬碼的風格差異很大,有些會用數學表示法 (mathematical notation),有些會用口語敘述,有些會接近真正的程式碼。沒有那一種風格是最好的,要看當下的需求來決定。學習虛擬碼就像學習程式語言,只要針對不同情境撰寫相對應的虛擬碼,再將其組合起來即可。一般來說,程式設計常見的情境如下:

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

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

[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)

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

選擇 (Selection)

if 是最常見的選擇區塊,可參考 Ruby 的語法撰寫虛擬碼:

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 a > b then
    print("a is larger then b")
end if

switchif 的語法糖,適時使用可簡省程式碼。此虛以類似 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 from 0 to n - 1) do
    do something here
end for

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

L is a list.

for (e in L) do
    do something here
end for

函式 (Function)

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

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

類別 (Class)

類別可以用 classstruct 來宣告:

P is a Point.

class Point:
    x <- 0
    y <- 0
  
sub X(P): scalar
    return P.x

sub SetX(P, data): void
    P.x <- data
  
sub Y(P): scalar
    return P.y

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

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

陣列 (Array)

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

arr <- an array from 1 to n

如果擔心以 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 a Node.
S is a Stack.

class Node:
    data <- none
    next <- null

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

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

    return N

class Stack:
    top <- null

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

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

    return S.top.data

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

    N.next <- S.top
    S.top <- N

sub Pop(S): data
    assert not IsEmpty(S)
    
    curr <- S.top
    popped <- curr.data
  
    top <- curr.next
    delete curr
  
    return popped
上篇為什麼要用 C 語言寫物件導向程式?
下篇JavaScript 轉譯器百百種,孰優孰劣?