漢諾塔是源于印度一個(gè)古老傳說的益智玩具。大梵天創(chuàng)造世界時(shí)做了三根石柱，在一根柱子上從下往上按大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，三根柱子之間一次只能移動(dòng)一個(gè)圓盤

概述

從今天開始, 小白我將帶大家開啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

漢諾塔

漢諾塔 (Tower of Hanoi) 是一個(gè)源于印度的古老益智玩具. 漢諾塔由三根柱子和若干大小不同的圓盤組成. 目標(biāo)是把圓盤從最左邊的柱子移到最右邊的柱子上. 如圖:

遞歸

遞歸 (Recursion) 指的是在函數(shù)中調(diào)用自身. 遞歸可以幫助我們簡(jiǎn)化問題, 使用更少的代碼達(dá)成目標(biāo).

漢諾塔實(shí)現(xiàn)

public class 漢諾塔 {

    // 漢諾塔實(shí)現(xiàn)
    private static void hanoi(int num, char a, char b, char c) {
        String str = "";

        // 判斷是否為最后
        if(num==1) {
            str = "盤1從: " + a + "->" + c;
            System.out.println(str);
        } else {

            // 2^(n-1)次, 把除第n個(gè)盤從A移動(dòng)到B
            hanoi(num - 1, a, c, b);

            str = "盤" + num + "從: " + a + "->" + c;
            System.out.println(str);

            // 2^(n-1)次, 把除第n個(gè)盤從B移動(dòng)到C
            hanoi(num - 1, b, a, c);
        }
    }

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

輸出結(jié)果: