汉诺塔问题详解

汉诺塔游戏规则

在一根柱子上从下往上按照大小顺序放置一定数量的圆盘，有三根柱子，把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

该问题可以理解为，先将有圆盘的柱子上的n-1个圆盘放到辅助柱上，再将最后一个圆盘放到目标柱上，最后将辅助柱上的n-1个圆盘放到目标柱上。

如图：

代码实现

#define _CRT_SECURE_NO_WARNINGS	
#include<stdio.h>

void move(char x, char y)//实现圆盘移动
{
	printf("从%c柱上拿一个盘子到%c柱上\n", x, y);
}

void hanoi(int n, char one, char two, char three)//one指起始点，three指目标点，two是上一个盘的目标点
{
	if (n == 1)
	{
		move(one, three);
	}
	else
	{
		hanoi(n - 1, one, three, two);//改变目标点
		move(one, three);
		hanoi(n - 1, two, one, three);//改变起始点
	}
}

int main()
{
	int n;//n为起始柱上圆盘的数量
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');//一开始设置A为起始柱，B为辅助柱，C为目标柱
	return 0;
}

可能看到这个代码，有很多人还是一脸懵逼，为什么要改变起始点和目标点，如果只是用一个n=**的代码怎么运行的例子解释，那么换另一个n后代码怎么实现我们就又不清楚了，所以我们需要找出其中的逻辑关系。

我用画图方法进行解释：

改变目标点的基本思想：

补充：1盘挪动后由于n=1，所以该次语句结束，跳回上一个函数进行下一个move语句，将2挪动到目标点。

改变起始点的基本思想：

在上图中1盘还在B柱上，需要将其挪动到C柱上，由于起始点（也就是one）一直等于A，使得处于B柱的1盘无法挪动，这时我们需要改变起始点（也就是没有改变起始点前的目标点和辅助点进行交换），实现1盘从B到C的挪动。

当盘子为n个时：

这其实就是无限套娃n个套n-1个，n-1套n-2个。。。。

做这个，需要对递归思想和函数有一定的了解