目录

前言

一、求解思路

二、代码实现

1.参考代码

2.运行结果

总结

前言

​ 汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。  

一、求解思路

三根柱子从左到右依次为 A , B , C，要将A的圆盘全部挪到C上去。

我们设盘子的数量为n，圆盘从小到大用数字表示，从1开始：

当 n = 1 时，移动1：A → C。

当 n = 2 时，移动1：A → B，移动2：A → C，移动1：B → C。

当 n = 3 时，移动1：A → C，移动2：A → B，移动1：C → B，移动3：A → C，移动1：B → A，

                     移动2：B → C，移动1：A → C。

汉诺塔问题中，n 个圆盘至少需要 2 ^n - 1 次移动操作。

通过上述过程总结出，对于初始状态下起始柱包含 2 个以上圆盘的情况，移动过程可以遵循以下步骤：

1.将起始柱上的 n-1 个圆盘移动到辅助柱B；

2.将起始柱上最大的圆盘移动到目标柱C；

3.将辅助柱中的 n-1个圆盘移动到目标柱C。

得出了以上的算法，我们就可以通过C语言来编写出程序了。

二、代码实现

1.参考代码

#include <stdio.h>

void Hanoi(int n,char pillar1,char pillar2,char pillar3) //1为起始柱，2为辅助柱，3为目标柱
{
	if (1 == n)
	{
		printf("移动第%d个：%c→%cn", n, pillar1, pillar3);
	}
	else if (n > 1)
	{
		Hanoi(n - 1, pillar1, pillar3, pillar2);
		printf("移动第%d个:%c→%cn", n, pillar1, pillar3);
		Hanoi(n - 1, pillar2, pillar1, pillar3);
	}
	else
	{
		printf("输入错误,重新选择n");
		main();
	}
}

int main()
{
	int n = 0;
	printf("要来多少个圆盘？n");
	scanf("%d", &n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

2.运行结果

当圆盘过多时，运行时间为以年为单位，如64个圆盘时运行结果等两百多年后再来看看差不多！

总结

汉诺塔是一个经典的问题。