传说

最早发明这个问题的人是法国数学家爱德华·卢卡斯。

传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

若传说属实，僧侣们需要2 − 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要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塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。

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

递归解

以C++语言实现:

/* * Project : hannoi * File : main.cpp * Author : iCoding * * Date & Time : Sat Oct 06 21:01:55 2012 * */usingnamespacestd;#include#includevoidhannoi(intn,charfrom,charbuffer,charto){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<>n;hannoi(n,"A","B","C");return0;}// end // iCoding@CodeLab//

以Python语言实现:

defhanoi(n,a="A",b="B",c="C"):ifn==1:print("move",a,"-->",c)returnhanoi(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)whenN>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 (hanoiconft)(let ((c(list->vector conf)))(define (movehft)(vector-set! cht)(printf"move disk ~s from peg ~s to peg ~s~n"hft))(define (third-pegft)(- 3ft))(define (hanoiht)(if (> h0)(let ((h(sub1h)))(let ((f(vector-ref ch)))(if (not (= ft))(let ((r(third-pegft)))(hanoihr)(movehft)))(hanoiht)))))(hanoi(vector-length c)t)))

在 C语言中:

intconf[HEIGHT];/* Element conf[d] gives the current position of disk d. */voidmove(intd,intt){/* move disk d to peg t */conf[d]=t;}voidhanoi(inth,intt){if(h>0){intf=conf[h-1];if(f!=t){intr=3-f-t;hanoi(h-1,r);move(h-1,t);}hanoi(h-1,t);}}

在PASCAL语言中:

procedureHanoi(n:integer;from,to,by:char);Beginif(n=1)thenwriteln("Move the plate ",n," from ",from," to ",to)elsebeginHanoi(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 个盘子的求解可以由如下模式产生：

举例来说：

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年时分别提出了基本上相同的一套算法，Bousch则在2014年证明了Frame-Stewart算法在4个柱子时就是最佳解，但此算法在5个柱子以上是否是最佳解仍是未知。

Frame-Stewart算法本质上也是递归的，可简单叙述如下：

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

流行文化

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。