汉诺塔问题递归算法

1. 用递归法求汉诺塔问题 求解

c1、c2都是临时变量，分别代表从A移到B时移动了几次，以及从B移动到C时移动了几次，两者相加再加1，就是从A移动到C的移动次数。
它们的赋值就是通过递归调用得到啊，c1 = move( n-1, A, C, B )...

2. 求大神讲解一下C语言汉诺塔递归算法的简易理解

一开始我接触汉诺塔也是很不解，随着代码量的积累，现在很容易就看懂了，因此楼主主要还是对递归函数的理解不够深刻，建议你多写一些递归程序，熟练了自己就能理解。
圆盘逻辑移动过程+程序递归过程分析
hanoi塔问题, 算法分析如下，设a上有n个盘子，为了便于理解我将n个盘子从上到下编号1-n，标记为盘子1，盘子2......盘子n。
如果n=1，则将“ 圆盘1 ” 从 a 直接移动到 c。
如果n=2，则：
（1）将a上的n-1（等于1）个圆盘移到b上，也就是把盘1移动到b上；
（2）再将a上 “盘2” 移到c上；
（3）最后将b上的n-1（等于1）个圆盘移到c上，也就是第（1）步中放在b上的盘1移动到c上。
注意：在这里由于超过了1个盘子，因此不能直接把盘子从a移动到c上，要借助b，那
么 hanoi（n，one，two，three）的含义就是由n个盘子，从one移动到three，如果n>2
那么就进行递归，如果n=1，那么就直接移动。
具体流程：
hanoi（2，a，b，c）；由于2>1因此进入了递归的环节中。
<1>执行hanoi（1，a，c，b）：这里就是刚才的步骤（1），代表借助c柱子，将a柱子上的 1个圆盘（盘1）移动到b柱子，其实由于是n=1，此时c柱子并没被用到，而是直接移动了。
<2>执行hanoi（1，a，b，c）：这是步骤（2），借助b柱子，将a柱子上的一个圆盘（盘2）移动到c柱子上。这里由于也是n=1，也并没有真正借助b柱子，直接移动的。
<3>执行hanoi（1，b，a，c）：这是步骤（3），将b上的一个盘子（盘1）移动到c
函数中由于每次调用hanoi的n值都是1，那么都不会进入递归中，都是直接执行了mov移动函数。
如果n=3，则：（倒着想会想明白）移动的倒数第二部，必然是下面的情况
（1）将a上的n`-1（等于2）个圆盘移到c上，也就是将盘1、盘2 此时都在b柱子上，只有这样才能移动最下面的盘子（盘3）。那么由于现在我们先忽略的最大的盘子（盘3），那么我们现在的目标就是，将两个盘子（盘1、盘2）从a柱子上，借助c柱 子，移动到b柱子上来，这个过程是上面n=2的时候的移动过程，n=2的移动过程是“2 个盘子，从柱子a，借助柱子b，移动到柱子c”。现在是“2个盘子，从柱子a，借助柱子 c，移动到柱子b上”。因此移动过程直接调用n=2的移动过程就能实现。
（2）将a上的一个圆盘（盘3）移到c。
（3）到这一步，由于已经将最大的盘子（盘3）移动到了目的地，此时无论后面怎么移动都不需要在用到最大的那个盘子（盘3），我们就先忽略他，剩下的目标就是将b上面的n-1个盘子（盘1、盘2）移动到c上，由于a上没有盘子了，此时要完成上面的目标，就要借助a盘子。最终达到的目标就是将b上的2个盘子，借助a移动到c上，这个过程就是当n=2时分析的过程了，仅仅是最开始的柱子（b柱子）和被借助的柱子（a柱子）不同了。所以直接调用n=2时候的过程就能股实现了。
具体执行过程：
hanoi（3，a，b，c）；由于3>1因此进入了递归的环节中。
<1>执行hanoi(2,a,c,b):这里代表刚才的步骤（1），将两个盘子（盘1、盘2）从a移动到b，中间借助c。根据n=2的分析过程，必然是能够达到我们的目的。
<2>执行hanoi（1，a，b，c）：现在a上只有一个盘子（盘3），直接移动到c上面即可。
<3>执行hanoi（2，b，a，c）：此时对应步骤（3），剩下的目标就是将b上的两个盘子，借助a移动到c上。那么同样根据n=2的移动过程，必然能达到目的。

最终实现了3个盘子从a，借助b移动到了c。

3. 汉诺塔递归算法求详解 （研究了5天了，没有理解，如果能教会我愿支付宝付现金20元）

首先要知道汉诺塔的基本思路.
汉诺塔有3根柱子. 为什么要有3根呢? 那是因为要直接使一个柱子上的盘片全部移动到另一根柱子是不行的,必须要通过第三根柱子来中转一下.
这种中转思路就是关键了.
具体来说,如果我们要把A柱子上的盘片移动到C柱子上,那么首先我们可以通过"某种方式"将A柱子上除了最底下的盘片以外的所有盘片移动到B柱子上去,也就是拿B柱子当中转. 然后下一步就可以直接把A柱子上最底层的那张盘片移动到C柱子上了. 最后,我们再以同样的方式,将B柱子上剩下的那堆盘片以同样的"某种方式"移动到C上. 总体来看,我们就完成了A->C的盘片移动操作.

那么剩下的问题就是,这"某种方式"是什么呢? 其实思考一下可以发现,在进行这"某种方式"的时候,除去A上最大的那个,其余盘片都是我们需要操作的, 这个时候由于A是最大,其他的盘片对他来说移动都没有限制的(都会比他小). 那么我们就可以暂时忽视这个最大的盘片.

以上面的例子来说,我们要移动A柱子上除了底层之外的所有盘片到B柱上,就可以暂时忽略掉A上最大的那个盘片. 发现没有, 这个时候我们的问题变成是: 将A上的所有盘片(因为已经忽视掉了最大的那个了)移动到B上,C可以作为转接(因为上面没有盘片).

这一步意味着我们把一个n个盘片的汉诺塔问题转化成了n-1个盘片的汉诺塔问题,从而这里面就包含了递归意义.

最后说回到你的程序. 函数hanoi(n,a,b,c)正是这样一个意味: 打印将a柱子上的n个盘片以b为中转移动到c上的操作步骤. 而可以看到,在执行这个函数的时候,如果n=1,那么由于只有一个盘片,可以直接打印a->c, 如果n>1,则先用hanoi(n-1,a,c,b), 以c为中转将a上的n-1个盘片先移动到b上,再打印a->c,即将a上剩下最大的那个盘片移动到c, 然后再调用hanoi(n-1,b,a,c), 以a为中转将b上的盘片移动到c上.
按如此的递归逻辑下去就可以得到全部的操作过程了.

4. 编程实现5个盘子的汉诺塔问题；（递归算法）

//汉诺塔c++程序
#include
using
namespace
std;
void
hanoi(int,int,int,int);//用于递归的函数
void
print(int,int);//从一个桩移动到另一个桩
int
A=1,B=2,C=3;
static
int
counter
=
0;//用于计算总共移动的次数
int
main()
{
int
n;//移动的盘数
cout<<"please
enter
the
quantity
of
the
plates：";
cin>>n;
hanoi(n,A,B,C);
cout<<"Totally
used
"<
"<
评论
0
0
0
加载更多

5. 关于汉诺塔问题的递归算法 算法如图 嗯 我看不懂if语句以后的算法 if(n){hanoi(n-1

递归方法最重要的清楚递归逻辑，也就是func(n)函数的含义。
汉诺塔的逻辑就是，先想办法把上面n-1个块挪到中间，再挪最底下那个到右侧，最后再把n-1个块挪到右侧。hanoi(n,x,y,z)的含义，就是把n个块从x挪到z上，可以利用中间柱子y。
使用递归的时候，看清楚最上层逻辑就好，不要纠结递归走到下一层的具体步骤。

6. 汉诺塔问题的递归算法流程图

关键是第一步移法，奇数层的说，3层在第一柱，后两根柱数数：123。所以，第一块应放在第二根柱，4层，第一块放第三柱。...........奇数层第一块放第二柱，偶数层第一块放第三柱。

7. 求汉诺塔C递归算法详细解答

Hanoi塔问题, 算法分析如下，设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。

Hanoi塔问题中函数调用时系统所做工作

一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：

①将所有的实参、返回地址等信息传递给被调用函数保存。

②为被调用函数的局部变量分配存储区；

③将控制转移到被调用函数的入口。

从被调用函数返回调用函数前，系统也应完成3件事：

①保存被调用函数的结果；

②释放被调用函数的数据区；

③依照被调用函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。

一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i＋1层。反之，退出第i层递归应返回至上一层，即i－1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
P.S.代码如您写的。

8. 汉诺塔递归函数问题

递归其实很简单,你只要晓得啥子是嵌套调用就可以了,所谓嵌套调用,就是在一个函数里调用另一个函数,main函数不能被调用的,所以递归就是有限次的嵌套调用本身函数,每次调用,系统都会重新分配内存,返回时就返回上次调用他的那块内存中的调用函数处,这样理解应该很简单了

void move(int , char ,char,char); /*声明函数,告诉系统我随后要定义一个函数,他不对其中参数进行检查,所以可以省略参数,一般只写类型,表示有多少个什么类型的参数,便于自己理解 */
main()
{int n;
printf("请输入盘数n=" );
scanf("%d",&n);
printf("在3根柱子上移%d只盘的步骤为:\n",n);
move(n,'a','b','c');}/*函数调用,用a,b,c代表3跟柱子,把盘子数,柱子代码传给函数*/
void move(int m, char p, char q, char r) //定义函数
{if (m==1)
{printf("[%d] move 1# from %c to %c\n", step, p,r);
step=step+1;}
else{move(m-1,p,r,q); //调用本身函数,进行递归 A
printf("[%d] move %d# from %c to %c\n",step, m,p,r);
step=step+1;
move(m-1,q,p,r); //再次调用 B
}
getch();}

这里面的递归涉及一个汉诺塔的算法问题,具体讲明白的话有点麻烦,总体思路是假设盘子全在a柱上,想放到c上
第N个人就想要是有人搬动其他N-1个盘子到b,那他只要搬一次从a到c就可以,在让那个人把N-1个盘子放到c上
第N-1那个人就想要是有人搬动其他N-2个盘子到c,他只要搬动一次从a到b就可以,在让那个人把N-2个盘子放到b上
....
第1个人就直接把盘子从a到c

这样形成递归
我在俩处调用标记了A,B,我写出步踌,你看看.
假设3个盘子
A函数相当于双重循环中的外层循环
B函数相当于双重循环中的内层循环

1,主函数调用,p=a,q=b,r=c,m=3,运行A,调用本身(A第一次调用)传入p,r,q(a,c,b) 注意调用函数中p,r,q排列
2,被调函数是用p,q,r的顺序接收传入的p,r,q.p=a,q=c,r=b,m=2,执行A,调用本身(A第二次调用) 调用传入p,r,q(a,b,c)
3,p=a,q=b,r=c,m=1,执行if,输出a->c,返回A第二次调用
4,本次函数中p=a,q=c,r=b,m=2,向下执行,输出a->b,执行B,调用本身(B第一次调用),传入q,p,r(c,a,b),m=1
5,p=c,q=a,r=b,m=1,执行if,输出c->b,返回B第一次调用
6,向下执行,执行完毕,返回A第一次调用
7,本次函数中p=a,q=b,r=c,m=3,向下执行,输出a->c,执行B,调用本身(B第一次调用),传入q,p,r(b,a,c),m=2
8,p=b,q=a,r=c,m=2,执行A,调用本身(A'第一次调用,注意是B函数调用中再次调用A) 传入p,r,q(b,c,a)
9,p=b,q=c,r=a,m=1,执行if,输出b->a,返回A'第一次调用
10,本次函数中p=b,q=a,r=c,m=2向下执行,输出b->c,执行B,调用本身(B'的第一次调用,注意是B函数中再次调用B) 传入q,p,r(a,b,c),m=1
11,p=a,q=b,r=c,m=1,执行if,输出a->c返回B'第一次调用
12,向下执行,执行完毕,返回B第一次调用
13,向下执行,执行完毕,返回主函数

仔细分析每次调用时当前变量p,q,r中所代表的a,b,c,每次调用时,p,q,r都是新的变量
我看了你的问题，估计你把调用函数中的p,q,r变量与被调函数中p,q,r变量搞混了

/*
4,向下执行,执行B,调用本身(B第一次调用),由于本次函数中p=a,q=c,r=b,m=2,先输出a->b,再传入q=c,p=a,r=b,m=1
这里不是[4] move 3# from a to c吗
*/
注意调用传入的顺序是q,p,r,传入的值是c,a,b的顺序，被调函数中是拿p,q,r的顺序在接收，所以被调函数中值的顺序就该是p=c,q=a,r=b,执行if就输出c->b

不要想太复杂了，q,p,r是变量，用来存储值的，而他只是个局部变量，每次调用函数后给q,p,r新分配的内存地址不一样。比如本次函数中q,p,r中放的值分别是q=c,p=a,r=b，当执行调用函数时，给被调函数传入的是变量的值，也就是说实际上传入的是c,a,b
在被调函数中，p,q,r是新的局部变量，他接收来自调用函数中的值，行参接收值的顺序与实参传入值的顺序是相对应的，因为实参传入的顺序是c,a,b，在行参接收值时也以这样的顺序接收,而行参变量的顺序是p,q,r,所以被调函数中p=c,q=a,r=b

9. 汉诺塔问题公式是什么

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

有三根杆子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次

10. 汉诺塔问题算法

纯手打，自己理解的。看的东就给分吧...
例如n=3
3，A,B,C
{ 2，A,C,B---------------->{1,A,B,C ============>A->C
move(A,B) ============>A->B
1,C,A,B ============>C->B
}
move(A,C) ============>A->C
2,B,A,C------------------>{1,B,C,A ============>B->A
move(B,C) ============>B->C
1,A,B,C ============>A->C
}
}