汉诺塔问题就是有三张柱子A、B、C,然后初始化在A上放了N个圆盘,圆盘按照小压大的方式堆放,需要用最少的步骤从A柱子上挪到C柱子上。在整个移动的过程中,也必须保持小压大的规则。
如下图所示,需要把A上的四个圆盘挪到C上。
假设A上面有N个圆盘,我们可以把每个圆盘的直径看作是N,那从最下面开始数:盘子直径是N,N-1,N-2,…,2,1
因为到目标柱子C后还需要维持小压大的规则,那第一个到达C柱子的圆盘肯定是最大的圆盘,也就是直径为N的圆盘,那剩下的圆盘(1到N-1)在哪里呢,都在过渡柱子B上。
按照这个逻辑,C上每次放一个除了C上面的圆盘外,最大的圆盘,然后其余的圆盘按照小压大的逻辑放在过度柱子上(有可能是A,也有可能是B)。
由上面可以看出,C上放一个除它外最大圆盘的逻辑是,先从堆满圆盘的柱子上转移圆盘,只剩下一个,然后把这一个圆盘挪到C上。
递归思路很符合上面的思路,一共有三个柱子,from、to、temp,先从from move n-1个圆盘到temp,然后从from move第N个给 to,最后从temp上面把剩余圆盘转移给to。
public static void hanoi(int n) { if (n > 0) { func(n, "A", "C", "B"); } } private static void func(int n, String from, String to, String other) { if (n == 1) { System.out.println("move 1 from " + from + " to " + to); } else { func(n - 1, from, other, to); System.out.println("move " + n + " from " + from + " to " + to); func(n - 1, other, to, from); } }
static class HanoiRecord { int index;//代表盘子的序号 int n; String from; String to; String other; public HanoiRecord(int index, int n, String from, String to, String other) { this.index = index; this.n = n; this.from = from; this.to = to; this.other = other; } } public static void hanoi3(int n) { hanoiNonRecursion(n, "A", "C", "B"); } private static void hanoiNonRecursion(int n, String A, String C, String B) { if (n < 1) return; Stack<HanoiRecord> stack = new Stack<>(); stack.push(new HanoiRecord(n, n, A, C, B)); while (!stack.isEmpty()) { HanoiRecord pop = stack.pop(); if (pop.n == 1) { move(pop.index, pop.from, pop.to); } else { //栈是先进后出的,所以和递归的处理逻辑相反,先把temp到to进栈 stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.other, pop.to, pop.from)); stack.push(new HanoiRecord(pop.n, 1, pop.from, pop.to, pop.other)); stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.from, pop.other, pop.to)); } } } private static void move(int index, String from, String to) { System.out.println("move " + index + " from " + from + " to " + to); }
类HanoiRecord里面的index可以不要,只是用来打印的而已。