递归函数汉诺塔（汉诺塔递归问题）

本文目录

• 汉诺塔递归问题
• 语言是C#,求解释汉诺塔问题的递归算法
• c语言递归解决汉诺塔参数变化的疑惑
• 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;
汉诺塔使用递归的方法来实现的
可能你对递归还没理解透，反正记住，程序总是一步一步的按顺序执行，有调用函数就先在调用的地方设个断点，转入函数执行，执行完了又返回断点，万变不离其宗！
程序执行的顺序
Hannoi(7,’a’,’b’,’c’);这里调用函数，转入函数执行并传入参数n=7
第一步，执行判断语句，根据n的值进入else执行
第二步，执行Hannoi(n-1,a,c,b);这时是调用函数本身，也就是所谓的递归了，你看传入的值n-1，相当于传入n=6，还有a,c,b,的值，这个要注意顺序，在调用的时候a,c,b的值是第一次传入的值
第三步，执行Hannoi(int n,char a,char b,char c)函数，这点能理解吧，这次传入的值n=6了，但是a,b,c,的值相对于第一次的值有改变了哦，可以理解成，a(2)=a(1),b(2)=c(1),c(2)=b(1),这里括号里代表函数调用的次数，其实这里最容易弄混的就是，a,b,c的值，自己用本子把每次传入的值的a,b,c按传入顺序列出来，会容易理解些
同样，执行判断，n》1进入else,按顺序执行，先执行Hannoi(n-1,a,c,b);然后又是调用本身，注意传入的值，是a(2),c(2),b(2),又转入去执行Hannoi(int n,char a,char b,char c)函数,这时接收的值a(3)=a(2),b(3)=c(2),c(3)=b(2)，就像在兜圈子是吧，没错。后面你自己做张表来理一下。
这样兜圈子直到n=1。你看Hannoi(n-1,a,c,b);每次n都是减了1的，所以n-1次递归的时候，就直接执行if(n==1)里面的了，终于有所改变了是吧，他执行的是Move(1,a,c); 也就是输出函数，执行完Move(int n,char x,char y) 返回原来的调用的那个断点。继续向后。没有语句了，就返回上次调用的函数，上次调用Hannoi(int n,char a,char b,char c)是谁呢，就是n-2次的Hannoi(int n,char a,char b,char c)中的Hannoi(n-1,a,c,b);调用的他啊，返回到这里，继续向后又遇到Move(n,a,c); 这里不用讲解了吧，输出后返回来，继续向后执行Hannoi(n-1,b,a,c); 新的递归开始了，看你再列个新的表理一下呢，注意传入的值和他的顺序，还有n的值这时是多少。
其实我的讲解你可能看的也不是很清楚，关键是要理解到递归他无非就是调用自己，调用完返回就是返回上次调用的地方，也是他自己，只是俩次的函数使用中的值是不一样的，这个值呢，最好拿笔记下来，并写个次数才容易理解和分析。
这递归程序很经典，值得研究，你会发现他是如此的巧妙，太棒了！建议测试的时候不要把n设的太大，不然容易死机！想想里面的循环次数就真令人咂舌了！

语言是C#,求解释汉诺塔问题的递归算法

设汉诺塔盘子从上到下，依次为 d1, d2,d3,......dn, ( n》0)
记 上面前k个盘子整体为 S(k) (k》1)
递归的思路是，先假设前n-1个盘子为一个整体S(n-1)，要把盘子从A移动C, 只需要借助桥梁B即可完成，具体移动方法是：
(1) S(n-1):A=》B
(2) dn:A=》C
(3) S(n-1):B=》C
实际上就是一个包含四个参数 f(n ,A, B, C) 的函数
第一步和第三步实际上就回到n-1层汉诺塔问题，
拿第一步来说，把前n-2个盘子看为一个整体S(n-2), 问题变为把盘子从A移动B,这时需要把C作为桥梁，移动方法是：
（4）S(n-2): A=》C
(5) d(n-1): A=》B
(6) S(n-2): C=》B
实际上和(1),(2),(3)的步骤没有区别，只是【桥梁】 B和C对调了一下而已：
通过（1），（2），（3）总结函数式：
(1) f(n-1, A, C, B) // 参数A为原地点，C为桥梁， B为目的地
(2) n : A=》C // 把最底下的盘子从 原地点=》目的地
(3) f(n-1, B, A, C) // 参数 B为原地点，A为桥梁，C为目的地
递归解这种问题是算比较好理解的， 更难的是用非递归的方法解，
实际上，所有递归算法都可以转换成非递归的算法，一些低级语言如汇编就没有递归算法。

c语言递归解决汉诺塔参数变化的疑惑

这种实现方法是递归的方法来是实现的，递归的实现离不开栈。首先第一个主函数调用
hanoi(m,’A’,’B’,’C’);（把A中的m个盘子利用B移动到C）在这个函数体内他由调移到hanoi(n-1,‘A’,‘C’,‘B’);（把A的前n-1个盘子利用C移到B）此时hanoi(m,’A’,’B’,’C’);在cpu中的环境入栈，hanoi(n-1,‘A’,‘C’,‘B’);的各个环境参数进驻cpu而他又调用hanoi(n-3,,‘A’,‘B,‘C);依次类推....直到第一个参数n==1为止就把A上的最后一个盘子移到另一个柱子上，然后返回...最后hanoi(n-1,‘A’,‘C’,‘B’)函数返回，执行move(’A‘，’C‘);把A移动到C上。再执行hanoi(n-1,‘B,‘A,‘C)；他的执行步骤和hanoi(n-1,‘A’,‘C’,‘B’)一样，就不在解释

c语言递归问题： 汉诺塔问题：

//可运行的代码
#include
void
move(char
x,char
y)
//
定义move函数
{
printf("%c--》%c\n",x,y);
}
void
hannuota(int
n,char
one,char
two,char
three)
//
定义hanuota函数
//
将n个盘从one座借助two座,移到three座
{
if(n==1)
move(one,three);
else
{
hannuota(n-1,one,three,two);
move(one,three);
hannuota(n-1,two,one,three);
}
}
int
main()
{
int
m;
printf("input
the
number
of
diskes:");
scanf("%d",&m);
printf("The
step
to
move
%d
diskes:\n",m);
hannuota(m,’A’,’B’,’C’);
while(1);
return
0;
}
/*
input
the
number
of
diskes:3
The
step
to
move
3
diskes:
A--》C
A--》B
C--》B
A--》C
B--》A
B--》C
A--》C
*/

c语言用递归实现汉诺塔

见代码注释，还有不懂可以问。

#include 《stdio.h》
void move(char x,char y)
{
    printf("%c--》%c\n",x,y);
}
//hannuota函数的作用：把n个圆盘从one柱子借助two柱子放到three柱子 
void hannuota(int n,char one,char two,char three)
{
    if(n==1)//如果只有一个柱子 
        move(one,three);//直接移动即可 
    else
    {
        hannuota(n-1,one,three,two);//先把one柱子上的n-1个圆盘借助three柱子移动到柱子two 
        move(one,three);//把第一个柱子的剩下那一个(第n个)移动到第三个柱子
//由于原来one柱子上的n-1个圆盘已经移动到了two柱子上，因此不会有圆盘挡住n圆盘出来 
        hannuota(n-1,two,one,three);
        //最后再把那n-1个圆盘从two柱子借助one柱子移动到three柱子
//(上面第一句话hannuota(n-1,one,three,two)已经移动到了two柱子，因此这里是从two柱子移动到three柱子) 
    }
}
int main()
{
    int m;
    printf("input the number of diskes:");
    scanf("%d",&m);
    printf("The step to move %d diskes:\n",m);
    hannuota(m,’A’,’B’,’C’);
    return 0;
}