递归的经典运用《汉诺塔问题》

学习递归的人应该都知道汉诺塔问题，翻开一些C语言的书几乎都会在递归中提到汉诺塔问题

为了更好的说明汉诺塔问题，我用一张图说明

算法如下所示：

当A柱子上只有一个盘子时

直接将A盘上的盘子移到C盘

当A柱子上有两个盘子时

先将上面的盘子放在B柱子上

再将下面的盘子放在C柱子上

当A柱子上有三个盘子时（盘子由上到下分别为 1号盘子  2号盘子 3号盘子）

第一步：将A柱子上的1号盘子移到C柱子上：

第二步：将A柱子上的2号盘子移到B柱子上

第三步：将C柱子上的1号盘子移到B柱子上

第四步：将A柱子上的3号盘子移到C柱子上

第五步：将B柱子上的1号盘子移到A柱子上

第六步：将B柱子上的2号盘子移到C柱子上

第七步：将A柱子上的1号盘子移到C柱子上

通过以上的算法可以得出的代码：

#include <stdio.h>

void  hannuota(int n,char X,char Y,char Z);

int main()
{
	char ch1 = ‘A‘;//A柱子
	char ch2 = ‘B‘;//B柱子
	char ch3 = ‘C‘;//C柱子
	int n;         //要移动盘子的个数

	printf("请输入要移动盘子的个数:\n");
	scanf("%d",&n);

	hannuota(n,‘A‘,‘B‘,‘C‘);

	return 0;
}

void hannuota(int n,char A,char B,char C)
{
 /*
  如果是一个盘子
       直接将A柱子上的盘子从A移到C
  否则
    1先将A柱子上的n-1个盘子借助C移到B
	2直接将A上的第n个盘子移到C
	3最后将B柱子上的n-1个盘子借助A移到C
 */
	if(1==n)
	{
       printf("将编号为%d的盘子直接从%c移到%c柱子\n",n,A,C);
	}
	else
	{
		hannuota(n-1,A,C,B);
        printf("将编号为%d的盘子直接从%c移到%c柱子\n",n,A,C);
	    hannuota(n-1,B,A,C);
	}
}

执行结果：

当有三个盘子时

递归的经典运用《汉诺塔问题》

原文：http://blog.csdn.net/u010105970/article/details/19696199