汉诺塔问题用什么方法解决?

cmaedu.com汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒。

第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。

面对庞大的数字(移动圆片的次数)18446744073709551615(2^64-1)，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

cmaedu.com相关信息

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

人教版四年级数学上册120页河内塔问题的规律是什么?

趣味数学——河内塔问题趣味数学——河内塔问题

cmaedu.com 如在四年级数学上册120页有这样的思考题：

cmaedu.com 1.有三根杆子1.2.3.A杆上有若干碟子

2.每次移动一块碟子,小的只能叠在大的上面

cmaedu.com 3.把所有碟子从1杆全部移到3杆上

经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片：

cmaedu.com 如3阶汉诺塔的移动：1→3,1→2,3→2,1→3,2→1,2→3,1→3

cmaedu.com

“河内塔问题”的解法

汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：

cmaedu.com有三根杆子A，B，C。A杆上有N个(N1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘；

2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须尊循上述两条规则。

问：如何移？最少要移动多少次？

cmaedu.com一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测，宇宙的年龄仅为137亿年。

cmaedu.com在真实玩具中，一般N=8；这将需移动255次。如果N=10，需移动1023次。如果N=15，需移动32767次；这就是说，如果一个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如果N=20，需移动1048575次，即超过了一百万次。

先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意，这里one柱或three柱到底是A、B还是C并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为：

one =》three

再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是：

one =》two

one =》three

two =》three

很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。

cmaedu.com再看hanoi(3, one, two, three)的情况。分析

hanoi(2, one , three, two)

one =》three

cmaedu.comhanoi(2, two, one, three)

cmaedu.com即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？

cmaedu.com运用归纳法可知，对任意n，

cmaedu.comhanoi(n-1, one , three, two)

one =》three

cmaedu.comhanoi(n-1, two, one, three)

就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！

cmaedu.com回答者：wuchenghua121 - 经理 四级 12-5 11:51

cmaedu.com汉诺塔

cmaedu.com汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

cmaedu.com后来，这个传说就演变为汉诺塔游戏:

1.有三根杆子A,B,C。A杆上有若干碟子

cmaedu.com2.每次移动一块碟子,小的只能叠在大的上面

cmaedu.com3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：

cmaedu.com如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

cmaedu.com补充：汉诺塔的算法实现（c++）

cmaedu.com#include fstream

cmaedu.com#include iostream

using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)

fout"把"n"号从"x"挪动到"yendl;

void Hannoi(int n,char a,char b,char c)

cmaedu.comif(n==1)

Move(1,a,c);

cmaedu.comelse

Hannoi(n-1,a,c,b);

cmaedu.comMove(n,a,c);

cmaedu.comHannoi(n-1,b,a,c);

cmaedu.comint main()

cmaedu.comfout"以下是7层汉诺塔的解法:"endl;

cmaedu.comHannoi(7,'a','b','c');

cmaedu.comfout.close();

cmaedu.comcout"输出完毕！"endl;

return 0;

C语言精简算法

/* Copyrighter by SS7E */

cmaedu.com#includestdio.h /* Copyrighter by SS7E */

void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */

cmaedu.comif(n==1)

cmaedu.comprintf("Move disk %d from %c to %c\n",n,A,C);

else

cmaedu.comhanoi(n-1,A,C,B); /* Copyrighter by SS7E */

cmaedu.comprintf("Move disk %d from %c to %c\n",n,A,C);

hanoi(n-1,B,A,C); /* Copyrighter by SS7E */

main() /* Copyrighter by SS7E */

cmaedu.comint n;

cmaedu.comprintf("请输入数字n以解决n阶汉诺塔问题：\n");

cmaedu.comscanf("%d",n);

hanoi(n,'A','B','C');

}/* Copyrighter by SS7E */

cmaedu.com回答者： Vanquisher_ - 举人 五级 12-5 13:57

cmaedu.comparcel::::::::::

cmaedu.comprogram hanoi;

functionhanoi(x:integer):longint;

begin

if x=1 then hanoi:=1;

cmaedu.comif x=2 then hanoi:=3;

cmaedu.comelse

cmaedu.combegin

cmaedu.comhanoi:=2*hanoi(x-1)+1;

end;

cmaedu.comend;

cmaedu.combegin

cmaedu.comread(x){第几个数 }

write(hanoi(x));

end.

cmaedu.com思想就是：第N个就等于第n-1个乘以2+1次