河内塔(Tower of Hanoi)是一个很谜的数学游戏,它是由三根杆子(Rod)和一个以上大小不同的盘片(Disk)所组成的。在游戏的一开始,这些盘片按照底大顶小的顺序叠在一起,由三根杆子中的其中一根串着。玩家每次可以移动一个盘片到其它的杆子上,但是不能将比较大的盘片叠在比较小的盘片上。当玩家把所有盘片都串到指定的杆子,游戏就结束了。

三碟的河内塔

如上图所示,就是一个三碟的河内塔游戏。习惯上会把最左边的杆子称作「A」,是起点。中间的杆子称作「B」。右边的杆子称作「C」,是终点。

所以要完成上面的这个河内塔,就要把左边的三个盘片移动到右边。移动方式如下视频:

通常河内塔的游戏至少会有三个盘片(如果盘片只有两个以下那还玩个毛),盘片愈多难度愈高。如果您从来没玩过的话,就算看了上面的视频,应该也还是不知道要怎么移,或者不知道为什么要那样移动。

其实要完成一个河内塔游戏,盘片的移动方式不只有一种而已。如果我们把视频中的盘片,以黄色、红色、蓝色的顺序来表示其所在的杆子,一开始,我们可以用 AAA 来表示(黄色、红色、蓝色都在 A 杆子)。下一步,我们只能够移动黄色盘片到 B 杆子或是 C 杆子,所以可以标示为 BAA(黄色在 B 杆子,红色、蓝色在 A 杆子)或是 CAA(黄色在 C 杆子,红色、蓝色在 A 杆子)。再下一步,可以移动黄色或红色盘片到空的杆子上,所以如果这一步是 BAA 的话,下一步就是 BCA 或 CAA;如果这一步是 CAA 的话,下一步就是 CBA 或 BAA。

让我们依此类推,继续用这样的标示法来把所有的组合都找出来,会得到如下的结果:

              AAA
              / \
            BAA-CAA
            /     \
          BCA     CBA
          / \     / \
        CCA-ACA-ABA-BBA
        /             \
      CCB             BBC
      / \             / \
    ACB-BCB         CBC-ABC
    /     \         /     \
  ABB     BAB     CAC     ACC
  / \     / \     / \     / \
BBB-CBB CAB-AAB-AAC-BAC-BCC-CCC

如上,我们把三碟的河内塔所有的移动方式都画成图(Graph)了,每条边所连接的两个节点表示这两个节点「只差了一步」。AAA 作为我们的起点,CCC 作为我们的终点,从上图可以快速地看出起点到终点的最短路径为 7。换句话说,三碟的河内塔,最少只要移动 7 步就可以完成。

再仔细看一次上面的视频,可以发现视频中的盘片移动方式正是最短路线。而且我们还可以注意到一个点,那就是我们在把三个盘片移动到 C 杆子前,有先把两个盘片移动到 B 杆子;而在两个盘片移动到中间前,有先把一个盘片移动到 C 杆子。也就是说,若我们要移动 #{{n}}# 个盘片到某指定的杆子上,就要先把 #{{n - 1}}# 个盘片移动到旁边的杆子上,此时最大的盘片就可以被移动到指定的杆子上,最后再把旁边杆子上的 #{{n - 1}}# 个盘片移来最大的盘片上,#{{n}}# 个盘片就都在指定的杆子上啦。

简而言之,我们找出的「以最短步数解决河内塔问题的算法」就是:

步骤一:移动 A 杆子上的 #{{n - 1}}# 个盘片到 B 杆子上。

将 n - 1 个盘片移到 B 杆子

步骤二:移动 A 杆子剩下的一个盘片到 C 杆子上。

将剩下的盘片移到 C 杆子

步骤三:移动 B 杆子上的所有(#{{n - 1}}# 个)盘片到 C 杆子上。

将 B 杆子上的盘片移到 C 杆子

如何?有没感觉像是在讲屁话?可是电脑真的可以这样做!

实际写程序就知道了。首先创建一个 hanoi 函数,让它可以透过参数输入盘片的数量 #{{n}}#、起始的杆子、结束的杆子和暂存的杆子。在程序一开始先去判断盘片的数量是否为 1,如果是的话就把盘片从起始的杆子移动到结束的杆子。我们不必真的创建出盘片的对象或是数值,因为河内塔的重点是在找盘片的移动方式。例如:A 移到 B→A 移到 C→B 移到 C。

可以先写出以下的代码:

接着就要来套入我们刚才找出的算法来计算 #{{n > 1}}# 时的情形了。首先是步骤一,要将起始的杆子上的 #{{n - 1}}# 个盘片移动到暂存的杆子。代码如下:

接着是步骤二,将起始的杆子上剩下来的一个盘片移动到结束的杆子上。代码如下:

最后是步骤三,移动暂存的杆子上所有的,也就是 #{{n - 1}}# 个盘片到结束的杆子上。代码如下:

至此我们就完成递归版本的河内塔函数了!很简单吧!不过笔者当初接触到河内塔的递归函数的时候,根本看不懂它在干嘛,所以是直接把它背起来,应付考试而已。后来从头开始厘清河内塔到底在干什么,自然就可以写出递归函数了,完全不需要背。

另外我们根据一个盘片的河内塔最少要移动 1 次来完成、两个盘片的河内塔最少要移动 3 次来完成、三个盘片的河内塔最少要移动 7 次来完成、四个盘片的河内塔最少要移动 15 次来完成,推测出 #{{n}}# 个盘片至少需要移动 #{{2^n - 1}}# 次来完成。利用数学归纳法的证明过程如下。

设 #{{S_n}}# 为 #{{n}}# 个盘片最少所需要的移动次数,而根据那三个步骤,我们知道 #{{S_{n + 1} = S_n + 1 + S_n}}#。

#{{{
\begin{alignedat}{2}
\\
\text{证明 } S_n &{}={}&& 2^n - 1, n \in \mathbb{N^+} \\
\\
n = 1, \\
S_1 &{}={}&& 2^1 - 1 = 1 \text{ (成立)} \\
\\
\text{假设 } n = k, \\
S_{k} &{}={}&& 2^k - 1 \\
\\
n = k + 1, \\
S_{k + 1} &{}={}&& S_k + 1 + S_k \\
&{}={}&& 2^k - 1 + 1 + 2^k - 1 \\
&{}={}&& 2^k + 2^k - 1 + 1 - 1 \\
&{}={}&& 2 \times 2^k - 1 \\
&{}={}&& 2^{k + 1} - 1 \\
\\
\therefore S_n &{}={}&& 2^n - 1, n \in \mathbb{N^+} \text{ 是正确的}
\end{alignedat}
}}}#

程序写出来了,但还是不知道怎么玩河内塔……

即便理解河内塔主要想展示的思想(大问题分解成小问题,也就是递归啦),在现实中使用教具或是桌游玩具玩河内塔,甚至是玩河内塔的电子游戏时,盘片数量超过三个的时候还是不知道该如何下手啊!毕竟人脑不像电脑那样,可以快速以递归的方式来思考问题。

所以我们必须要再想个「迭代」的方式来解决河内塔的问题。

在开始想之前,可以先看看下面这篇文章,将递归版本的河内塔直接转成迭代版本。

转出来的程序如下:

以上的河内塔函数,虽然已经是迭代版本了没错,但骨子里还是用递归(或者更准确来说是 Top-down)的方式在算的,看看就好。

其实多玩几次三个盘片的河内塔和四个盘片的河内塔(或是也可以玩两个盘片,如果您真的不太会玩河内塔的话),就可以发现如果要用最少的步数来完成河内塔的话,三个盘片和四个盘片分别在一开始,最小的盘片必须要移动往不同的杆子。像是三个盘片的河内塔,第一步就必须要先将最小的盘片从 A 杆移到 C 杆;而四个盘片的河内塔,第一步就必须要先将最小的盘片从 A 杆移到 B 杆。这是为了要确保 #{{n - 1}}# 个盘片在移动之后,是在暂存的杆子上,而不是在结束的杆子上,好让我们能把起始的杆子上的最大的盘片移动到结束的杆子。若 #{{n - 1}}# 个盘片在移动之后,是在结束的杆子上,那我们也就只能再把 #{{n - 1}}# 个盘片搬到暂存的杆子上后,才能把起始的杆子上的最大的盘片移动到结束的杆子。

也就是说,河内塔第一步最小的盘片移动的方式,要根据盘片的数量是奇数还是偶数来决定。如果是三个盘片的河内塔,那第一步就是把最小的盘片从 A 杆移到 C 杆;如果是四个盘片的河内塔,那第一步就是把最小的盘片从 A 杆移到 B 杆。

若您还不了解的话,试想一下,若我们玩四个盘片的河内塔,第一步是把最小的盘片从 A 杆移到 C 杆的话,那不就跟在玩三个盘片的河内塔时一样,就会先把三个盘片移动到 C 杆了,然后又得把那三个盘片再移到 B 杆上,才能将 A 杆上最大的盘片移到 C 杆,所以这对四个盘片的河内塔游戏来说也就不会是一个最佳的解决方式。

所以知道第一步要怎么移之后呢?我们都知道河内塔的盘片只是大的在下、小的在上,因此最小的盘片在被移动之后,势必得赶紧移回第二小的盘片之上,不然任何其它的盘片都无法使用最小的盘片所在的杆子。当然,我们不会在移动完最小的盘片后,下一步又把它移回去,或者又把它移动到另一个杆子上,因为这样一点意义都没有。也就是说,我们合理能做的第二步,就是将第二小的盘片移动到另一个杆子上,然后在第三步的时候,把最小的盘片移到第二小的盘片所在的杆子上。此时就完成了两个盘片的移动。

再来要进行第四步的时候,我们就会发现,除了将最小的盘片又移动到其它杆子上外,其实也只剩下一种移动方式。在此时若将最小的盘片又移动到其它杆子上,就等同于又要开始进行最小和第二小的盘片的移动,没有意义。所以我们也只能够选择剩下的那一种移动方式。

第五步时,我们不考虑去还原第四步,就只会剩下一种移动方式,那就是花费三步(第五步、第六步、第七步)去移动最小和第二小的盘片。

第八步时,同理,除了将最小的盘片又移动到其它杆子上外,其实也只剩下一种移动方式。

聪明的读者们大概都看得出来这其中的规律了吧!也就是「四步一循环」:移动最小的盘片→移动第二小的盘片→移动最小的盘片到第二小的盘片上→移动其它的盘片。

现在的问题是在于,「移动最小的盘片」时,该盘片因为最小,所以另外两个杆子都可以成为目标,但除了第一步我们知道最小的盘片究竟要移动到哪个杆子之外,第五步、第九步……到达这些后续的步数时,就不知道该怎么移动了。

事实上,如果我们观察河内塔最短步数的移动方式,会在「移动最小的盘片」的步骤时,发现它们总是往同一个「方向」移动一个距离。以三个盘片的河内塔来说,一开始将最小的盘片从 A 杆移到 C 杆,看作是「向左」(A 杆子向左会到 C 杆子,形成循环);而四个盘片的河内塔,一开始将最小的盘片从 A 杆移到 B 杆,看作是「向右」(C 杆子向右会到 A 杆子,形成循环)。找出这个「向左」、「向右」规律后,我们可以扩充一下我们刚刚发现的「四步一循环」规则:

  • 0. 判断盘片的数量是奇数还是偶数,来决定最小的盘片和第二小的盘片移动时的方向。偶数往右;奇数往左。
  • 1. 移动最小的盘片一个杆子的距离。
  • 2. 移动第二小的盘片两个杆子的距离。
  • 3. 移动最小的盘片一个杆子的距离。(将最小的盘片移动到第二小的盘片上。)
  • 4. 移动其它的盘片。

如此一来在游玩河内塔的时候,我们可以在心中默念「一、二、三、四」,按照步骤来解决河内塔,完全不需要动脑。

总算会玩了吧!那用这样的方式写程序来实作一个迭代版本的河内塔函数如何?程序如下:

以上程序,将「向左」、「向右」的问题以交换除了起始的杆子之外的两个杆子来简化。试想一下,向右的顺序如果是 ABCABC,那么向左就是 ACBACB,这不就是把 B、C 两个杆子交换了吗?

再来,一个循环的第四步如果我们不知道当下盘片的分布情形,就不知道要怎么移动了(以上程序先以 Move a disk from ? to ?. 来输出)。所以我们必须在每步都去改变并记录盘片的分布情形才行,可以用一个堆栈来模拟一个杆子,三个杆子就是三个堆栈。将以上程序加入堆栈后的样子如下:

以上程序,创建了三个堆栈来保存盘片(数值愈小的盘片尺寸愈大。0 表示杆子的底部,以一个尺寸最大的盘片来模拟,所以移不走)。再来就是要处理每个循环的第四步,盘片要怎么移动了。其实这个很简单,我们只需判断前两小的盘片所在的另外两个杆子,看它们顶部保存的数值哪个比较大,就从顶部数值比较大的杆子移到顶部数值比较小的杆子。

所以最终的代码如下:

这边再介绍另一个河内塔迭代版的算法,现实中在玩河内塔的时候也可以使用,但是会比较烧脑一点。

如果仔细观察河内塔最短路径的解,可以发现一个「三步一循环」的规律,而且有区分偶数和奇数的盘片数量。偶数就是「AB→AC→BC」,奇数就是「AC→AB→BC」。

什么意思?

如果盘片数量为偶数,在这三步组成的循环中,第一步我们只需要去看 A、B 这两个杆子,看是要把盘片从 A 杆移到 B 杆,还是要反过来从 B 杆移到 A 杆;第二步只需要去看 A、C 这两个杆子,看是要把盘片从 A 杆移到 C 杆,还是要反过来从 C 杆移到 A 杆;第三步只需要去看 B、C 这两个杆子,看是要把盘片从 B 杆移到 C 杆,还是要反过来从 C 杆移到 B 杆。

与先前同样地,若要以程序来实作,当盘片数量为奇数时,可以先去交换 B、C 两个杆子,这样一来「三步一循环」的规律就只剩下「AB→AC→BC」了。所以可以写出以下迭代版本的河内塔函数:

不用堆栈空间的河内塔迭代算法

回顾我们一开始介绍的递归版本的河内塔算法:

步骤一:移动 A 杆子上的 #{{n - 1}}# 个盘片到 B 杆子上。

回顾递归版本:n - 1 个盘片移到 B 杆子

步骤二:移动 A 杆子剩下的一个盘片到 C 杆子上。

回顾递归版本:最大的盘片移到 C 杆子

步骤三:移动 B 杆子上的所有(#{{n - 1}}# 个)盘片到 C 杆子上。

回顾递归版本:B 杆子的盘片移到 C 杆子

其实要把已知步骤的 #{{n}}# 个盘片从一个杆子搬到另一个杆子上是很容易的。举例来说,若要把三个盘片从 A 杆搬到 C 杆,搬移步骤如下:

Move a disk from A to C.
Move a disk from A to B.
Move a disk from C to B.
Move a disk from A to C.
Move a disk from B to A.
Move a disk from B to C.
Move a disk from A to C.

而若要把三个盘片从 A 杆搬到 B 杆,搬移步骤如下:

Move a disk from A to B.
Move a disk from A to C.
Move a disk from B to C.
Move a disk from A to B.
Move a disk from C to A.
Move a disk from C to B.
Move a disk from A to B.

有没有发现?其实我们只要把从 A 杆搬到 C 杆的路线中的 B、C 杆子交换就可以了。

而若要把三个盘片从 B 杆搬到 C 杆,搬移步骤如下:

Move a disk from B to C.
Move a disk from B to A.
Move a disk from C to A.
Move a disk from B to C.
Move a disk from A to B.
Move a disk from A to C.
Move a disk from B to C.

有没有发现?其实我们只要把从 A 杆搬到 B 杆的路线中的 A 换成 B、B 换成 C、C 换成 A。

所以呢?

根据这个发现,要把 #{{n}}# 个盘片从 A 杆搬到 C 杆,我们可以先将 #{{n - 1}}# 个盘片搬到 C 杆(可沿用计算 #{{n - 1}}# 个盘片时找出的解),接着再把 B、C 杆子交换(利用 A 杆到 C 杆的路线,把 B、C 杆子交换),然后再把剩下的一个盘片从 A 杆搬到 C 杆,最后再把 B 杆的 #{{n - 1}}# 个盘片搬到 C 杆(利用 A 杆到 B 杆的路线,把 A 换成 B、B 换成 C、C 换成 A)。

为了快速地将路线进行置换,我们可以把六种(#{{P^3_2 = 6}}#)移动方式编号如下,称作「路线表」好了。

  • 0: A→B
  • 1: A→C
  • 2: B→A
  • 3: B→C
  • 4: C→A
  • 5: C→B

把「路线表」的 B、C 杆子交换,并依照原来 A→B、A→C、B→A、……的方式来排序,结果如下:

  • 1: A→B
  • 0: A→C
  • 4: B→A
  • 5: B→C
  • 2: C→A
  • 3: C→B

这样做可以让我们利用原先路线的编号,快速地对应到把 B、C 杆子交换后的结果。

把「路线表」的 A 换成 C、C 换成 B、B 换成 A,并依照原来 A→B、A→C、B→A、……的方式来排序,结果如下:

  • 3: A→B
  • 2: A→C
  • 5: B→A
  • 4: B→C
  • 0: C→A
  • 1: C→B

这样做可以让我们利用原先路线的编号,快速地对应到把 A 换成 B、B 换成 C、C 换成 A 后的结果。

再来我们就可以实作出不需堆栈空间(但需要暂存结果)的河内塔迭代函数:

让程序能输出盘片编号

为了让各位更容易了解,上面提供的代码都没有输出究竟是哪个盘片被移动了。所以最后就来提供一下,这些代码的「完整版」吧!

首先是递归版本的河内塔。(盘片数字愈小,尺寸愈小)

再来是「四步一循环」与「三步一循环」的堆栈空间迭代版所用的 move_disk 或 moveDisk 函数。(盘片数字愈小,尺寸愈大)

最后是无堆栈空间的迭代版河内塔。(盘片数字愈小,尺寸愈小)

利用盘片的输出规律来实现不用堆栈空间的河内塔迭代版函数

在实作出有输出盘片编号的河内塔程序后,可以试玩一下,会发现输出的盘片编号其实也有规律。

如果我们只让河内塔程序输出盘片编号,四个盘片的结果如下:

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

五个盘片的结果如下:

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

六个盘片的结果如下:

1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  6  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3  1  2  1  4  1  2  1  3  1  2  1

看出来了吗?这摆明就是一个数列嘛!而且可以找出以下公式来直接求得指定项数的值。

#{{{
a_n = \lfloor log_2{(n \text{ } XOR \text{ } (n + 1))} \rfloor + 1, n \in \mathbb{N^0}
}}}#

也就是说,我们先前利用「四步一循环」和「三步一循环」规律来实作的迭代版的河内塔函数,可以改成无堆栈空间的版本,只需要额外记录当下的所有盘片在哪个杆子上即可,而且也可以顺便将它们修改成以「盘片数字愈小,尺寸愈小」的方式来输出。

将「四步一循环」修改后的代码如下:

将「三步一循环」修改后的代码如下: