汉诺塔（港台：河內塔）是根据一个传说形成的數學问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

传说

最早發明這個問題的人是法國數學家愛德華·盧卡斯。

傳說印度某間寺院有三根柱子，上串64个金盤。寺院裡的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完毕，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要2⁶⁴ − 1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5845億年才能完成。整個宇宙現在也不過137億年。

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位于越南的河內，所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。

佛教中確實有「浮屠」（塔）這種建築；有些浮屠亦遵守上述規則而建。「河內塔」一名可能是由中南半島在殖民時期傳入歐洲的。

解答

如取N=64，最少需移动2⁶⁴-1次。即如果一秒钟能移动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

在真实玩具中，一般N=8；最少需移动255次。如果N=10，最少需移动1023次。如果N=15，最少需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他最多仅能移动15块。如果N=20，最少需移动1048575次，即超过了一百万次。

解法

解法的基本思想是递归。假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。

每次移动多于一块盘时，则再次使用上述算法来移动。

遞歸解

以 C++ 语言实现:

/*
 * Project     : hanoi
 * File        : main.cpp
 * Author      : iCoding
 *
 * Date & Time : Sat Oct 06 21:01:55 2012 
 *
 */
using namespace std;
#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << from << " to " << to << endl;

    }
    else
    {
        hannoi (n-1, from, to, buffer);
        cout << "Move disk " << n << " from " << from << " to " << to << endl;
        hannoi (n-1, buffer, from, to);
    }
}

int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}

// end 
// iCoding@CodeLab
//

以 Python 语言实现:

def hanoi(n, a='A', b='B', c='C'): 
    if n == 1:
        print('move', a, '-->', c)
        return
    hanoi(n-1, a, c, b)
    print('move', a, '-->', c)
    hanoi(n-1, b, a, c)

print(hanoi(5))

以 Erlang 语言求解：

-module(hanoi).
-export([hanoi/1]).
hanoi(N) when N>0 ->
	do_hanoi({N, 1, 3}).

do_hanoi({0, _, _}) ->
	done;
do_hanoi({1, From, To}) ->
	io:format("From ~p, To ~p~n", [From, To]);
do_hanoi({N, From, To}) ->
	do_hanoi({N-1, From, by(From, To)}),
	do_hanoi({1, From, To}),
	do_hanoi({N-1, by(From, To), To}).

by(From, To) ->
	[Result|_] = [1, 2, 3] -- [From, To],
	Result.

任意初始結構（arbitrary initial configuration）的解法[编辑]

為了從任意初始結構中找尋最佳解（optimal solution），其演算法可以一般化（be generalized）如下：

以 Scheme 語言表示：

 ; Let conf be a list of the positions of the disks in order of increasing size.
 ; Let the pegs be identified by the numbers 0, 1 and 2.
 (define (hanoi conf t)
  (let ((c (list->vector conf)))
   (define (move h f t)
    (vector-set! c h t)
    (printf "move disk ~s from peg ~s to peg ~s~n" h f t))
   (define (third-peg f t) (- 3 f t))
   (define (hanoi h t)
    (if (> h 0)
     (let ((h (sub1 h)))
      (let ((f (vector-ref c h)))
       (if (not (= f t))
        (let ((r (third-peg f t)))
         (hanoi h r)
         (move h f t)))
       (hanoi h t)))))
   (hanoi (vector-length c) t)))

在 C語言中:

int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */

void move(int d, int t) {
    /* move disk d to peg t */
    conf[d] = t;
}

void hanoi(int h, int t) {
    if (h > 0) {
        int f = conf[h-1];
        if (f != t) {
            int r = 3 - f - t ;
            hanoi(h-1, r);
            move(h-1, t);
        }
        hanoi(h-1, t);
    }
}

在PASCAL語言中:

procedure Hanoi(n: integer; from, to, by: char);
Begin
    if (n=1) then
        writeln('Move the plate ',n,' from ', from, ' to ', to)
    else begin
        Hanoi(n-1, from, by, to);
        Writeln('Move the plate ',n,' from ', from, ' to ', to);
        Hanoi(n-1, by, to, from);
    end;
End;

非遞歸解[编辑]

SAS Institute Inc. 员工 Yinliang Wu 在研究汉诺塔结果数据时发现了一种基于如下隐藏模式的新求解方法：

• 对于 1 个盘子的情况，移动步骤总是从源柱子到目标柱子，即 a-> c;
• 基于此初始状态，对于 n 个盘子的求解可以由如下模式产生：
  • 对 n-1 个盘子的移动步骤，交换目标柱子和中间柱子，即 定义 T1 =交换(b,c);
  • 插入从源柱到目标柱子的移动步骤：a->c;
  • 对 n-1 个盘子的移动步骤，交换来源柱子和中间柱子，即 定义 T2=交换(b,a);

举例来说：

• seq(1)={from->to}={a->c}
• seq(2)={ T1(seq(1)), {from->to}, T2(seq(1))}. 因为 T1=swap(middle, to) 和 T2=swap(middle, from), 则　T1({a->c})= {a->b}, T2({a->c})={b->c}, 最终的步骤为 seq(2)={a->b, a->c, b->c}
• seq(3)=T1(seq(2)), {from->to}, T2(seq(2))} = {a->c, a->b, c->b} + {a->c} + { b->a, b->c, a->c} ={a->c, a->b, c->b, a->c, b->a, b->c, a->c}

这种非递归的方式是利用数据统计发现的隐藏模式，可以在著名统计分析语言 SAS 的数据步中轻松实现，也能在其他计算机编程语言中快速实现。

二元解[编辑]

多塔汉诺塔问题[编辑]

• 在有3个柱子时，所需步数的公式较简单，但对于4个柱子以上時，情形複雜許多。Frame及Stewart在1941年時分別提出了基本上相同的一套演算法^[1]，Bousch則在2014年證明了Frame-Stewart演算法在4個柱子時就是最佳解^[2]，但此演算法在5個柱子以上是否是最佳解仍是未知。

Frame-Stewart演算法本質上也是递归的，可簡單敘述如下：

• 令${\displaystyle f(n,k)}$为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：

对于任何移动方法，必定会先将${\displaystyle m(1\leq m\leq n-1)}$个圆盘移动到一个中间柱子上，再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上，最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为${\displaystyle 2f(m,k)+f(n-m,k-1)}$。

进行最优化，易得:${\displaystyle f(n,k)=\mathrm {min} _{m\in [1,n-1]}\;(2f(m,k)+f(n-m,k-1))}$ 。

流行文化[编辑]

2011年電影《猿人爭霸戰：猩凶革命》曾出現河內塔以測試猩猩的智商。其后续电影《猩球崛起2》中也有类似的场景。

參見[编辑]

• 九連環
• 遞迴

參考來源[编辑]

外部連結[编辑]

• MathWorld上Tower of Hanoi的资料，作者：埃里克·韦斯坦因。
• Tower of Hanoi animation