分治

分治法的基本思想：分治法將一個(gè)難以直接解決的大問題分解成一些規(guī)模較小的子問題，分別解決各個(gè)子問題，再合并子問題的解得到原問題的解。

漢諾塔問題

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A、B、C)，在A桿自下而上、由大到小按順序放置64個(gè)金盤。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

public class DivideAndConquer {
    // 漢諾塔問題，遞歸
    public static void hanoi(int n, String a, String b, String c) {
        if (n == 1) {
            // 只有一個(gè)盤，則直接從a移動(dòng)到c
            System.out.println("第1個(gè)盤子移動(dòng)：" + a + "-->" + c);
        } else {
            // 1. 以C盤為中介，從A桿將1至n-1號(hào)盤移至B桿
            hanoi(n - 1, a, c, b);
            // 2. 將A桿中剩下的第n號(hào)盤移至C桿
            System.out.println("第" + n + "個(gè)盤子移動(dòng)：" + a + "-->" + c);
            // 3. 以A桿為中介，從B桿將1至n-1號(hào)盤移至C桿
            hanoi(n - 1, b, a, c);
        }
    }

    public static void main(String[] args) {
        hanoi(3, "A", "B", "C");
    }
}