汉诺塔问题可视化算法（汉诺塔问题-算法面试题）
在经典的汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时会受到以下限制:
- 每次只能移动一个盘子;
- 盘子只能从柱子顶端滑出移到下一根柱子;
- 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
题目分析- 当 n = 1 时：
start
step1
直接将盘子从pillar1移到pillar3。
- 当 n = 2 时：
start
step1
step1: 将盘子 1 从 pillar1 移到 pillar2
step2
step2: 将盘子 2 从 pillar1 移到 pillar3
step3
step3: 将盘子 1 从 pillar2 移到 pillar3
- 当 n = 3 时：
start
step1
step1: 将盘子 1、2 从 pillar1 移到 pillar2（重复 n=2 时的步骤即可）。
step2
step2: 将盘子 3 从 pillar1 移到 pillar3
step3: 将盘子 1 、2 从 pillar2 移到 pillar3
- 根据上面的例子，我们可以推理出 n 个盘子从 pillar1 移到 pillar3的步骤：
step1: 将盘子 1、2......、n-1 从 pillar1 移到 pillar2
step2: 将盘子 n 从 pillar1 移到 pillar3
step1: 将盘子 1、2......、n-1 从 pillar2 移到 pillar3
代码实现
public class Pillar {
private int index;
private Stack<Integer> pillar = new Stack<>();
public Pillar(int index){
this.index = index;
}
public int getIndex(){
return index;
}
public void add(int disk){
if (!pillar.isEmpty() && disk > pillar.peek()){
System.out.println("Error placing: Disk " disk " is bigger than top disk " pillar.peek());
} else {
pillar.push(disk);
}
}
public void moveTopDiskTo(Pillar destination){
if(pillar.isEmpty()){
System.out.println("Error moving: No disk int pillar " index);
}else {
destination.add(pillar.pop());
}
}
public void moveToPillar(int n, Pillar destination, Pillar buff){
if(n > 0) {
moveToPillar(n - 1, buff, destination);
moveTopDiskTo(destination);
buff.moveToPillar(n - 1, destination, this);
}
}
public Stack<Integer> disks(){
return pillar;
}
public static void main(String[] args) {
Pillar pillar1 = new Pillar(1);
Pillar pillar2 = new Pillar(2);
Pillar pillar3 = new Pillar(3);
int n = 10;
for (int i = n; i > 0 ; i--) {
pillar1.add(i);
}
System.out.println("Start: ");
System.out.println("pillar1: " pillar1.disks());
System.out.println("pillar2: " pillar2.disks());
System.out.println("pillar3: " pillar3.disks());
pillar1.moveToPillar(n, pillar3, pillar2);
System.out.println("end: ");
System.out.println("pillar1: " pillar1.disks());
System.out.println("pillar2: " pillar2.disks());
System.out.println("pillar3: " pillar3.disks());
}
}
免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。
