汉诺塔问题.docx
《汉诺塔问题.docx》由会员分享，可在线阅读，更多相关《汉诺塔问题.docx（20页珍藏版）》请在冰点文库上搜索。
汉诺塔问题
汉诺塔
百科名片
汉诺塔初始状态
汉诺塔：
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。
上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
目录
由来
1.来源
2.传说
3.预言
汉诺塔与宇宙寿命
concreteHAM：
1.在分析
（2）之前
2.讨论问题
（2），
3.算法介绍：
汉诺塔问题的程序实现
1.汉诺塔问题的递归实现：
2.汉诺塔问题的非递归实现
3.汉诺塔问题的递归Java语言实现
4.汉诺塔问题的递归pascal语言实现
由来
1.来源
2.传说
3.预言
汉诺塔与宇宙寿命
concreteHAM：
1.在分析
（2）之前
2.讨论问题
（2），
3.算法介绍：
汉诺塔问题的程序实现
1.汉诺塔问题的递归实现：
2.汉诺塔问题的非递归实现
3.汉诺塔问题的递归Java语言实现
4.汉诺塔问题的递归pascal语言实现
展开
编辑本段由来
来源
汉诺塔是源自印度神话里的玩具。
上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着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^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个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
计算结果非常恐怖（移动圆片的次数）184********709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍：
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n–1（有兴趣的可以自己证明试试看）。
后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：
若n为偶数，按顺时针方向依次摆放ABC；
若n为奇数，按顺时针方向依次摆放ACB。
（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
voidhanoi（intn,charA,charB,charC）
{
if（n==1）
{
printf（"Movedisk%dfrom%cto%c\n",n,A,C）;
}
else
{
hanoi（n-1,A,C,B）;
printf（"Movedisk%dfrom%cto%c\n",n,A,C）;
hanoi（n-1,B,A,C）;
}
}
main（）
{
intn;
printf（"请输入数字n以解决n阶汉诺塔问题：
\n"）;
scanf（"%d",&n）;
hanoi（n,'A','B','C'）;
}
●汉诺塔算法的非递归实现C++源代码
#include
usingnamespacestd;
//圆盘的个数最多为64
constintMAX=64;
//用来表示每根柱子的信息
structst{
ints[MAX];//柱子上的圆盘存储情况
inttop;//栈顶，用来最上面的圆盘
charname;//柱子的名字，可以是A，B，C中的一个
intTop（）//取栈顶元素
{
returns[top];
}
intPop（）//出栈
{
returns[top--];
}
voidPush（intx）//入栈
{
s[++top]=x;
}
};
longPow（intx,inty）;//计算x^y
voidCreat（stta[],intn）;//给结构数组设置初值
voidHannuota（stta[],longmax）;//移动汉诺塔的主要函数
intmain（void）
{
intn;
cin>>n;//输入圆盘的个数
stta[3];//三根柱子的信息用结构数组存储
Creat（ta,n）;//给结构数组设置初值
longmax=Pow（2,n）-1;//动的次数应等于2^n-1
Hannuota（ta,max）;//移动汉诺塔的主要函数
system（"pause"）;
return0;
}
voidCreat（stta[],intn）
{
ta[0].name='A';
ta[0].top=n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
for（inti=0;i ta[0].s[i]=n-i;
//柱子B，C上开始没有没有圆盘
ta[1].top=ta[2].top=0;
for（inti=0;i ta[1].s[i]=ta[2].s[i]=0;
//若n为偶数，按顺时针方向依次摆放ABC
if（n%2==0）
{
ta[1].name='B';
ta[2].name='C';
}
else//若n为奇数，按顺时针方向依次摆放ACB
{
ta[1].name='C';
ta[2].name='B';
}
}
longPow（intx,inty）
{
longsum=1;
for（inti=0;i sum*=x;
returnsum;
}
voidHannuota（stta[],longmax）
{
intk=0;//累计移动的次数
inti=0;
intch;
while（k {
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch=ta[i%3].Pop（）;
ta[（i+1）%3].Push（ch）;
cout<<++k<<":
"<<
"Movedisk"< "to"< i++;
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if（k {//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if（ta[（i+1）%3].Top（）==0||
ta[（i-1）%3].Top（）>0&&
ta[（i+1）%3].Top（）>ta[（i-1）%3].Top（））
{
ch=ta[（i-1）%3].Pop（）;
ta[（i+1）%3].Push（ch）;
cout<<++k<<":
"<<"Movedisk"
< <<"to"< }
else
{
ch=ta[（i+1）%3].Pop（）;
ta[（i-1）%3].Push（ch）;
cout<<++k<<":
"<<"Movedisk"
< <<"to"< }
}
}
}
汉诺塔问题的非递归实现
#include
#include
#include
//第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 isrev[i]=false;
//循环计算是否逆序
for（intci=2;ci<=n;ci++）
{
for（intzixh=（int）pow（2,ci-1）;zixh //初始值重复一次，自增值可加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 {
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;
}
汉诺塔
汉诺塔问题的递归Java语言实现
importjava.util.Scanner;
publicclassHanoiTest{
publicstaticvoidhanoi（intlevel,String
升级会员 