【汉诺塔问题】c语言实现

1.问题描述

汉诺塔问题是指：
一块板上固定三个木杆： A、B、C。A 赶上套有若干个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这些圆盘从 A 移动到 C 上，每次只能移动一个圆盘，移动过程可以借助 B 。但在任何时候，任何木杆上的圆盘都必须保持大盘在下，小盘在上。

从键盘输入需移动的圆盘个数n，打印出移动的过程。

2.问题分析

模拟其实际操作过程，可以发现：

1. 当只移动一个圆盘时，直接将圆盘从 A 移动到 C 。

2. 若移动的圆盘为 n(n>1)，则分成几步走：

step1. 把 (n-1) 个圆盘从 A 移动到 B （借助 C ）；
step2. A 上的最后一个圆盘移动到 C ；
step3. B 上的 (n-1) 个圆盘移动到 C （借助 A ）。

因此，解决汉诺塔问题可设计一个递归函数，上述模拟过程即为递归体。当n最后为1时，即可完成整个移动过程。

3.C语言代码实现及测试

int main()
{
	void han(int,char,char,char);
	int n;
	printf("Please input the number of the disks:>");
	scanf("%d", &n);
	printf("\n");
	
	han(n,'A','B','C');
	return 0;
}

void han(int n, char a, char b, char c)
{
	void move(char,int,char);
	if (n == 1)
		move(a,1,c);
	else
	{
		han(n-1,a,c,b);
		move(a,n,c);
		han(n-1,b,a,c);
	}
}

void move(char from, int n, char to)
{
	static int count = 1;
	printf("%2d:%3d %c -> %c\n", count,n,from,to);
	if (count%3 == 0)
		printf("\n");
	count++;
}

/*测试
Please input the number of the disks:>3

 1:  1 A -> C
 2:  2 A -> B
 3:  1 C -> B

 4:  3 A -> C
 5:  1 B -> A
 6:  2 B -> C

 7:  1 A -> C
*/

4.参考

1.用C语言实现汉诺塔

2.动图-汉诺塔问题