一个古老而又经典的算法-汉诺塔问题
16lz
2021-01-22
哈诺塔问题相信只要学习计算机的人都知道。这是一个古老而又伟大的问题。在这篇文章中,主要是给出递归解决汉诺塔问题的代码方法。毕竟面试的时候,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),最后我们给出递归结束的条件。只有一个圆盘的时候,只需一次移动操作即可。
二、代码实现
1public class Hanoi {
2 public static void move(int n, String from, String buffer, String to) {
3 //第一步:递归结束的条件
4 if (n == 1) {
5 System.out.println("from " + from + " to " + to);
6 return;
7 }
8 // n-1 个圆盘从 from -> buffer
9 move(n - 1, from, to, buffer);
10 //将 1 个圆盘从 from -> to
11 move(1, from, buffer, to);
12 //将 n-1 个圆盘从 buffer -> to
13 move(n - 1, buffer, from, to);
14 }
15
16 public static void main(String[] args) {
17 Hanoi.move(3, "石柱1", "石柱2", "石柱3");
18 }
19}
更多相关文章
- 函数和递归
- 迭代和函数的递归的学习
- 如何递归将特色图像应用于Wordpress中的子页面?
- PHP递归函数删除所有子节点导致stackoverflow
- PHP按照 年、月、日创建递归目录
- php 无限级分类 递归+sort排序 和 非递归
- 使用python api递归计算每个Dropbox文件夹大小
- 学习python的第十六天(迭代器,三元表达式,列表生成式,字典生成式,
- 绕脑的汉诺塔递归