Hanoi Tower

HanoiTower.java

import java.util.Stack;

/**
 * 递归求解汉诺塔
 */
public class HanoiTower {
    // 三个塔 a、b、c
    Stack<Integer> a,b,c;

    public static void main(String[] args) {
        int num = 5;
        long t0 = System.currentTimeMillis();
        HanoiTower ht = new HanoiTower(num);
        long t1 = System.currentTimeMillis();
        System.out.format("总时间：%d ms，总步数：%d 步", t1-t0,ht.step);
    }

    HanoiTower(int num) {
        // 初始化
        // a塔有从1..num个元素
        a = new Stack<>();
        for (int i = num; i > 0; i--) {
            a.push(i);
        }
        // b塔为空
        b = new Stack<>();
        // c塔为空
        c = new Stack<>();

        printTowers();

        hanoi(a, b, c, num);
    }

    /**
     * 将n个盘从t1移到t3（用t2作为中间塔）
     * @param t1		原始塔
     * @param t2		中间塔
     * @param t3		目标塔
     * @param n		    盘数
     */
    void hanoi(Stack<Integer> t1, Stack<Integer> t2, Stack<Integer> t3, int n) {
        if (n == 1) {
            // 需移动盘数为1个，直接从t1移动到t3
            move(t1,t3);
        } else {
            // 将上面n-1个盘从t1移到t2（t3为中间塔）
            hanoi(t1, t3, t2, n - 1);
            // 将最下面的盘从t1移到t3
            move(t1,t3);
            // 将上面n-1个盘从t2移到t3（t1为中间塔）
            hanoi(t2, t1, t3, n - 1);
        }
    }

    /**
     * 从塔t1移动到塔t2
     * @param t1
     * @param t2
     */
    void move(Stack<Integer> t1, Stack<Integer> t2){
        t2.push(t1.pop());
        step++;
        printTowers();
    }

    /**
     * 打印所有塔的信息
     */
    void printTowers(){
        StringBuffer sb = new StringBuffer();
        sb.append("step=").append(step).append('\n');

        sb.append("A:");
        for (int n : a) sb.append(n).append(' ');
        sb.append('\n');

        sb.append("B:");
        for (int n : b)  sb.append(n).append(' ');
        sb.append('\n');

        sb.append("C:");
        for (int n : c) sb.append(n).append(' ');
        sb.append('\n');

        System.out.println(sb.toString());
    }
    // 步数
    int step;
}