河内塔游戏

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

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

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

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

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

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

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

在真实玩具中，一般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柱上。

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

hanoi(2, one , three, two)

one =》three

hanoi(2, two, one, three)

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

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

hanoi(n-1, one , three, two)

one =》three

hanoi(n-1, two, one, three)

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

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

汉诺塔

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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

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

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

#include <fstream>

#include <iostream>

using namespace std;

ofstream fout("outtxt");

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

{

fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;

}

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

{

if(n==1)

Move(1,a,c);

else

{

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

Move(n,a,c);

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

}

}

int main()

{

fout<<"以下是7层汉诺塔的解法:"<<endl;

Hannoi(7,'a','b','c');

foutclose();

cout<<"输出完毕！"<<endl;

return 0;

}

C语言精简算法

/ Copyrighter by SS7E /

#include<stdioh> / Copyrighter by SS7E /

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

{

if(n==1)

{

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

}

else

{

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

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

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

}

}

main() / Copyrighter by SS7E /

{

int n;

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

scanf("%d",&n);

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

}/ Copyrighter by SS7E /

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

parcel::::::::::

program hanoi;

functionhanoi(x:integer):longint;

begin

if x=1 then hanoi:=1;

if x=2 then hanoi:=3;

else

begin

hanoi:=2hanoi(x-1)+1;

end;

end;

begin

read(x){第几个数 }

write(hanoi(x));

end

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

void Move(char chSour, char chDest)

{

/打印移动步骤/

printf("\nMove the top plate of %c to %c",chSour, chDest);

}

Hanoi(int n, char chA, char chB, char chC)

{

/检查当前的盘子数量是否为1/

if(n==1) /盘子数量为1，打印结果后，不再继续进行递归/

Move(chA,chC);

else/盘子数量大于1，继续进行递归过程/

{

Hanoi(n-1,chA,chC,chB);

Move(chA,chC);

Hanoi(n-1,chB,chA,chC);

}

}

main()

{

int n;

/输入盘子的数量/

printf("\nPlease input number of the plates: ");

scanf("%d",&n);

printf("\nMoving %d plates from A to C:",n);

/调用函数计算，并打印输出结果/

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

}

这是基本算法

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

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

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

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

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

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

在真实玩具中，一般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柱上。

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

hanoi(2, one , three, two)

one =》three

hanoi(2, two, one, three)

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

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

hanoi(n-1, one , three, two)

one =》three

hanoi(n-1, two, one, three)

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

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

汉诺塔

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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

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

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

#include <fstream>

#include <iostream>

using namespace std;

ofstream fout("outtxt");

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

{

fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;

}

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

{

if(n==1)

Move(1,a,c);

else

{

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

Move(n,a,c);

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

}

}

int main()

{

fout<<"以下是7层汉诺塔的解法:"<<endl;

Hannoi(7,'a','b','c');

foutclose();

cout<<"输出完毕！"<<endl;

return 0;

}

C语言精简算法

/ Copyrighter by SS7E /

#include<stdioh> / Copyrighter by SS7E /

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

{

if(n==1)

{

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

}

else

{

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

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

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

}

}

main() / Copyrighter by SS7E /

{

int n;

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

scanf("%d",&n);

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

}/ Copyrighter by SS7E /

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

parcel::::::::::

program hanoi;

functionhanoi(x:integer):longint;

begin

if x=1 then hanoi:=1;

if x=2 then hanoi:=3;

else

begin

hanoi:=2hanoi(x-1)+1;

end;

end;

begin

read(x){第几个数 }

write(hanoi(x));

end

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

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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个移动到目标棒

(非专业人士可以忽略以下内容)

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

#include <fstream>

#include <iostream>

using namespace std;

ofstream fout("outtxt");

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

{

fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;

}

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

{

if(n==1)

Move(1,a,c);

else

{

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

Move(n,a,c);

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

}

}

int main()

{

fout<<"以下是7层汉诺塔的解法:"<<endl;

Hannoi(7,'a','b','c');

foutclose();

cout<<"输出完毕！"<<endl;

return 0;

}

C语言精简算法

/ Copyrighter by SS7E /

#include<stdioh> / Copyrighter by SS7E /

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

{

if(n==1)

{

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

}

else

{

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

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

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

}

}

main() / Copyrighter by SS7E /

{

int n;

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

scanf("%d",&n);

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

}/ Copyrighter by SS7E /

PHP算法：

<php

function hanoi($n,$x,$y,$z){

if($n==1){

move($x,1,$z);

}else{

hanoi($n-1,$x,$z,$y);

move($x,$n,$z);

hanoi($n-1,$y,$x,$z);

}

}

function move($x,$n,$z){

echo 'move disk '$n' from '$x' to '$z'<br>';

}

hanoi(10,'x','y','z');

>

JAVA算法：

public class Haniojava

{

public static void main(String args[])

{

byte n=2;

char a='A',b='B',c='C';

hanio(n,a,b,c);

}

public static void hanio(byte n,char a,char b,char c)

{

if(n==1)

Systemoutprintln("move "+a+" to "+b);

else

{

hanio((byte)(n-1),a,c,b);

Systemoutprintln("move "+a+" to "+b);

hanio((byte)(n-1),c,b,a);

}

}

}

#include<iostreamh>

void move(char ch1, char ch2) {

cout<<ch1<<"->"<<ch2<<' ';

}

void hanoi(int n, char a, char b, char c) {

if (n==1)

move (a,c);

else {

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

move (a,c);

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

}

}

void main() {

int m;

cout<<"Enter the number of disk to move:\n";

cin>>m;

cout<<"The step to moving "<<m<<" disk:\n";

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

cin>>m;

}

用不了这么复杂

，设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。 显然这是一个递归过程，据此算法可编程如下：

move(int n,int x,int y,int z)

{

if(n==1)

printf("%c-->%c\n",x,z);

else

{

move(n-1,x,z,y);

printf("%c-->%c\n",x,z);

move(n-1,y,x,z);

}

}

main()

{

int h;

printf("\ninput number:\n");

scanf("%d",&h);

printf("the step to moving %2d diskes:\n",h);

move(h,'a','b','c');

}

以上就是关于河内塔游戏全部的内容，包括:河内塔游戏、C语言题——汉诺塔问题、汉诺塔问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！