河內塔

河內塔是一道經典數學謎題，規則如下

1. 將第一根柱子上的碟子移動到第三根柱子
2. 每次只能移動一個碟子
3. 碟子只能放在這三根柱子中
4. 碟子有大小之分，小的只能疊在大的上面

這並非一個無解的題，多嘗試一定試得出來
因此重點在最佳解，即如何用最少的步驟完成
數學公式為 2 ^ n - 1
因此 10 個盤子就至少要移動 1023 次
難怪益智玩具通常不會超過 7 片

如果在程式中，通常是考遞迴
不過若沒有這題的數學背景，是寫不太出來的
而知道了數學邏輯，就只是把它轉換成程式語言而已

步驟拆解：

1. 將 A 塔頂部的 N-1 塊盤移動到 B 塔
2. 將 A 塔的底盤移到 C 塔
3. 將 B 塔的 N-1 塊盤移到 C 塔

public class Hanoi {

    public static void main(String[] args) {
        int level = 5;
        printSteps(level, 'A', 'B', 'C');
        System.out.println(countMoves(level));
    }

    public static void printSteps(int n, char a, char b, char c) {
        if(n == 1) {
            System.out.printf("move disk from %s to %s%n", a, c);
        } else {
            printSteps(n - 1, a, c, b);
            printSteps(1, a, b, c);
            printSteps(n - 1, b, a, c);
        }
    }

    public static int countMoves(int n) {
        int sum = 2;
        for (int i = 0; i < n - 1; i++) {
            sum *= 2;
        }
        return sum - 1;
    }
}