利用递归方法解决汉诺塔问题

Bena ·

更新时间:2024-11-10

· 645 次阅读

利用递归方法解决汉诺塔（Hanoi）问题

一、汉诺塔问题
图片来源于网络
汉诺塔问题是一个经典的古典数学问题，它由三根柱子和若干个圆盘组成。
游戏规则如下：
1.每次只能移动一个圆盘
2.任何时候必须保证大圆盘在下，小圆盘在上
3.目的是在1，2条件下将一根柱子上所有圆盘转移到另一根柱子上。
二、递归算法
想要利用递归解决这个问题，首先我们要确定几个概念：
1、初始柱A 也就是游戏开始时所有圆盘所在的柱子。
2、中间辅助柱B 在转移过程中需要用到的辅助柱。
3、目标柱C 转移的最终目标柱。

首先我们来看当圆盘只有两个时应该如何移动。

我们只需要将A柱的上面一个圆盘暂时放在B柱上，然后将A柱下面一个圆盘直接放在目标柱C上，最后再把B柱暂时存放的圆盘放到C柱上。

然后我们以三个圆盘为例，确定另外一个概念：整体

在移动三个圆盘时，我们不妨假设上面两个圆盘为一个整体，把它看作为一个圆盘。那么解决问题的方法与只移动两个圆盘类似。

而在移动这个整体圆盘时，我们也需要用到与最开始只移动两个圆盘同样的方法，不同的只是目标柱。

不难联想，当圆盘个数变为n时，我们只需要多进行几次与上面同样的步骤，即可获得解决汉诺塔问题的方法。

接下来我们来看，如何在C语言中实现这个算法

三、利用C语言实现算法
递归函数：

void hanoi(int N,char a,char b,char c) 
/*a,b,c分别代表初始柱，中间柱，目标柱    N代表圆盘总数*/
{
	if(N==1) //递归算法的出口
		printf("%c -> %c\n",a,c);//将A移动至C
	else{
	hanoi(N-1,a,c,b); //将整体圆盘从A移动到目标柱（此时目标柱是B）
	printf("%c -> %c\n",a,c);//然后将A剩余的一个圆盘直接移动到C
	hanoi(N-1,b,a,c);//再将整体圆盘从B借助辅助柱A移动到C
	}
}

四、总结
递归方法可以解决很多问题，但是频繁调用函数会占用计算机比较多的资源从而降低效率，所以在使用时应谨慎。

作者：Invinciblenuonuo

方法汉诺塔递归

1024 个赞