汉诺塔.docx
- 文档编号:7292421
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:13
- 大小:39.14KB
汉诺塔.docx
《汉诺塔.docx》由会员分享,可在线阅读,更多相关《汉诺塔.docx(13页珍藏版)》请在冰点文库上搜索。
汉诺塔
汉诺塔
河内塔是根据一个传说形成的一个问题:
有三根杆子A,B,C。
A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。
要求按下列规则将所有圆盘移至C杆:
提示:
可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:
如何移?
最少要移动多少次?
基本介绍
有三根杆子A,B,C。
A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。
要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;大盘不能叠在小盘上面。
提示:
可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:
如何移?
最少要移动多少次?
汉诺塔是根据一个传说形成的一个问题:
有三根杆子A,B,C。
A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。
要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:
可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:
如何移?
最少要移动多少次?
历史传说
一位法国数学家曾编写过一个印度的古老传说:
在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。
不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:
一次只移动一片,不管在哪根针上,小片必须在大片上面。
僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。
这需要多少次移动呢?
这里需要递归的方法。
假设有n片,移动次数是f(n).显然f⑴=1,f⑵=3,f⑶=7,且f(k+1)=2*f(k)+1。
此后不难证明f(n)=2^n-1。
n=64时,
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
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');
while⑴{}
}
汉诺塔问题的非递归实现
#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语言实现 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'); } } 汉诺塔问题的递归pascal语言实现 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. 汉诺塔问题的递归易语言实现 子程序汉诺塔盘子运动 .参数盘子数,整数型 .参数柱子甲,文本型 .参数柱子乙,文本型 .参数柱子丙,文本型 .如果(盘子数=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文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汉诺塔