汉诺塔Word下载.docx
- 文档编号:8374412
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:13
- 大小:39.14KB
汉诺塔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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汉诺塔