一个古老而又经典的算法-汉诺塔问题（java语言实现）
愚公要移山12019-11-29 14:12
哈诺塔问题相信只要学习计算机的人都知道。这是一个古老而又伟大的问题。在这篇文章中，主要是给出递归解决汉诺塔问题的代码方法。毕竟面试的时候，HR比我们要变态很多，怎么蹂躏我们怎么玩。
一、什么是汉诺塔问题
这个问题来源于印度。有三个金刚石塔，第一个从小到大摞着64片黄金圆盘。现在把圆盘按大小顺序重新摆放在最后一个塔上。并且规定，在小圆盘上不能放大圆盘，在三个塔之间一次只能移动一个圆盘。
也就是说将 from 上的圆盘全部移动到 to 上，并且要保证小圆盘始终在大圆盘上。
如何来求解呢？很明显这道题大家都知道使用递归的方式来做。不过如何去考虑递归呢？
在这里我想说一下我个人目前关于递归的理解。递归其实就是一个方程式：f(n) = f(n-1) + a;也就是说在设计递归的时候应该考虑下面三个方面：
（1）求解f(n)的时候，假设f(n-1)已经求解出来了。我们不要去考虑f(n-1)是如何求解出来的。
（2）关键点在于递归的结束条件。
（3）递归往往和分治法是分不开的。对于复杂的递归，往往将递归拆分。然后再合并
整体的递归方法流程是这样的。首先我们要写一个递归方法。
（1）首先判断递归结束时候的操作
（2）递归分解
而本题的汉诺塔就是使用典型的递归思想。首先我们求解f(n)
① 将 n-1 个圆盘从 from -> buffer
② 将 1 个圆盘从 from -> to
③ 将 n-1 个圆盘从 buffer -> to
④以上三步都是为了求解f(n)，最后我们给出递归结束的条件。只有一个圆盘的时候，只需一次移动操作即可。
二、代码实现
举报/反馈
0
0
收藏
分享
