汉诺塔

传说

最早发明这个问题的人是法国数学家爱德华·卢卡斯。
传说越南河内某间寺院有三根银棒，上串64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5849 亿年才能完成。整个宇宙现在也不过137 亿年。
这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

解答

如取N=64，最少需移动2⁶⁴-1 次。即如果一秒钟能移动一块圆盘，仍将需5849.42 亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137 亿年。
在真实玩具中，一般 N=8；最少需移动255 次。如果 N=10，最少需移动1023 次。如果N=15，最少需移动32767次；这就是说，如果一个人从3 岁到99 岁，每天移动一块圆盘，他最多仅能移动15 块。如果 N=20，最少需移动1048575 次，即超过了一百万次。

算法求解

解法的基本思想是递归。假设有A、B、C 三个塔，A 塔有 块盘，目标是把这些盘全部移到C 塔。那么先把A 塔顶部的 块盘移动到B 塔，再把A 塔剩下的大盘移到C，最后把B 塔的 块盘移到C。
如此递归地使用下去, 就可以求解。

递归解

以 C++ 语言实现:
#include <iostream>#include <cstdio>using namespace std;void hannoi (int n, char from, char buffer, char to){
    if (n == 0)
        return;
    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;}
以 Python 语言实现:
def hanoi(n, a, b, c):
if n == 1:
print(a, '-->', c)
else:
hanoi(n - 1, a, c, b)
hanoi(1    , a, b, c)
hanoi(n - 1, b, a, c)# 调用if __name__ == '__main__':
hanoi(5, 'A', 'B', 'C')

以 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.
以 Haskell 语言实现:
hanoi :: Integer -> String -> String -> String -> [(String, String)]hanoi 0 _ _ _ = []hanoi 1 from _ to = [(from, to)]hanoi x from buffer to = 
    hanoi (x-1) from to buffer ++ hanoi 1 from buffer to ++ hanoi (x-1) buffer from to

任意初始结构（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);
    }}

流行文化

2011年 电影《猿族崛起》曾出现汉诺塔以测试猩猩的智商。其后续电影《猿族崛起2》中也有类似的场景。