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

概述

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

漢諾塔

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

遞歸

遞歸 (Recursion) 指的是在函數(shù)中調(diào)用自身. 遞歸可以幫助我們簡(jiǎn)化問(wè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 = "盤(pán)1從: " + a + "->" + c;
            System.out.println(str);
        } else {

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

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

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

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

輸出結(jié)果: