- 汉诺塔
汉诺塔
发展历程
名字由来
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的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时，
假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：
汉诺塔18446744073709551615秒
这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
印度传说
和汉诺塔故事相似的，还有另外一个印度传说：舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。
那么，宰相要求得到的麦粒到底有多少呢？总数为
1+2+2^2 + … +2^63=2^64-1
等于移完汉诺塔所需的步骤数。我们已经知道这个数字有多么大了。人们估计，全世界两千年也难以生产这么多麦子！
相关预言
有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
玩法介绍
最简单的汉诺塔是由三个木桩（塔）和n个具有一定大小梯度的圆盘构成。圆盘中心有孔，使它们能够从下往上依次由最大到最小的顺序堆叠在其中一个木桩（塔）上。
汉诺塔的玩法是将一个木桩上的圆盘转移到另外一个木桩。移动规则：1、一次只能移动一个圆盘；2、每个桩上只有最顶层的圆盘可以移动，并且所移动的圆盘只能移到空木桩上或者它要比木桩顶层已存在的圆盘小。也就是说，您不能将大圆盘置于小圆盘之上。常见的汉诺塔n=6~10，完成转移需要2n-1步。[1]
相关信息
宇宙寿命
如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什么时候呢？
让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了
因此让我们逻辑性的思考一下吧。
3个的时候能够移动最大的3盘时如图所示。
汉诺塔到此为止用了7次。
接下来如右图，在上面再放上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到底有多大呢？动动计算器，答案是一个二十位的数字约是
1.84467440*10^19
用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。
太阳及其行星形成于50亿年前，其寿命约为100亿年。
经典题目
汉诺塔(3)有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。
首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们得出表达式：
H⑴ = 1
H(n) = 2*H(n-1）+1 (n>1）
那么我们很快就能得到H(n）的一般式：
H(n) = 2^n - 1 (n>0)
并且这种方法的确是最少次数的，证明非常简单，可以尝试从2个盘子的移动开始证，你可以试试。
进一步加深问题（解法原创*_*）：
假如现在每种大小的盘子都有两个，并且是相邻的，设盘子个数为2n，问：⑴假如不考虑相同大小盘子的上下要多少次移动，设移动次数为J(n）；⑵只要保证到最后B上的相同大小盘子顺序与A上时相同，需要多少次移动，设移动次数为K(n）。
⑴中的移动相当于是把前一个问题中的每个盘子多移动一次，也就是：
J(n) = 2*H(n) = 2*（2^n - 1） = 2^(n+1）-2
在分析⑵之前
，我们来说明一个现象，假如A柱子上有两个大小相同的盘子，上面一个是黑色的，下面一个是白色的，我们把两个盘子移动到B上，需要两次，盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次，盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒。
现在回到最开始的问题，n个盘子移动，上方的n-1个盘子总移动次数为2*H(n-1），所以上方n-1个盘子的移动次数必定为偶数次，最后一个盘子移动次数为1次。
讨论问题⑵，
综上两点，可以得出，要把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个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖（移动圆片的次数）大约是1.84467440*10^19，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍
汉诺塔(3)其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。
程序实现
C语言
FORTRAN
汉诺塔问题的非递归实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<stdio.h> #include<windows.h> voidHanoi(intn,chara,charb,charc); voidMove(intn,chara,charb); intcount; intmain() { intn=8; printf("汉诺塔的层数:\n"); scanf("%d",&n); Hanoi(n,'A','B','C'); Sleep(20000); return0; } voidHanoi(intn,chara,charb,charc) { if(n==1) { Move(n,a,c); } else { Hanoi(n-1,a,c,b); Move(n,a,c); Hanoi(n-1,b,a,c); } } voidMove(intn,chara,charb) { count++; printf("第%d次移动Move%d:Movefrom%cto%c!\n",count,n,a,b); } |
汉诺塔
FORTRAN
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
CHANOILIST PROGRAMMAIN INTEGERN PRINT*,"ENTERTHEAMOUNTOFSTEP:" READ*,N CALLHANOI(N,'A','B','C') END RECURSIVESUBROUTINEHANOI(N,START,STATION,AIM) INTEGERN CHARACTER::START,STATION,AIM IF(N.EQ.1)THEN CALLMOVE(START,AIM) ELSE CALLHANOI(N-1,START,AIM,STATION) CALLMOVE(START,AIM) CALLHANOI(N-1,STATION,START,AIM) ENDIF ENDSUBROUTINE SUBROUTINEMOVE(START,AIM) CHARACTER::START,AIM PRINT*,START,"->",AIM ENDSUBROUTINE |
汉诺塔问题的非递归实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include<stdio.h> #include<math.h> #include<stdlib.h> //第0位置是柱子上的塔盘数目 intzhua[100]={0},zhub[100]={0},zhuc[100]={0}; charcharis(charx,intn) //左右字符出现顺序固定，且根据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'; } } voidprint(charlch,charrch) //打印字符 { 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"); inti; 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("\n"); } voidHannuo(intn) { //分配2^n个空间 bool*isrev; isrev=(bool*)malloc(sizeof(bool)*(int)pow（2,n)); for(inti=1;i<pow（2,n); i++) isrev[i]=false; //循环计算是否逆序 for(intci=2;ci<=n;ci++) { for(intzixh=(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; } charlch='A',rch; rch=(n%2==0?'B':'C'); printf("%d\t",1）； printf("%c->%c",lch,rch); print(lch,rch); for(intk=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); } } } intmain() { intn; printf("Inputthenum:"); scanf("%d",&n); zhua[0]=n; for(inti=1;i<=n;i++) zhua[i]=n-i+1; Hannuo(n); return0; } |
递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> usingnamespacestd; template<intn> voidhanoi(chara,charb,charc){ hanoi<n-1>(a,c,b); printf("%c->%c\n",a,c); hanoi<n-1>(b,a,c); } template<> voidhanoi<1>(chara,charb,charc){ printf("%c->%c\n",a,c); } //////////////////////////////////////////////// template<intn,chara,charb,charc> classhanoi1{ public: staticinthanoi(){ hanoi1<n-1,a,c,b>::hanoi(); printf("%c->%c\n",a,c); hanoi1<n-1,b,a,c>::hanoi(); } }; template<chara,charb,charc> classhanoi1<1,a,b,c>{ public: staticinthanoi(){ printf("%c->%c\n",a,c); } }; intmain(){ #defineN4 cout<<"类模板偏特化："; hanoi1<N,'A','B','C'>::hanoi(); cout<<endl; cout<<"函数模板全特化："; hanoi<3>('A','B','C'); exit(0); } |
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
usingSystem; classHANOI { privatestaticinttime=0; staticvoidMain(string[]args) { Hanoi(3,"x","y","z"); Console.WriteLine(time+"Times"); Console.ReadKey(); } publicstaticvoidHanoi(intn,stringx,stringy,stringz) { if(n==1) { Console.WriteLine(x+"--->"+z); time++; } else { Hanoi(n-1,x,z,y); Hanoi(1,x,y,z); Hanoi(n-1,y,x,z); } } } |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
publicclassHanoi{ /** * *@paramn盘子的数目 *@paramorigin源座 *@paramassist辅助座 *@paramdestination目的座 */ publicvoidhanoi(intn,charorigin,charassist,chardestination){ if(n==1){ move(origin,destination); }else{ hanoi(n-1,origin,destination,assist); move(origin,destination); hanoi(n-1,assist,origin,destination); } } //Printtherouteofthemovement privatevoidmove(charorigin,chardestination){ System.out.println("Direction:"+origin+"--->"+destination); } publicstaticvoidmain(String[]args){ Hanoihanoi=newHanoi(); hanoi.hanoi(3,'A','B','C'); } } |
php
简单的用php实现了汉诺塔问题的求解，使用递归调用，但是用php实现要是盘子的个数很多的话，运行起来会很慢的...
汉诺塔主要是有三个塔座X，Y，Z，要求将三个大小不同，依小到大编号为1，2.....n的圆盘从A移动到塔座Z上，要求
（1）：每次只能移动一个圆盘
（2）：圆盘可以插到X，Y，Z中任一塔座上
（3）：任何时候不能将一个较大的圆盘压在较小的圆盘之上
主要是运用了递归的思想，这里使用php做个简单的实现......
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
<?php functionhanoi($n,$x,$y,$z){ if($n==1){ move($x,1,$z); }else{ hanoi($n-1,$x,$z,$y); move($x,$n,$z); hanoi($n-1,$y,$x,$z); } } functionmove($x,$n,$z){ echo'movedisk'.$n.'from'.$x.'to'.$z.'<br>'; } hanoi(10,'x','y','z'); ?> |
易语言
汉诺塔(3)子程序 汉诺塔盘子运动
.参数 盘子数，整数型
.参数 柱子甲，文本型
.参数 柱子乙，文本型
.参数 柱子丙，文本型
.如果 （盘子数 = 1）
' 如果只有一个盘，则直接将它从柱子一移动到柱子三
移动 （1，柱子甲，柱子丙）
.否则
' 把1 ~ n - 1个盘从柱子一移动到柱子二，用柱子三作为中转
汉诺塔盘子运动 （盘子数 － 1，柱子甲，柱子丙，柱子乙）
' 把第n个盘从柱子一移动到柱子三
移动 （盘子数，柱子甲，柱子丙）
' 把1 ~ n - 1个盘从柱子二移动到柱子三，用柱子一作为中转
汉诺塔盘子运动 （盘子数 － 1，柱子乙，柱子甲，柱子丙）
.如果结束
.子程序 移动
.参数 盘子号，整数型
.参数 甲柱子，文本型
.参数 乙柱子，文本型
路径 = 路径 + “步骤” + 到文本 （步骤） + “：” + “把” + 到文本 （盘子号） + “号圆盘从柱子 ” + 甲柱子 + “ 移动到” + 乙柱子 + “上 ” + #换行符
步骤 = 步骤 + 1
.子程序 _计算图形按钮_被单击
.局部变量 盘子总数，整数型
.局部变量 现在柱子，文本型
易语言--hanoi.局部变量 中间柱子，文本型
.局部变量 目标柱子，文本型
' 把盘子编辑框.内容传给现在柱子
现在柱子 = 盘子编辑框.内容
' 把中间编辑框.内容传给中间柱子
中间柱子 = 中间编辑框.内容
' 把目标编辑框.内容传给目标柱子
目标柱子 = 目标编辑框.内容
.如果真 （到数值 （现在柱子） ≤ 0 或 到数值 （中间柱子） ≤ 0 或 到数值 （目标柱子） ≤ 0 或 到数值 （个数编辑框.内容） ≤ 0 或 到数值 （个数编辑框.内容） > 10）
信息框 （“柱子或圆盘数量只能是大于0小于10的数字！”，#错误图标，“出现错误了：”）
返回 ()
.如果真结束
盘子总数 = 到数值 （个数编辑框.内容）
结果编辑框.内容 = “”
路径 = “”
' 首次调用汉诺塔盘子运动 （）程序
汉诺塔盘子运动 （盘子总数，现在柱子，中间柱子，目标柱子）
结果编辑框.内容 = 路径
步骤 = 1
JavaScript
1 2 3 4 5 6 7 8 9 10 11 |
varhanoi=function(n,from,ass,to){ if(n>0){ hanoi(n-1,from,to,ass); move(n,from,to); hanoi(n-1,ass,from,to); } } varmove=function(n,from,to){ console.log("移动第"+n+"个从"+from+"到"+to); } hanoi(3,"A","B","C"); |
Python
1 2 3 4 5 6 7 8 9 |
defhanoi(n,a,b,c): ifn==1: print(a,'-->',c) else: hanoi(n-1,a,c,b) print(a,'-->',c) hanoi(n-1,b,a,c) #调用 hanoi(5,'A','B','C') |
pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
varm:integer; proceduremove(getone,putone:char); beginwriteln(getone,'->',putone)end; procedurehanoi(n:integer;one,two,three:char); begin ifn=1thenmove(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('thesteptomovingdisks:'); writeln; hanoi(m,'A','B','C') end. |
Lua
1 2 3 4 5 6 7 8 9 10 |
functionhanoi(num,a,b,c) if(num==1)then print(a.."-->"..c) else hanoi(num-1,a,c,b) print(a.."-->"..c) hanoi(num-1,b,a,c) end end hanoi(3,'A','B','C') |
荣誉奖项
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<stdio.h> #include<windows.h> voidHanoi(intn,chara,charb,charc); voidMove(intn,chara,charb); intcount; intmain() { intn=8; printf("汉诺塔的层数:\n"); scanf("%d",&n); Hanoi(n,'A','B','C'); Sleep(20000); return0; } voidHanoi(intn,chara,charb,charc) { if(n==1) { Move(n,a,c); } else { Hanoi(n-1,a,c,b); Move(n,a,c); Hanoi(n-1,b,a,c); } } voidMove(intn,chara,charb) { count++; printf("第%d次移动Move%d:Movefrom%cto%c!\n",count,n,a,b); } |
词条图册
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
CHANOILIST PROGRAMMAIN INTEGERN PRINT*,"ENTERTHEAMOUNTOFSTEP:" READ*,N CALLHANOI(N,'A','B','C') END RECURSIVESUBROUTINEHANOI(N,START,STATION,AIM) INTEGERN CHARACTER::START,STATION,AIM IF(N.EQ.1)THEN CALLMOVE(START,AIM) ELSE CALLHANOI(N-1,START,AIM,STATION) CALLMOVE(START,AIM) CALLHANOI(N-1,STATION,START,AIM) ENDIF ENDSUBROUTINE SUBROUTINEMOVE(START,AIM) CHARACTER::START,AIM PRINT*,START,"->",AIM ENDSUBROUTINE |
-
-
-
-
-
-
-
娜塔莉亚·波娃·薇丝塔
2025-09-28 06:57:23 查看详情 -
-
-
求购