汉诺塔

常见玩具版汉诺塔有8个圆盘

3个圆盘的汉诺塔的移动

4个圆盘的汉诺塔的移动

河內塔是根据一个传说形成的一个问题：

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

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

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

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

解答

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

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

传说

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

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

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

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

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

解法

許多的河內塔玩具都有 8 個碟子（disks）。在初學者看起來似乎不太可能有解，然而其演算法以程式語言來說如下：

遞歸解

以 C++ 语言实现:

/*
 * Project     : hannoi
 * 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 A, char B, char C)
{
    if (n == 1)
    {
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
 
    }
    else
    {
        hannoi (n-1, A, C, B);
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
        hannoi (n-1, B, A, C);
    }
}
 
int main()
{
    int n;
    cin >> n;
    hannoi (n, 'A', 'B', 'C');
    return 0;
}
 
// end 
// iCoding@CodeLab
//

以 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;

多塔汉诺塔问题

• 在有3个柱子时，所需步数的公式较简单，但对于4个以上柱子的汉诺塔尚未得到通用公式，但有一递归公式（未得到证明，但目前为止没有找到反例）：
• 令$f(n,k)$为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：

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

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

流行文化

2011年電影《猿人爭霸戰：猩凶革命》曾出現河內塔以測試猩猩的智商。