汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

由 来

印度传说

相关预言

汉诺塔与宇宙寿命

concreteHAM(在分析（2）之前 讨论问题（2）， 算法介绍)

汉诺塔问题的程序实现(汉诺塔问题的递归实现 汉诺塔问题的非递归实现 汉诺塔问题的递归Java语言实现 汉诺塔问题的递归pascal语言实现 汉诺塔问题的递归易语言实现)

由 来

一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

f(64)= 2^64-1=18446744073709551615

假如每秒钟一次，共需多长时间呢？一个平年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，

18446744073709551615/31556952=584554049253.855年

这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

印度传说

和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。

那么，宰相要求得到的麦粒到底有多少呢？总数为

1+2+2^2 + … +2^63 =2^64-1

和移完汉诺塔的次数一样。我们已经知道这个数字有多么大了。人们估计，全世界两千年也难以生产这么多麦子！

相关预言

有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。

汉诺塔与宇宙寿命

如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什么时候呢？

让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了

因此让我们逻辑性的思考一下吧。

4个的时候能够移动最大的4盘时如图所示。

到此为止用了7次。

接下来如下图时用1次，在上面再放上3个圆盘时还要用7次（把3个圆盘重新放在一起需要的次数）。

因此，4个的时候是

“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”

=2x“3个圆盘重新摞在一起的次数”+1次

=15次。

那么，n个的时候是

2x“（n-1）个圆盘重新摞在一起的次数”+1次。

由于1 个的时候是1次，结果n个的时候为（2的n次方减1）次。

1个圆盘的时候 2的1次方减1

2个圆盘的时候 2的2次方减1

3个圆盘的时候 2的3次方减1

4个圆盘的时候 2的4次方减1

5个圆盘的时候 2的5次方减1

........

n个圆盘的时候 2的n次方减1

也就是说，n=64的时候是（2的64次方减1）次。

因此，如果移动一个圆盘需要1秒的话，

宇宙的寿命=2的64次方减1（秒）

2的64次方减1到底有多大呢？动动计算器，答案是一个二十位的数字：

18446744073709551615

用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。

据说，现在的宇宙年龄大约是150亿年，还差得远呢。

汉诺塔问题在数学界有很高的研究价值，

而且至今还在被一些数学家们所研究，

也是我们所喜欢玩的一种益智游戏，

它可以帮助开发智力，激发我们的思维。

concreteHAM

现在有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。

首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式：

H(1) = 1

H(n) = 2*H(n-1)+1 (n>1)

那么我们很快就能得到H(n）的一般式：

H(n) = 2^n - 1 (n>0)

并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。

进一步加深问题（解法原创*_*）：

假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：（1）假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n）；（2）只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n）。

(1）中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：

J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2

在分析（2）之前

，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。

现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1），所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。

讨论问题（2），

综上两点，可以得出，要把A上2n个盘子移动到B上，首先可以得出上方的2n-2个盘子必定移动偶数次，所以顺序不变，移动次数为：

J(n-1) = 2^n-2

然后再移动倒数第二个盘子，移动次数为2*J(n-1)+1 = 2^(n+1)-3，

最后移动最底下一个盘子，所以总的移动次数为：

K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5

开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖（移动圆片的次数）18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。

算法介绍

其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；

若n为奇数，按顺时针方向依次摆放 A C B。

（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。

（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。

（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

所以结果非常简单，就是按照移动规则向一个方向移动金片：

如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。

汉诺塔问题的程序实现

汉诺塔问题的递归实现

#include<stdio.h>

void hanoi(int n,char A,char B,char C)

{

if(n==1)

{

printf("Move disk %d from %c to %c\",n,A,C);

}

else

{

hanoi(n-1,A,C,B);

printf("Move disk %d from %c to %c\",n,A,C);

hanoi(n-1,B,A,C);

}

}

main()

{

int n;

printf("请输入数字n以解决n阶汉诺塔问题：\");

scanf("%d",&n);

hanoi(n,'A','B','C');

while(1){}

}

汉诺塔问题的非递归实现

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

//第0位置是柱子上的塔盘数目

int zhua[100]={0},zhub[100]={0},zhuc[100]={0};

char charis(char x,int n)

//左右字符出现顺序固定，且根据n值奇偶而不同

{

switch(x)

{

case 'A':

return (n%2==0)?'C':'B';

case 'B':

return (n%2==0)?'A':'C';

case 'C':

return (n%2==0)?'B':'A';

default:

return '0';

}

}

void print(char lch,char rch)

//打印字符

{

if(lch=='A')

{

switch(rch)

{

case 'B':

zhub[0]++;

zhub[zhub[0]]=zhua[zhua[0]];

zhua[zhua[0]]=0;

zhua[0]--;

break;

case 'C':

zhuc[0]++;

zhuc[zhuc[0]]=zhua[zhua[0]];

zhua[zhua[0]]=0;

zhua[0]--;

break;

default:

break;

}

}

if(lch=='B')

{

switch(rch)

{

case 'A':

zhua[0]++;

zhua[zhua[0]]=zhub[zhub[0]];

zhub[zhub[0]]=0;

zhub[0]--;

break;

case 'C':

zhuc[0]++;

zhuc[zhuc[0]]=zhub[zhub[0]];

zhub[zhub[0]]=0;

zhub[0]--;

break;

default:

break;

}

}

if(lch=='C')

{

switch(rch)

{

case 'A':

zhua[0]++;

zhua[zhua[0]]=zhuc[zhuc[0]];

zhuc[zhuc[0]]=0;

zhuc[0]--;

break;

case 'B':

zhub[0]++;

zhub[zhub[0]]=zhuc[zhuc[0]];

zhuc[zhuc[0]]=0;

zhuc[0]--;

break;

default:

break;

}

}

printf("\\t");

int i;

printf("(");

for(i=1;i<=zhua[0];i++)

printf(" %d ",zhua[i]);

printf(")");

printf("(");

for(i=1;i<=zhub[0];i++)

printf(" %d ",zhub[i]);

printf(")");

printf("(");

for(i=1;i<=zhuc[0];i++)

printf(" %d ",zhuc[i]);

printf(")");

printf("\");

}

void Hannuo(int n)

{

//分配2^n个空间

bool *isrev;

isrev=(bool *)malloc(sizeof(bool)*(int)pow(2,n));

for(int i=1;i<pow(2,n);i++)

isrev[i]=false;

//循环计算是否逆序

for(int ci=2;ci<=n;ci++)

{

for(int zixh=(int)pow(2,ci-1);zixh<pow(2,ci);zixh+=4)

//初始值重复一次，自增值可加4，减少循环次数。

isrev[zixh]=isrev[(int)pow(2,ci)-zixh];

//该位置为中间位置，且奇次幂逆序，偶数幂不逆序

isrev[(int)pow(2,ci)]=((ci-1)%2==0)?false:true;

}

char lch='A',rch;

rch=(n%2==0?'B':'C');

printf("%d\\t",1);

printf("%c->%c",lch,rch);

print(lch,rch);

for(int k=2;k<pow(2,n);k++)

{

if(k%2==0)

rch=charis(lch,n);

else

lch=charis(rch,n);

printf("%d\\t",k);

if(isrev[k])

{

printf("%c->%c",rch,lch);

print(rch,lch);

}

else

{

printf("%c->%c",lch,rch);

print(lch,rch);

}

}

}

int main()

{

int n;

printf("Input the num:");

scanf("%d",&n);

zhua[0]=n;for(int i=1;i<=n;i++)

zhua[i]=n-i+1;

Hannuo(n);

return 0;

}

汉诺塔问题的递归Java语言实现

public class Hanoi {/**

*

* @param n

* 盘子的数目

* @param origin

* 源座

* @param assist

* 辅助座

* @param destination

* 目的座

*/

public void hanoi(int n,char origin,char assist,char destination) {

if (n == 1) {

move(origin,destination);

} else {

hanoi(n - 1,origin,destination,assist);

move(origin,destination);

hanoi(n - 1,assist,origin,destination);

}

}

// Print the route of the movement

private void move(char origin,char destination) {

System.out.println("Direction:" + origin + "--->" + destination);

}

public static void main(String[] args) {

Hanoi hanoi = new Hanoi();

hanoi.hanoi(3,'A','B','C');

}

}

汉诺塔问题的递归pascal语言实现

var m:integer;

procedure move(getone,putone:char);

begin writeln(getone,'->',putone) end;

procedure hanoi(n:integer;one,two,three:char);

begin

if n=1 then move(one,three) else

begin

hanoi(n-1,one,three,two);

move(one,three);

hanoi(n-1,two,one,three)

end

end;

begin

readln(m);

write('the step to moving disks:');

writeln;

hanoi(m,'A','B','C')

end.

汉诺塔问题的递归易语言实现

子程序 汉诺塔盘子运动

.参数 盘子数，整数型

.参数 柱子甲，文本型

.参数 柱子乙，文本型

.参数 柱子丙，文本型

.如果 （盘子数 = 1)

' 如果只有一个盘，则直接将它从柱子一移动到柱子三

移动 (1，柱子甲，柱子丙）

.否则

' 把1 ~ n - 1个盘从柱子一移动到柱子二，用柱子三作为中转

汉诺塔盘子运动 （盘子数 － 1，柱子甲，柱子丙，柱子乙）

' 把第n个盘从柱子一移动到柱子三

移动 （盘子数，柱子甲，柱子丙）

' 把1 ~ n - 1个盘从柱子二移动到柱子三，用柱子一作为中转

汉诺塔盘子运动 （盘子数 － 1，柱子乙，柱子甲，柱子丙）

.如果结束

.子程序 移动

.参数 盘子号，整数型

.参数 甲柱子，文本型

.参数 乙柱子，文本型

路径 = 路径 + “步骤” + 到文本 （步骤） + “：” + “把” + 到文本 （盘子号） + “号圆盘从柱子 ” + 甲柱子 + “ 移动到” + 乙柱子 + “上 ” + #换行符

步骤 = 步骤 + 1

.子程序 _计算图形按钮_被单击

.局部变量 盘子总数，整数型

.局部变量 现在柱子，文本型

.局部变量 中间柱子，文本型

.局部变量 目标柱子，文本型

' 把盘子编辑框.内容传给现在柱子

现在柱子 = 盘子编辑框.内容

' 把中间编辑框.内容传给中间柱子

中间柱子 = 中间编辑框.内容

' 把目标编辑框.内容传给目标柱子

目标柱子 = 目标编辑框.内容

.如果真 （到数值 （现在柱子） ≤ 0 或 到数值 （中间柱子） ≤ 0 或 到数值 （目标柱子） ≤ 0 或 到数值 （个数编辑框.内容） ≤ 0 或 到数值 （个数编辑框.内容） > 10)

信息框 （“柱子或圆盘数量只能是大于0小于10的数字！”，#错误图标，“出现错误了：”）

返回 ()

.如果真结束

盘子总数 = 到数值 （个数编辑框.内容）

结果编辑框.内容 = “”

路径 = “”

' 首次调用汉诺塔盘子运动 （）程序

汉诺塔盘子运动 （盘子总数，现在柱子，中间柱子，目标柱子）

结果编辑框.内容 = 路径

步骤 = 1