（1）什么是汉诺塔

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

若每次移动需要1s的时间，那么请问婆罗门需要多久才能把这64片黄金圆盘从一根石柱上移动到另一个石柱上？

（2）汉诺塔打印步骤

/***********************************************************************

目的：使用递归打印1个n层的汉诺塔从A柱到C柱的所有步骤
原理：封装1个函数Hanio(num, ‘A’, ‘B’, ‘C’)。
其中num是塔数；A、B、C，3个字符为抽象成的3个柱子。
如果只有1层那么输出A；
否则就有2种情况，其1是将n-1个碟子从A经C到B。其2是将n-1个碟子从B经A到C
平台：Visual studio 2017 && windows
*************************************************************************/

塔数   步骤
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
…   …
偶   A->B
奇   A->C

（3）如何用C语言实现汉诺塔

现有三个柱子A、B、C，其中有n个圆盘在A柱上，最终要实现把这n个圆盘从A柱借助B柱移动到C柱上。实现实现思路：先将n-1个圆盘从A柱移动到B柱上，然后将A柱上最后一个圆盘移动到C柱上，最后再把B柱上的n-1个圆盘移动到C柱上。如下图所示：

当n=1时：
1.将A柱上最后一个圆盘移动到C柱上（A →C）

当n=2时：
1.将1个圆盘从A柱移动到B柱上，重复n=1时的步骤，只不过是将那1个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
2.将A柱上最后一个圆盘移动到C柱上（A →C）
3.将B柱上的1个圆盘移动到C柱上。重复n=1时的步骤，只不过是将那个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）

当n=3时：
1.将2个圆盘从A柱移动到B柱上。重复n=2时的步骤，只不过是将那2个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
2.将A柱上最后一个圆盘移动到C柱上（A →C）
3.将B柱上的2个圆盘移动到C柱上。重复n=2时的步骤，只不过是将那2个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）

当n=4时：
1.将3个圆盘从A柱移动到B柱上。重复n=3时的步骤，只不过是将那3个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
2.将A柱上最后一个圆盘移动到C柱上（A →C）
3.将B柱上的3个圆盘移动到C柱上。重复n=3时的步骤，只不过是将那3个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）

以此类推，当汉诺塔上的圆盘数为n个时该如何移动，只需要按照上面的规律一直往上递归，最终是可以达到目的的。

（4）实现代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Hanio_Step(int n, char A, char B, char C)
{
	if (1 == n)
		printf("%c->%c\n", A, C);
	else
	{
		Hanio_Step(n-1, A, C, B);
		printf("%c->%c", A, C);
		Hanio_Step(n-1, B, A, C);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	Hanio_Step(n, 'A', 'B', 'C');
	return 0;
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/73276.html