汉诺塔问题（C语言递归实现）

一、问题分析
1.要用递归实现汉诺塔问题得先了解递归的两个必要条件
（1）存在限制条件，当满足这个条件的时候，递归将不再继续
（2）每次调用递归之后会越来越接近这个限制条件
2.汉诺塔问题用递归解决的思路
（1）假设有n个大小不一样的盘子且大盘子下面不能有小盘子，三根柱子A,B,C
（2）找到限制条件：当只需要移动的盘子只有一个时直接移动该盘子
有n个盘子在A柱，将n-1个盘子移动到B柱，将A柱上剩余的1个盘子移动到C柱
有n-1个盘子在B柱，将n-2个盘子移动到A柱，将B柱上剩余的1个盘子移动到C柱
有n-2个盘子在A柱，将n-3个盘子移动到B柱，将A柱上剩余的1个盘子移动到C柱
......
有2个盘子在A或B柱上，将1个盘子移动到B或A柱上，将A或B柱上剩余的1个盘子移动到C柱
将A或B柱上的1个盘子移动到C柱上，完成了移动

 
二、具体代码

1. #include <stdio.h>
2. void move(char ch1, char ch2)
3. {
4.     //把一根柱子的最上面的一个盘子移到另外一根柱子的最上面
5.     printf("%c->%c\n", ch1, ch2);
6. }
7. void Hanoi(char a, char b, char c, int n)
8. {
9.     if (n == 1)
10.     {
11.         //当移动的盘子数量只有一个的时候直接使用move函数
12.         move(a, c);
13.     }
14.     else
15.     {
16.         Hanoi(a, c, b, n - 1);//A柱借助C柱将n-1个盘子移动到B柱      
17.         move(a, c);//将A柱剩余的一个盘子移动到C柱                    
18.         Hanoi(b, a, c, n - 1);//将B柱的n-1个盘子借助A柱移动到C柱     
19.     }
20. }
21. int main()
22. {
23.     int n;//要移动的盘子的总数
24.     scanf("%d", &n);
25.     Hanoi('A', 'B', 'C', n);//A柱借助B柱将n个盘子移到C柱上
26.     return 0;
27. }

复制代码

三、运行结果

 
 
四、总结
一开始打算用数组内移动元素的方式来写，但觉得编译后的结果很难看到具体的移动过程，于是借鉴了CSDN上一位老铁的打印移动柱子的方法，并配上了汉诺塔递归最底层的逻辑思维写出来的，并且补全了具体的递归步骤
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！