| 词条 | 汉诺塔 |
| 释义 | 汉诺塔问题是现代递归算法思想的来源，是一个很经典的问题。 汉诺塔 - 问题起源 汉诺塔问题 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果恰如上题，面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。 汉诺塔 - 汉诺塔游戏 后来，这个传说就演变为汉诺塔游戏: 3个盘子的汉诺塔问题解决过程图解 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片： 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 此外，汉诺塔问题也是程序设计中的经典递归问题。 对于汉诺塔问题的求解，可以通过以下三个步骤实现： ⑴将塔A上的n-1个碟子借助塔C先移到塔B上。 ⑵把塔A上剩下的一个碟子移到塔C上。 ⑶将n-1个碟子从塔B借助塔A移到塔C上。 汉诺塔 - 解决思路 1.如果只有一个金片，则把该金片从源移动到目标棒，结束。 2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒 汉诺塔 - 算法实现 C++语言算法实现 #include #include usingnamespacestd; ofstreamfout("out.txt"); voidMove(intn,charx,chary) { fout<<"把"<<<"号从"<<<"挪动到"<< } voidHannoi(intn,chara,charb,charc) { if(n==1) Move(1,a,c); else { Hannoi(n-1,a,c,b); Move(n,a,c); Hannoi(n-1,b,a,c); } } intmain() { fout<<"以下是7层汉诺塔的解法:"< Hannoi(7,'a','b','c'); fout.close(); cout<<"输出完毕！"< return0; } C语言精简算法 /*CopyrighterbySS7E*/ #include/*CopyrighterbySS7E*/ voidhanoi(intn,charA,charB,charC)/*CopyrighterbySS7E*/ { if(n==1) { printf("Movedisk%dfrom%cto%c\",n,A,C); } else { hanoi(n-1,A,C,B);/*CopyrighterbySS7E*/ printf("Movedisk%dfrom%cto%c\",n,A,C); hanoi(n-1,B,A,C);/*CopyrighterbySS7E*/ } } main()/*CopyrighterbySS7E*/ { intn; printf("请输入数字n以解决n阶汉诺塔问题：\"); scanf("%d",&n); hanoi(n,'A','B','C'); }/*CopyrighterbySS7E*/ JAVA算法： publicclassHaniojava { publicstaticvoidmain(Stringargs[]) { byten=2; chara='A',b='B',c='C'; hanio(n,a,b,c); } publicstaticvoidhanio(byten,chara,charb,charc) { if(n==1) System.out.println("move"+a+"to"+b); else { hanio((byte)(n-1),a,c,b); System.out.println("move"+a+"to"+b); hanio((byte)(n-1),c,b,a); } } } 汉诺塔 - 算法复杂度分析 n个金片的汉诺塔问题需要移动的金片数是n-1个金片的汉诺塔问题需要移动的金片数的2倍再加1。因此： 汉诺塔 因此，要完成64个金片的汉诺塔问题，需要移动的金片数为： 汉诺塔 如果每秒移动一次，一年有31,536,000秒，则僧侣们一刻不停地来回移动，也需要花费5849亿年的时间；假定计算机以每秒1000万个金片的速度进行移动，则需要花费58,490年的时间。 汉诺塔问题说明了理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。通常将可以在多项式时间内求解的问题看作是易解问题，这类问题在可以接受的时间内实现问题求解，将需要指数时间求解的问题看作是难解问题，这类问题的计算时间随着问题规模的增长而快速增长，即使中等规模的输入，其计算时间也是以世纪来衡量的。 汉诺塔 - 参考资料 1.http://baike.baidu.com/view/191666.htm 2.http://jsj.ccut.edu.cn/sjjg/index.php?option=com_content&task=view&id=649&Itemid=1 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。