问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
你好,欢迎来到懂视!登录注册
当前位置: 首页 - 正文

汉诺塔问题公式是什么?

发布网友 发布时间:2022-04-30 15:39

我来回答

12个回答

热心网友 时间:2022-04-19 03:35

汉诺塔问题(又称河内塔问题)是根据一个传说形成的一个问题:

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

1. 每次只能移动一个圆盘;
2. 大盘不能叠在小盘上面。

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

问:如何移?最少要移动多少次?
一般取N=64。这样,最少需移动264-1次。即如果一秒钟能移动一块圆盘,仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为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("out.txt");

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');
fout.close();
cout<<"输出完毕!"<<endl;
return 0;
}

C语言精简算法
/* Copyrighter by SS7E */
#include<stdio.h> /* 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:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第几个数 }
write(hanoi(x));
end.

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

热心网友 时间:2022-04-19 04:53

这是一个古典的数学问题,是一个用递归方法解题的典型例子.
问题是这样的:古代有一个梵塔,塔内有3个座A,B,C,开始时A座上有n个盘子,盘子大小不等,大的在下,小的在上.有一个老和尚想把这n个盘子从A座移到C座,但每次只允许移动一个盘,且在移动过程中在3个座上都始终保持大盘在下,小盘在上.在移动过程中可以利用B座.
将n个盘子从A座移动到C座可以分解为以下3个步骤:
1.将A上n-1个盘借助C座先移到B座上
2.把A座上剩下的一个盘移动到C座上
3.将n-1个盘从B座借助于A座移动到C座上
上面第1步和第3步,都是把n-1个盘从一个座移到另一个座上,采取的办法是一样的,只是座的名字不同而已.为使之一般化,可以将第1步和第3步表示为: 将"one"座上n-1个盘移到"two"座(借助three座).只是在第1步和第3步中,one,two,three和A,B,C的对应关系不同.对第1步,对应关系是one---A,two---B,three---C.对第3步是:one---B,two---C,three---A.
因此,可以把上面3个步骤分成两类操作:
1.将n-1个盘从一个座移到另一个座上(n>1).
2.将1个盘子从一个座上移到另一个座上.

下面是用C语言实现的代码:
用hanoi函数实现上面第1类操作,用move函数实现上面第2类操作,函数调用hanoi(n,one,two,three)表示将n个盘子从"one"座移到"three"座的过程(借助"two"座).函数调用move(x,y)表示将1个盘子从x座移到y座的过程.x和y是代表A,B,C座之一,根据每次不同情况分别取A,B,C代入.
程序:
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
void hanoi(int n,char one,char two,char three)
/*将n个盘从one座借助two座,移到three座*/
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main()
{
int m;
printf("input the number of diskes:");
scanf("%d",&m);
printf("The step to moving %3d diskes:\n",m);
hanoi(m,'A','B','C');
}

另外补充说一句:移动n个盘子要经历2∧n-1步.如移4个盘子经历15步

热心网友 时间:2022-04-19 06:28

付费内容限时免费查看回答亲亲,上午好呀,答案已经为您整理好了呢:汉诺塔的通项公式递推公式: H(k)=2H(k-1)+1。 通项公式(有n个圆盘,全部完成需要的次数):sum=2^n-1。

汉诺塔问题的递推公式:M(n)=2M(N-1)+1=2N-1;从汉诺塔问题的解法看出来,它是将输入规模为n的问题变成了一个输入规模为2N的问题,从道理上看,它是将原来输入规模扩大了,而不是减少了,所以问题的解题时间为2n。

热心网友 时间:2022-04-19 08:19

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

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');
fout.close();
cout<<"输出完毕!"<<endl;
return 0;
}

C语言精简算法
/* Copyrighter by SS7E */
#include<stdio.h> /* 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 */

热心网友 时间:2022-04-19 10:27

汉诺塔问题(又称河内塔问题)是根据一个传说形成的一个问题:

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

1. 每次只能移动一个圆盘;
2. 大盘不能叠在小盘上面。

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

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

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

热心网友 时间:2022-04-19 12:52

先看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("out.txt");

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');
fout.close();
cout<<"输出完毕!"<<endl;
return 0;
}

C语言精简算法
/* Copyrighter by SS7E */
#include<stdio.h> /* 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:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第几个数 }
write(hanoi(x));
end.

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

热心网友 时间:2022-04-19 15:33

汉诺塔问题的非递归非堆栈算法(一)
#i nclude <iostream.h>
#i nclude <math.h>
#define maxno 10000
int step_d,step_s,no;//定义将要行进的步数
void main()
{
cout<<"请输入数字(1-64):";
cin>>no;//获取实际的塔片数
//初始化

int **p=new int*[3];

p[0]=new int[no+1];

p[1]=new int[no+1];

p[2]=new int[no+1];
p[0][0]=maxno;p[1][0]=maxno;p[2][0]=maxno;
for(int count=1;count<=no;count++)
{
p[0][count]=no-count+1;
p[1][count]=0;
p[2][count]=0;
}
//初始化完毕
if(fmod(no,2)){step_s=2;step_d=1;}else {step_s=1;step_d=2;}//判断奇数盘的步数和偶数盘的步数
int from,to;
from=0;
to=step_s+from;
p[0]=&p[0][no];
while(*(p[0]) != *(p[1]))
{
cout<<"从柱:"<<from+1<<" 到柱: "<<to+1<<endl;
*(++p[to])=*(p[from]);
*(p[from]--)=0;
//以下求得下一步将要From移动的柱子
switch(to)
{
case 2:
if(*(p[0]) < *(p[1]))from=0;else from=1;
break;
case 1:
if(*(p[0]) < *(p[2]))from=0;else from=2;
break;
case 0:
if(*(p[2]) < *(p[1]))from=2;else from=1;
break;
}
//以下一行求得下一步将要移动到的柱子
if(fmod(*(p[from]),2))to=fmod(from+step_s,3);else to=fmod(from+step_d,3);
}
char c;
cin>>c;
}

汉诺塔问题的非递归非堆栈算法(二)

前一种方法的/*原理:
如果把三个柱子围成一个环,盘子总数为N,其移动的规律是:
如果N为偶数:奇数号盘每次2步;偶数号盘每次1步;
如果N为奇数:奇数号盘每次1步;偶数号盘每次2步;
至于下一步该移动哪个柱子上的盘子,通过大小和顺序即可判断。

以上可以通过数学证明,不赘述!

热心网友 时间:2022-04-19 18:31

先看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柱上。这就是我们所需要的结果!

热心网友 时间:2022-04-19 21:46

A、B、C 3根针,A针自下而上由大到小套了N个环,目标是将所有环借助B或C移动到C或B,移动规则:一次一个环;大不压小。

汉诺塔算法
#include <stdio.h>

void hanoi(int n, char x, char y, char z)
{
if(n == 1)
{
printf("%c->%c\n",x,z);
}
else
{
hanoi(n-1, x, z, y);
printf("%c->%c\n",x,z);
hanoi(n-1, y, x, z);
}
}

void main()
{
int n;
printf("Input the height of the tower ...... \n");
scanf("%d",&n);
hanoi(n,'a','b','c');

热心网友 时间:2022-04-20 01:17

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

1. 每次只能移动一个圆盘;
2. 大盘不能叠在小盘上面。
我只知道这些

热心网友 时间:2022-04-20 05:05

2

热心网友 时间:2022-04-20 09:10

parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;

begin
read(x){第几个数 }
write(hanoi(x));
end.

思想就是:第N个就等于第n-1个乘以2+1次
声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。
E-MAIL:11247931@qq.com
貔貅请多少只 生活的滋味 写写你的生活实际 这个短文收到什么启发 阳光城并州府施工进度 狙击手幽灵战士契约2伪装所在地点位置分享介绍_狙击手幽灵战士契约2伪 ... 狙击手幽灵战士契约2弹药怎么搜集_狙击手幽灵战士契约2弹药怎么获得 《狙击手幽灵战士2》攻略图文详解(精准射击) 生产经营能力主要形式 每到节假日新华书店坐满了看书的人把坐满了看书的人写具体 三星4300提示墨粉用尽 生豆腐渣有营养吗?喂羊好吗? 汉诺塔有什么规律吗? 看图写话什么事让他们从此成了好朋友 如何玩八层的汉诺塔 我给跪了。。。 豆腐渣 可以用来加工什么? 汉诺塔问题通项公式 看图写话介绍你的朋友时应该从哪几个方面去介绍? 看图写话什么事情让他们成了好朋友? 手机摄像头原因信用卡App人脸识别不过怎么办 在哪看围棋直播啊?没电视啊 豆腐渣是什么食品厂出的? 看图写话朋友圈怎么发 江苏农商银行人脸识别不能通过怎么办 汉诺塔的规律是什么? 重庆度小满金融贷款可靠不可靠? 描写好朋友王艺萌的看图写话 从药店买回来的决明子,可以直接泡茶喝吗 一年级看图写话芳芳邀请好朋友到她家做客 汉诺塔8层口诀规律是什么? 德诚无人机新手玩家需要注意点什么? 好朋友帮我想一想,这个看图写话200个字,这么写。写一写,谢谢 豆渣能喂小鹅吗? 怎么修改第二次? 怎么进行第二次修改 怎么进行第二次修改呢? 电极式暖宝宝和电热丝式暖宝宝有啥不同 怎么改第二次? 怎么修改第二次 百度经验 暖宝宝贴的可以和电热毯一起使用吗 怎么改第二次 冬天天寒地冻,取暖器、暖宝宝、电热毯等这些取暖神器孕妈妈都能用吗? 暖宝宝为什么撕开才发热? 在快手里我取消了一些我所关注的人,接着粉丝掉了很多。取消关注有影响吗?为什么粉丝掉了那么 有首歌曲里面有句歌词是 什么就算全世界 什么什么与你为敌人的那是什么歌女的唱的 今天刚下载完正版gta5然后进入游戏,然后就正在加载中,之后就黑屏了,连游戏都没能进去 gta5进不了游戏,先是正在加载,然后就黑屏,一直黑屏没反应 我女朋友说全世界为她为敌我该怎么回答? GTA5序章黑屏无限载入如何解决 怎么了,好像全世界都与我为敌 云班课误点作业结束,如何才能批阅?
  • 焦点

最新推荐

猜你喜欢

热门推荐