【java练习】汉诺塔递归实现
1. 问题描述
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、 由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在 移动过程中三根杆上都始 终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
2. 问题分析
因为无法直接从题目中获得思路，所以采用数学归纳法进行推导
让n为当前层数上的圆盘编号，当 n=1
的时候：
圆盘1
直接从 A
到 C
当 n=2
的时候：
圆盘1
需要从 A
到 B
圆盘2
需要从 A
到 C
圆盘1
需要从 B
到 C
其中 B
作为中间柱被使用过一次
当 n=n
的时候（将 n-1
看为一个整体）：
A. A
上的 n-1
个圆盘需要从 A
移动到 B
(借助于 C
)
圆盘n
需要从 A
到 C
C. B
上的 n-1
个圆盘需要从 B
到 C
（借助于 A
）
当步骤为A的时候：
1. 将 A
上的 n-2
个圆盘移到 C
上。
2. 将 A
上的第 n-1
个圆盘移到 B
。
3. 将 C
上的 n-2
个圆盘移到 B
。
当步骤为C的时候：
1. 将 B
上的 n-2
个圆盘移到 A
。
2. 将 B
上的第 n-1
个盘子移到 C
。
3. 将 A
上的 n-2
个圆盘移到 C
。
所以从上面可以分析出来，当n>=2的时候可以分为三个步骤：
(A为初始位置，C为中间位置，B为目的位置) (B为初始位置，A为中间位置，C为目的位置)
3. 编码
可以创建方法：
/**
* @param layer 层数
* @param init 初始位置
* @param middle 中间位置
* @param target 目标位置
* @return void
*/
private static void solve(int layer, String init, String middle, String target) {
if (1 == layer) {
System.out.printf("%d从%s移动到%s;/n", layer, init, target);
} else {
solve(layer - 1, init, target, middle); //1.
System.out.printf("%d从%s移动到%s;/n", layer, init, target); //2.
solve(layer - 1, middle, init, target); //3.
}
}
方法说明
System.out.printf("%d从%s移动到%s;/n", layer, init, target);
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
