【C语言】汉诺塔问题的递归解法

汉诺塔是一个很经典的问题。简单来说，有三根柱子，从左到右，分别编号为A,B,C，在A上套有n个盘子，从下到上依次减小，我们的任务是把所有的盘子移动到C上，每次移动的过程中，都必须保持上面的盘子比下面的小。

破题的关键就是把大事化小。假设有n个盘子（n>1），我们只需要把上面n-1个盘子通过C柱移动到B柱上，接着把A柱剩下的一个盘子移动到C柱上，最后再把B柱上的n-1个盘子通过A柱移动到C柱上。

所以这是一个递归。每次调用函数都会把n-1传给自己，就把大事化小了。那么递归的限制条件是什么呢？很简单，当n=1时，也就是说A柱上只有一个盘子了，我们就直接把这个盘子移动到C住上。而n>1时就按照前面的思路递归，每次递归调用时n都会-1，总有一天n会等于1，从而停止递归。把上面的思路转化成代码如下：

#include 

//
//运行结果
//1:A->C
//2:A->B A->C B->C
//3:A->C A->B C->B A->C B->A B->C A->C
//4:A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C
//

//从pos1到pos2
void move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);
}

//n为盘子个数，pos123分别是起始位置，中转位置，目标位置
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (1 == n)
	{
		move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}

int main()
{
	printf("1:");
	Hanoi(1, 'A', 'B', 'C');
	printf("n");

	printf("2:");
	Hanoi(2, 'A', 'B', 'C');
	printf("n");

	printf("3:");
	Hanoi(3, 'A', 'B', 'C');
	printf("n");

	printf("4:");
	Hanoi(4, 'A', 'B', 'C');
	printf("n");

	return 0;
}