C语言实现递归解决汉罗塔问题

1.问题：

• 汉诺塔(Tower of Hanoi），又称河内塔。是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2. 编程思路：

• ①不管有多少层汉诺塔，我全看成只有两层,即为第n层和第n-1层这两层，而这两层的 *** 作就是A先移动一层到B柱，然后A在移动一层到C柱，最后B柱上一层再移动到C柱即完成了移动。
• ②递归思想的理解：递归就是一直重复调用自己，直到达到限制条件就从里到外退出这次递归，所以我们第一次递归到最里层，就是直到n=1时，我们这次递归是希望通过C柱把n-1层放在B柱上，所以递归条件就是hannuota（n-1,A,C,B）即最终结果就是A——B,接下来我们就是把A柱第n层移动到C柱了，此时B柱上有n-1层，C柱上只有第n层这一层而已,A柱上零层，那此刻我们就需要借助A柱，实现B柱上的n-1层，从n-1层移动到C柱上条件为hannuota（n-1,B,A,C）。而这达到最终目的的过程中的其他步骤，在递归回去的过程也逐一满足。 

 

3.具体代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include
void hannuota(int n,char A,char B,char C)
{
if (n == 1)
{
printf(" % c -> % c\n",A, C);//n
//count++;
}
if (n > 1)
{ hannuota(n - 1, A, C, B);//使A柱子上的(n-1)个盘子借助C移动到B上 小循环当n=1时结束 使得A->B
printf(" %c -> %c\n", A, C);
//count++;
hannuota(n - 1, B, A, C);
}
//printf(“总共移动%d次\n”,count);
}
int main()
{
int count = 0;
int n;
printf(“请输入你所要计算的汉诺塔的层数：\n”);
scanf(“%d”, &n);
hannuota(n, ‘a’, ‘b’, ‘c’);
return 0;
}

• 运行结果：