快捷導(dǎo)航

Java 細(xì)致圖解帶你分析漢諾塔

更新時(shí)間：2022年03月23日 11:21:30 作者：來(lái)自爪哇的bean

漢諾塔問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。漢諾塔（Hanoi Tower），又稱(chēng)河內(nèi)塔，源于印度一個(gè)古老傳說(shuō)。本文將用Java求解這一問(wèn)題，感興趣的可以學(xué)習(xí)一下

一、漢諾塔問(wèn)題來(lái)源

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

二、問(wèn)題分析

從簡(jiǎn)單問(wèn)題開(kāi)始

直接拿64個(gè)盤(pán)子來(lái)想，可能會(huì)比較難，我們可以先從1個(gè)盤(pán)子開(kāi)始看，如下圖：

一個(gè)盤(pán)子

A -> C?

只有一個(gè)盤(pán)子情況下，我們可以直接將 A 柱子上面的盤(pán)子移到 C 柱子上

需要移動(dòng)一次

兩個(gè)盤(pán)子

當(dāng)有兩個(gè)盤(pán)子時(shí)，我們也可以通過(guò)下面方式實(shí)現(xiàn)：

A -> B? ? ?A->C? ? ?B->C

需要移動(dòng)3次

1.? A -> B

2.? A -> C

?3.? B -> C

?三個(gè)盤(pán)子

?當(dāng)有三個(gè)盤(pán)子時(shí)，移動(dòng)步驟如下：

A -> C? ? ?A -> B? ? ?C -> B? ? ?A -> C? ? ?B -> A? ? ?B -> C? ? ?A -> C

共需要移動(dòng)7次?

?1.? A -> C

2.? A -> B

?3.? C -> B

4.? A -> C

?5.? B -> A

?6.? B -> C

?7.? A -> C

這就完成了3個(gè)盤(pán)子的移動(dòng)

當(dāng)有 4 個(gè)盤(pán)子時(shí)，這個(gè)問(wèn)題其實(shí)就已經(jīng)很復(fù)雜了

規(guī)律推導(dǎo)

1個(gè)盤(pán)子? ? ? 移動(dòng)1次

2個(gè)盤(pán)子? ? ? 移動(dòng)3次

3個(gè)盤(pán)子? ? ? 移動(dòng)7次

……

N 個(gè)盤(pán)子? ? 移動(dòng) 2^N - 1 次

那么64個(gè)盤(pán)子就是需要移動(dòng) 2^64 - 1 次

三、解決問(wèn)題

我們可以通過(guò)遞歸來(lái)解決這個(gè)問(wèn)題，獲得正確的移動(dòng)方式

如果有N個(gè)盤(pán)子該怎么移動(dòng)呢？

整體思路

我們可以先將 N?- 1 個(gè)盤(pán)子從 A 柱借助 C 柱移動(dòng)到 B 柱，再將 A 柱剩下的一個(gè)盤(pán)子移動(dòng)到 C柱，然后將 B 柱上的 N - 1 個(gè)盤(pán)子借助 A 柱移動(dòng)到 C 柱，就完成了所有柱子的移動(dòng)（中間具體移動(dòng)過(guò)程暫不討論）

上代碼

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一個(gè)盤(pán)子的時(shí)候直接移動(dòng)
        System.out.print(src + "->" + dest + "  ");  // 將一個(gè)盤(pán)子從源柱子挪到目標(biāo)柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 將n - 1個(gè)盤(pán)子從源柱子借助目標(biāo)柱子挪到輔助柱子
        System.out.print(src + "->" + dest + "  ");  // 將一個(gè)盤(pán)子從源柱子挪到目標(biāo)柱子
        hanoi(num - 1, help, src, dest);  // 將輔助柱子上n - 1個(gè)盤(pán)子借助源柱子挪到目標(biāo)柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

這段代碼中 src 是源柱子，help是輔助柱子，dest 是目標(biāo)柱子

這是一個(gè)二路遞歸

運(yùn)行結(jié)果：

?這就成功完成了盤(pán)子的移動(dòng)

四、婆羅門(mén)能否完成大梵天的任務(wù)

移動(dòng) 64 個(gè)盤(pán)子需要多長(zhǎng)時(shí)間

在這里我們假設(shè)婆羅門(mén)的人都非常聰明，不需要思考就直接能知道正確的移動(dòng)方法，移動(dòng)一個(gè)盤(pán)子需要一秒鐘，一直不停的移

將2^64 - 1秒換算為年約為5849 4241 7355年（5849.42億年），而地球存在至今不過(guò)45億年，太陽(yáng)系的預(yù)期壽命據(jù)說(shuō)也就是數(shù)百億年。真的過(guò)了5849.42億年，不說(shuō)太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅。

相關(guān)預(yù)言

有預(yù)言說(shuō)，這件事完成時(shí)宇宙會(huì)在一瞬間閃電式毀滅。也有人相信婆羅門(mén)至今還在一刻不停地搬動(dòng)著圓盤(pán)