汉诺塔Word下载.docx
《汉诺塔Word下载.docx》由会员分享，可在线阅读，更多相关《汉诺塔Word下载.docx（13页珍藏版）》请在冰点文库上搜索。
f（64）=2^64-1=184********709551615
假如每秒钟一次，共需多长时间呢？
一个平年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
和移完汉诺塔的次数一样。
我们已经知道这个数字有多么大了。
人们估计，全世界两千年也难以生产这么多麦子！
concreteHAM
现在有三根相邻的柱子，标号为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个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
计算结果非常恐怖（移动圆片的次数）184********709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。
算法介绍
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n–1（有兴趣的可以自己证明试试看）。
后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：
若n为偶数，按顺时针方向依次摆放ABC；
若n为奇数，按顺时针方向依次摆放ACB。
⑴按顺时针方向把圆盘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
汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。
汉诺塔问题的程序实现
汉诺塔问题的递归实现
#include<
stdio.h>
voidhanoi（intn,charA,charB,charC）
{
if（n==1）
printf（"
Movedisk%dfrom%cto%c\n"
n,A,C）;
}
else
hanoi（n-1,A,C,B）;
hanoi（n-1,B,A,C）;
main（）
intn;
请输入数字n以解决n阶汉诺塔问题：
\n"
）;
scanf（"
%d"
&
n）;
hanoi（n,'
A'
'
B'
C'
while⑴{}
汉诺塔问题的非递归实现
#include<
math.h>
stdlib.h>
//第0位置是柱子上的塔盘数目
intzhua[100]={0},zhub[100]={0},zhuc[100]={0};
charcharis（charx,intn）
//左右字符出现顺序固定，且根据n值奇偶而不同
switch（x）
case'
:
return（n%2==0）?
'
;
default:
return'
0'
voidprint（charlch,charrch）
//打印字符
if（lch=='
）
switch（rch）
zhub[0]++;
zhub[zhub[0]]=zhua[zhua[0]];
zhua[zhua[0]]=0;
zhua[0]--;
break;
zhuc[0]++;
zhuc[zhuc[0]]=zhua[zhua[0]];
zhua[0]++;
zhua[zhua[0]]=zhub[zhub[0]];
zhub[zhub[0]]=0;
zhub[0]--;
zhuc[zhuc[0]]=zhub[zhub[0]];
zhua[zhua[0]]=zhuc[zhuc[0]];
zhuc[zhuc[0]]=0;
zhuc[0]--;
zhub[zhub[0]]=zhuc[zhuc[0]];
\t"
inti;
（"
for（i=1;
i<
=zhua[0];
i++）
%d"
zhua[i]）;
）"
=zhub[0];
zhub[i]）;
=zhuc[0];
zhuc[i]）;
voidHannuo（intn）
//分配2^n个空间
bool*isrev;
isrev=（bool*）malloc（sizeof（bool）*（int）pow（2,n））;
for（inti=1;
pow（2,n）;
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='
rch;
rch=（n%2==0?
%d\t"
1）；
%c->
%c"
lch,rch）;
print（lch,rch）;
for（intk=2;
k<
k++）
if（k%2==0）
rch=charis（lch,n）;
lch=charis（rch,n）;
k）;
if（isrev[k]）
rch,lch）;
print（rch,lch）;
intmain（）
Inputthenum:
"
zhua[0]=n;
for（inti=1;
zhua[i]=n-i+1;
Hannuo（n）;
return0;
汉诺塔问题的递归Java语言实现
publicclassHanoi{/**
*
*@paramn
*盘子的数目
*@paramorigin
*源座
*@paramassist
*辅助座
*@paramdestination
*目的座
*/
publicvoidhanoi（intn,charorigin,charassist,chardestination）{
if（n==1）{
move（origin,destination）;
}else{
hanoi（n-1,origin,destination,assist）;
hanoi（n-1,assist,origin,destination）;
//Printtherouteofthemovement
privatevoidmove（charorigin,chardestination）{
System.out.println（"
Direction:
+origin+"
--->
+destination）;
publicstaticvoidmain（String[]args）{
Hanoihanoi=newHanoi（）;
hanoi.hanoi（3,'
汉诺塔问题的递归pascal语言实现
varm:
integer;
proceduremove（getone,putone:
char）;
beginwriteln（getone,'
->
putone）end;
procedurehanoi（n:
one,two,three:
begin
ifn=1thenmove（one,three）else
hanoi（n-1,one,three,two）;
move（one,three）;
hanoi（n-1,two,one,three）
end
end;
readln（m）;
write（'
thesteptomovingdisks:
writeln;
hanoi（m,'
end.
汉诺塔问题的递归易语言实现
子程序汉诺塔盘子运动
.参数盘子数，整数型
.参数柱子甲，文本型
.参数柱子乙，文本型
.参数柱子丙，文本型
.如果（盘子数=1）
'
如果只有一个盘，则直接将它从柱子一移动到柱子三
移动（1，柱子甲，柱子丙）
.否则
把1~n-1个盘从柱子一移动到柱子二，用柱子三作为中转
汉诺塔盘子运动（盘子数－1，柱子甲，柱子丙，柱子乙）
把第n个盘从柱子一移动到柱子三
移动（盘子数，柱子甲，柱子丙）
把1~n-1个盘从柱子二移动到柱子三，用柱子一作为中转
汉诺塔盘子运动（盘子数－1，柱子乙，柱子甲，柱子丙）
.如果结束
.子程序移动
.参数盘子号，整数型
.参数甲柱子，文本型
.参数乙柱子，文本型
路径=路径+“步骤”+到文本（步骤）+“：
”+“把”+到文本（盘子号）+“号圆盘从柱子”+甲柱子+“移动到”+乙柱子+“上”+#换行符
步骤=步骤+1
.子程序_计算图形按钮_被单击
.局部变量盘子总数，整数型
.局部变量现在柱子，文本型
.局部变量中间柱子，文本型
.局部变量目标柱子，文本型
把盘子编辑框.内容传给现在柱子
现在柱子=盘子编辑框.内容
把中间编辑框.内容传给中间柱子
中间柱子=中间编辑框.内容
把目标编辑框.内容传给目标柱子
目标柱子=目标编辑框.内容
.如果真（到数值（现在柱子）≤0或到数值（中间柱子）≤0或到数值（目标柱子）≤0或到数值（个数编辑框.内容）≤0或到数值（个数编辑框.内容）>
10）
信息框（“柱子或圆盘数量只能是大于0小于10的数字！
”，#错误图标，“出现错误了：
”）
返回（）
.如果真结束
盘子总数=到数值（个数编辑框.内容）
结果编辑框.内容=“”
路径=“”
首次调用汉诺塔盘子运动（）程序
汉诺塔盘子运动（盘子总数，现在柱子，中间柱子，目标柱子）
结果编辑框.内容=路径
步骤=1
升级会员 