知道汉诺塔的进啊

发布网友发布时间：2022-04-26 00:37

共1个回答

热心网友时间：2023-10-25 08:31

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 此外，汉诺塔问题也是程序设计中的经典递归问题。算法思路： 1.如果只有一个金片，则把该金片从源移动到目标棒，结束。 2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒. 3.单纯对于有N个金片要挪动的步数求出, 可以使用递推方法,满足递推方程f(i) = f(i - 1) * 2 + 1. Hanoi塔问题一块板上有三根针，A，B，C。A针上套有64个大小不等的圆盘，大的在下，小的在上。如图5.4所示。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。本题算法分析如下，设A上有n个盘子。如果n=1，则将圆盘从A直接移动到C。如果n=2，则： 1.将A上的n-1(等于1)个圆盘移到B上； 2.再将A上的一个圆盘移到C上； 3.最后将B上的n-1(等于1)个圆盘移到C上。如果n=3，则： A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下： (1)将A上的n`-1(等于1)个圆盘移到C上。 (2)将A上的一个圆盘移到B。 (3)将C上的n`-1(等于1)个圆盘移到B。 B. 将A上的一个圆盘移到C。 C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下： (1)将B上的n`-1(等于1)个圆盘移到A。 (2)将B上的一个盘子移到C。 (3)将A上的n`-1(等于1)个圆盘移到C。到此，完成了三个圆盘的移动过程。从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：第一步把A上的n-1个圆盘移到B上；第二步把A上的一个圆盘移到C上；第三步把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。显然这是一个递归过程，

热心网友时间：2023-10-25 08:31