技术杂谈:如何撰写伪代码 (Pseudocode)

PUBLISHED ON APR 17, 2018

    直接使用程序代码来呈现 (数据结构和) 算法,往往需注意过多细节,像是类型、数组长度、存取权限、内存管理等,而且程序语言很多,单一语言能满足的客群相对小。有许多算法的书籍会转而使用伪代码 (pseudocode) 来表示,由读者自行将其转为可用的程序代码。伪代码不需在意程序语言的细节,叙述上比较简洁。

    在伪代码和程序代码之间的转换,需要一段时间的学习才能上手。但学过一段时间的程序设计后,反而会觉得程序代码比伪代码简单,因为编译器或直译器会协助我们找出程序代码中的错误,而伪代码没有固定的格式,只能由人工阅读来确认是否正确。有时候我们需要撰写伪代码而非程序代码,像是学校考试、学术报告、技术文件等;因此,除了能读懂别人写的伪代码,最好还是要能自己写伪代码。

    伪代码的风格差异很大,有些会用数学表示法 (mathematical notation),有些会用口语叙述,有些会接近真正的程序代码。没有那一种风格是最好的,要看当下的需求来决定。学习伪代码就像学习程序语言,只要针对不同情境撰写相对应的伪代码,再将其组合起来即可。一般来说,程序设计常见的情境如下:

    • 声明 (declaration)
    • 指派 (assignment)
    • 代数运算 (algebraic operations)
    • 选择 (selection)
    • 迭代 (iteration) *函数 (function)
    • 类 (class)
    • 数组 (array)
    • 集合 (collections)

    我们只要针对这些情境撰写相对应的伪代码,大概就可以抓到伪代码的写法。学习其他人的伪代码也是用相同的要诀去拆解各种不同的情境即可。

    [Update on 2018/04/25] 略为修改伪代码写法,希望能更加直观。

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

    注意事项

    既然要写伪代码,就不能直接写出程序代码,顶多只能风格上接近程序代码。以考试的情境来说,该写伪代码却直接写程序代码会让考官觉得考生没有抓到算法的抽象思维,无法跳脱特定程序语言的实现方式;所以平常最好还是练习一下。笔者以为,比较接近程序代码的伪代码会比较好写,建议不熟伪代码的读者可由这个方向下手;如果仔细观察本文,也会发现这个现象。

    由于伪代码没有严谨的格式,不会有什么伪代码的编译器或直译器,仅能由人工检阅,一开始时其实不太好上手。如果没办法直接写伪代码,可以先写程序代码,再将其手动转为伪代码,来回对照几次后,慢慢就会抓到写伪代码的要诀。一开始练习时,可以先从很简单的算法开始,像是求最大公因数、求 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 (0 to n - 1) do
        do something here
    end for
    

    如果每次跳动不为 1,可加上 stepby

    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
    

    类 (Class)

    类可以用 classstruct 来声明:

    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
    

    由于大部分主流的程序语言的数组是以零为基准 (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 a Node.
    S is a Stack.
    
    class Node:
        data <- epmty
        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
    
    你或许对以下产品有兴趣
    All code in the website is licensed under Apache 2.0 unless otherwise mentioned.