【C语言】汉诺塔问题

一、何为汉诺塔问题？

二、汉诺塔计算规律

三、打印汉诺塔的移动路径

总结

一、何为汉诺塔问题？

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

简单来讲，汉诺塔问题是这样的：

给定三根柱子，记为A,B,C，其中 A 柱子上有 n个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将A 柱上的盘子经由 B柱移动到 C 柱最少需要多少次？并且移动时还有要求：1、一次只能移动一个盘子 2、大的盘子不能压在小盘子上

二、汉诺塔计算规律

我们分别计算有1个圆盘、2个圆盘、3个圆盘、4个圆盘的情况：

.......

3个圆盘需要移动7次，4个圆盘需要移动15次，我们可以得出规律，得到一条计算公式：

2^n - 1 == 移动次数。

三、打印汉诺塔的移动路径

递归打印移动路径，核心思想是大事化小，借助B柱子，一次性移动(n-1)个圆盘到B柱子上，再将A柱子上的圆盘移动到C柱子上，看代码：

//递归方法
//n -- 盘子个数
//post1 -- 起始柱子
//post2 -- 辅助柱子
//post3 -- 目标柱子
void move(char post1,char post2)
{
	printf("%c->%c ", post1, post2);
}
void hanoi(int n,char post1,char post2,char post3) 
{
	//当n==1时，只有一个盘子
	//post1 -> post3 即可
	//递归的终止条件
	if (n == 1)
	{
		move(post1, post3);
	}
	else
	{
		//将n-1个盘子从post1通过post3移动到post2。
		hanoi(n-1, post1, post3, post2);
        // move(post1, post3); 
        //函数的作用是模拟将一个盘子从 post1 柱子移动到 post3 柱子，
        //并打印出这一移动的过程。
		move(post1, post3);
        //将n-1个盘子从post2通过post1移动到post3。
		hanoi(n-1, post2, post1, post3);
	}
}
int main() 
{
	hanoi(2, 'A', 'B', 'C');
	return 0;
}

代码解释：

当盘子数量为1时：我们只需要将它从起始柱子直接移动到目标柱子。这也是递归的终止条件。

当盘子数量大于1时，我们执行以下三个步骤：

将n-1个盘子从post1通过post3移动到post2。
将剩下的那个盘子（最大的那个）从post1移动到post3。
将n-1个盘子从post2通过post1移动到post3。