汉诺塔问题算法分析递推关系式

① 汉诺塔问题求解

这个汉诺塔我觉得可以算是谭浩强书上最难得一个例题了 我也花费了很长时间才理解的 我把我曾经写在书上的一些自己总结的东西写给你 不知道你能不能看得明白
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
一。void hanoi(int n,char one,char two,char 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("输入塔的个数");
scanf("%d",&m);
hanoi(m,'A','B','C');
}
我上面标注了4个地方
假设这里输入的是3
1的作用是从1座借助2座移到3座
2的作用是将n-1个盘子移到2座，具体怎么移动先不要管因为要进行递归操作
3的作用是将前卖弄最下面的盘子移到C
4的作用是将2座上剩下的N-1个盘子移到C上
以上的2，4进行了递归运算
运行过程如下
输入3
void hanio(int 3,char x,char y,char z)
hanoi(n-1,one,three,two);
*****************→(2-1,x,y,z)→(1,x,y,z)→x→z
****(3-1,x,z,y)→运行2*********************x→y
*****************→(2-1,z,x,y)→(1,z,x,y) *z→y
move(one,three);
运行3**************************************x→z
hanoi(n-1,two,one,three);
运行4
******************→(2-1,y,z,x)→(1,y,z,x)→y-X
(3-1,y,x,z)*******运行2******************y→z
(2-1,x,y,z)→(1,x,y,z)******************x→z
不知道你能不能看得明白
这样得到的答案就是
x->z;
x->y;
z→y,
x->z;
y->x;
y->z;
x->z;

② 汉诺塔递归算法是什么

汉诺塔问题实际上就是要将柱子A上由小到大排列的圆环按照相同的大小顺序移动到柱子C，之间的过程可以使用柱子B。

其递归的归纳思想是这样的：

（1）首先，当只有一个盘子的时候只需要将A上的1号盘子移动到C上就行了

（2）当有2个盘子在A上的时候，需要将A上的1号盘子（由上往下数）移动到B上，再将A上的2号盘子移动到C上，之后将B上的1号盘子移动到C上

（3）当有3个盘子在A上的时候，需要将A上的1号和2号盘子移动到B上（需要借助C），之后将A上的3号盘子移动到C上，再将B上的盘子移动到C上（需要借助A）

（...）以此类推

（N）当有N个盘子在A上的时候，需要将A上的N-1个盘子移动到B上（需要借助C），之后将A上的第N个盘子移动到C上，再将B上的盘子移动到C上（需要借助A）

起源

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

③ 汉诺塔问题

编程时，脑子里不要去思考递归过程（转来转去，会让人很头疼，一会儿就晕了）。
数列我想你是清楚的，所谓的递归，就是把an变成a(n-1)去处理问题，处理一个通项式是相同的方法，只要给出a1(或者还有a2)，这是递归结束的条件。
假设汉诺塔A B C三根针，只考虑移动最底下的盘子时，
如果只有一个盘子，就是直接A->C
如果只有两个盘子，就是A->B 然后A->C
如果只有三个盘子，就是A->C A->B C->B 然后A->C
可以发现，
（1）如果想移动最底下的盘子，则，先要上面n-1个移动到B盘，即可。
（2）在移动B盘上的n-1中的最底下的盘子时，则改变一下源针和中间针即可，即：把B看成A A看成B
（3）接下来，在移动A盘上的n-2中的最底下的盘子时，则恢复源针和中间针即可，即：A还是A，B还是B。本步与第一步相同，即1 2两步是在n>1时，的循环。
（4）当只有一个盘子时（n=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 <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次

⑤ 求汉诺塔递归全过程的算法详解图，记得一定要是图释哦！！！

图解是什么意思呀。
这个算法 那么简单没必要搞得那么复杂吧。
an = an-1 + 1;
你明白这个等式的意义吗？
这个等式已经包含了递归算法的全部含义。

an 表示 n个数的和，an-1 表示n-1个数的和 ，an = an-1 + 1;表示n个数的和可以通过n-1个数的和来求的。
上述说明哪些情况可以使用递归呢？
那就是：已知前一个步骤可以求得后一个步骤的结果的情况，并且前一个步骤和后一个步骤是有规律过度的。
比如汉诺塔问题：
移n个盘是已移n-1个盘为条件的，两者的共同点是移盘。所以可以用f（n）表示移n个盘，f(n-1)表示移n-1个盘，那么移n个盘和移n-1个盘有什么关系呢？
这就需要预先分析问题才能得出具体的关系
在这个问题中，把n个盘从a移到c需要三个步骤来完成。
1.n-1个盘从a移到b
2 1个盘从a移到c
3 n-1个盘从b移到c
已知n-1个盘从a移到b是可行的，为什么？
因为移1个盘是可行，那么移2个盘也是可行，移 3个盘是已移2个盘为条件的，所以移3个盘也是可行的，所以移n个 盘是可行的。
所以根据已知条件可以解得：
设f(n, a, b,c) 表示 把n个盘从a移到c 借助b --------------------------这里很关键，这是搞懂递归的关键关键。
那么把n-1个盘从a移到b 借助c 怎样表示呢？
很明显是：f(n-1, a, c,b)
那么把1个盘从a移到c怎样表示呢?
很明显是：f(1, a, b,c)
那么把n-1个盘从b移到c 借助a 怎样表示呢？
很明显是：f(n-1, b, a,c)

所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
这和等差等比数列一个原理。
没有什么 特别的。

记住是问题有这样递推关系才可以使用这种方法。
如果要你计算1+2+8+22 的结果 你就不能使用递归。
因为该问题的后一步骤与前一步骤不具有规律性，所以已知前一个步骤并不能求的后一个步骤的值
1+2+3+4 ...+
这个问题就可以使用递归
原因你懂了吧。
至于爬楼梯问题，无限级分类 问题等一些递归问题，那不过时小菜一碟。
一句话：后一步骤依赖前一步骤并且二者联系具有规律性，运用递归必然成功。

⑥ 汉诺塔问题通项公式

通项公式：H（k）=2^k-1。

汉诺塔游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。

操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：

(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；

(2)将A杆中剩下的第n号盘移至C杆；

(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。

事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。

依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。

(6)汉诺塔问题算法分析递推关系式扩展阅读：

目前关于汉诺塔问题解决的一个最主要的观点认为，完成汉诺塔任务时要对圆盘的移动顺序进行预先计划和回顾性计划活动。

当问题呈现后，在开始第一步的移动之前，大多数被试都会根据设定好的目标状态，对圆盘的移动顺序进行预先计划。以决定圆盘的移动顺序，但是这种计划能力的作用可能会受到问题难度的影响。

也有研究者认为，不是计划能力而是抑制能力参与汉诺塔问题的解决过程。为了把更大的圆盘先放置于指定位置，必须让较小的圆盘暂时偏离其最终应该放置的位置，但被试的自然反应总是“尽快”将圆盘移动到最终的目的地，如此反而导致错误，使移动步数更多，完成时间更长。

⑦ 汉诺塔的算法

算法介绍：当盘子的个数为n时，移动的次数应等于2^n–1。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A、B、C；

若n为奇数，按顺时针方向依次摆放A、C、B。

所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

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

(7)汉诺塔问题算法分析递推关系式扩展阅读

由来：

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615秒。

这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

⑧ 关于汉诺塔的问题。

利用递归解决汉诺塔，其最巧妙之处在于实参和形参的不断变幻，实际的柱子也改变了，例如move(n-1,x,z,y)，借组z柱，移到y柱在进入递归时：形参move(int n,int x,int y,int z) /，移到z柱而在递归时; //，盘子数量减少了，和以前数学中的递推证明非常接近,z所对应的实参, y 。就是形参x。数学的递推证明的思想是;/ 函数的目的是把x柱的n个盘子，借助y柱，假定n-1的时候是正确的，证明n也是正确就可以了。 递归过程的思想是，如果已经有了解决n的方法（汉诺塔中，移动n-1个盘子），怎么来处理当前n的问题（如果n-1个盘子已经移好了，那只要把最后一个盘子移过去就可以）。当然理解计算机的递归过程，柱子改变了; 这是把x柱的n-1个盘子，还要处理一下递归的结束条件（当n=1的时候），否则递归就不会结束了，在递归过程中是不断改变的。注意

⑨ 汉诺塔问题公式是什么

求汗诺塔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、...

⑩ 汉诺塔递归算法是什么

如下：

1、汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2、抽象为数学问题：从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

算法分析（递归算法）：

实现这个算法可以简单分为三个步骤：把n-1个盘子由A 移到 B；把第n个盘子由 A移到 C；把n-1个盘子由B 移到 C。从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步。

1、中间的一步是把最大的一个盘子由A移到C上去。

2、中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上。

3、中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上。