汉诺塔问题公式是什么？ 如何推导汉诺塔的公式
有三根杆子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次
汉诺塔
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着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 */
这是一个古典的数学问题,是一个用递归方法解题的典型例子.
问题是这样的:古代有一个梵塔,塔内有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步
汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：
有三根杆子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次，即超过了一百万次。
汉诺塔问题的非递归非堆栈算法（一）
＃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步；
至于下一步该移动哪个柱子上的盘子，通过大小和顺序即可判断。
以上可以通过数学证明，不赘述！
如何推导汉诺塔的公式~
求汗诺塔N个盘子须几次移动时得到了下面的递推公式：
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
请教通项公式？
a[1] = 1;
a[n] = a[n-1] * 2 + 1;
可得a[i]= 2^i-1;
证明，采用数学归纳法：
1、猜想a[i]= 2^i-1
2、当i=1时，显然成立。
3、假设i=k时成立，即 a[k] = 2^k - 1;则：
由a[n] = a[n-1] * 2 - 1;得
a[k+1] = a[k] * 2 - 1
= 2^k * 2 - 1
= 2^(k-1) - 1
故得证。
同时：：
汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：
有三根杆子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
#include
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 /* 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,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c
",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("请输入数字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次
如果有n个盘的话，那么移动次数为 2的n次方-1
具体证明如下
对于一个单独的塔，可以进行以下操作：
1：将最下方的塔的上方的所有塔移动到过渡柱子
2：将底塔移动到目标柱子
3：将过渡柱子上的其他塔移动到目标柱子
可以归纳出第一步与第三步的步数是一样的，设为a
则总步数为2a+1
可以得到数列
An=2A(n-1)+1
最后可算得An是
2的n次方-1
相关要点总结：
18415289645：汉诺塔问题公式是什么?
袁呢答：汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问题：有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：1. 每次只能移动一个圆盘；2. 大盘不能叠在小盘上面。提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆...
18415289645：汉诺塔规律公式是什么?
袁呢答：汉诺塔规律公式是：H（k）=2^k-1。汉诺塔的规律是：二进制数的进位变化规律与汉诺塔问题的处理思路一样。汉诺塔，又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺...
18415289645：汉诺塔通关公式是什么?
袁呢答：f(x)=2^x-1
18415289645：汉诺塔问题公式是什么
袁呢答：求汗诺塔N个盘子须几次移动时得到了下面的递推公式: a[1]=1; a[n]=a[n-1]*2+1; 请教通项公式? a[1]=1; a[n]=a[n-1]*2+1; 可得a[i]=2^i-1; 证明,采用数学归纳法: 1、猜想a[i]=2^i-1 2、当i=1时,显然成立。 3、...
18415289645：一文带你吃透汉诺塔和其变形题
袁呢答：即 ： 公式 H ( n ) = H ( n - 1 ) + 1 + H ( n - 1 )现在思路清楚了，我们来讲它的两种解法：假如有2N个盘子，盘子种类有N种，并且每种盘子有两个（这两个大小和颜色完全相同）新2n盘子从A移动到B = 2 * 之前n个盘子移动次数 因此，依然有两种解法：假如A和B...
18415289645：汉诺塔公式
袁呢答：2n次减一！！！
18415289645：如何计算汉诺塔移动次数和总次数
袁呢答：1层：1次 2层：3次 3层：7次 4层：15次 5层：31次 6层：63次 7层：127次 8层：255次 9层：511次 计算公式：f(x)=2^x-1
18415289645：汉诺塔该怎么玩,方法
袁呢答：n若为偶数的话，顺时针方向依次摆放为：ABC；而n若为奇数的话，就按顺时针方向依次摆放为：ACB。这样经过反复多次的测试，最后就可以按照规定完成汉诺塔的移动。因此很简单的，结果就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C。
18415289645：n个碟子汉诺塔递归问题的时间复杂度是?
袁呢答：时间复杂度的计算：用递归来解决汉诺塔问题是非常方便的选择。设盘子个数为n时，需要T(n)步，把A柱子n-1个盘子移到B柱子，需要T(n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T(n-1)步。得递推公式T(n)=2T(n-1)+1。所以，汉诺塔问题的时间复杂度为O(2^n)...
18415289645：斐波那契数列、卡特兰数列、汉诺塔数列
袁呢答：3、汉诺塔数列：汉诺塔问题家传户晓，其问题背景不做详述，此处重点讲解在有3根柱子的情况下，汉诺塔问题求解的通项公式的推导。问题背景：有A，B和C三根柱子，开始时n个大小互异的圆盘从小到大叠放在A柱上，现要将所有圆盘从A移到C，在移动过程中始终保持小盘在大盘之上。求移动盘子次数的最小值。变量...