hanoi.c

来自「该文件夹中包含了大部分经典的算法的源程序代码」· C语言 代码 · 共 59 行

/* 
	Name : Hanoi.c

	Description : 利用函数递归法求hanoi塔问题之解
     Rules :
       hanoi塔问题目的乃在三根柱子中,将n个盘子从
       A 柱子搬到 C 柱中,每次只移动一盘子,而且必须遵守
       每个盘子都比其上面的盘子还要大的原则。
    Ans :
       hanoi塔问题的想法必须针对最底端的盘子。
      必须先把A柱子顶端n-1个盘子想办法(借助C柱)移至B柱子
      然后才能将想最底端的盘子移至C柱。
      此时C有最大的盘子,B总共n-1个盘子,A柱则无。
      只要再借助A柱子，将B柱n-1个盘子移往C柱即可:
      HanoiTower(n-1,A,C,B);
      将A顶端n-1个盘子借助C移至B
      HanoiTower(n-1,B,A,C);
      将B上的n-1个盘子借助A移至C

*/

#include <stdio.h>
#include <conio.h>

/* 函数原型宣告 */
void HanoiTower(int ,char,char,char);

void main()
{

	int n;
	char A = 'A' , B = 'B' , C = 'C';

	printf("-----Hanoi Tower Implementaion----\n");
	/*输入共有几个盘子在A柱子中*/
	printf("How many disks in A ? ");
	scanf("%d",&n);
	if ( n == 0 )
		printf("no disk to move\n");
	else
		HanoiTower(n,A,B,C);
}


/* 递归函数调用求河内塔之解 */
void HanoiTower(int n,char a,char b,char c)
{
	if ( n == 1 )
		printf("Move disk 1 from %c -> %c\n",a,c);
	else
	{
		/*将A上n-1个盘子借助C移至B */
		HanoiTower(n-1,a,c,b);
		printf("Move disk %d from %c -> %c\n",n,a,c);
		/*将B上n-1个盘子借助A移至C */
		HanoiTower(n-1,b,a,c);
	}
}