Java 数据结构与算法系列精讲之汉诺塔
时间：2022-11-15 09:47:14 | 栏目：JAVA代码 | 点击：次
概述
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
汉诺塔
汉诺塔 (Tower of Hanoi) 是一个源于印度的古老益智玩具. 汉诺塔由三根柱子和若干大小不同的圆盘组成. 目标是把圆盘从最左边的柱子移到最右边的柱子上. 如图:
递归
递归 (Recursion) 指的是在函数中调用自身. 递归可以帮助我们简化问题, 使用更少的代码达成目标.
汉诺塔实现
public class 汉诺塔 {
// 汉诺塔实现
private static void hanoi(int num, char a, char b, char c) {
String str = "";
// 判断是否为最后
if(num==1) {
str = "盘1从: " + a + "->" + c;
System.out.println(str);
} else {
// 2^(n-1)次, 把除第n个盘从A移动到B
hanoi(num - 1, a, c, b);
str = "盘" + num + "从: " + a + "->" + c;
System.out.println(str);
// 2^(n-1)次, 把除第n个盘从B移动到C
hanoi(num - 1, b, a, c);
}
}
// main
public static void main(String[] args) {
hanoi(3, 'A', 'B', 'C');
}
}
输出结果:
盘1从: A->C
盘2从: A->B
盘1从: C->B
盘3从: A->C
盘1从: B->A
盘2从: B->C
盘1从: A->C