PHP怎么實(shí)現(xiàn)漢諾塔算法

本篇內(nèi)容介紹了“PHP怎么實(shí)現(xiàn)漢諾塔算法”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

起源

傳說最早發(fā)明這個(gè)問題的人是法國數(shù)學(xué)家『愛德華·盧卡斯』。

在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

這個(gè)傳說有很多的變本具體是誰就不得而知了，但是留下的數(shù)學(xué)問題卻是很經(jīng)典的。

其留下的數(shù)學(xué)知識：金片的個(gè)數(shù)和移動(dòng)步數(shù)的關(guān)系為 2^n - 1。

• 1個(gè)金片的移動(dòng)次數(shù) 2的1次方減1

• 2個(gè)金片的移動(dòng)次數(shù) 2的2次方減1

• 3個(gè)金片的移動(dòng)次數(shù) 2的3次方減1

• …

• 個(gè)金片的移動(dòng)次數(shù) 2的n次方減1

若傳說屬實(shí)，僧侶們需要 2^64 - 1 步才能完成這個(gè)任務(wù)；假設(shè)他們每秒移動(dòng)一個(gè)金片，就需要 5849 億年才能完成。整個(gè)宇宙現(xiàn)在也不過 137 億年，所以宇宙毀滅還早…（閑的無聊，我還真計(jì)算了一下，如下圖）

基本規(guī)則

漢諾塔算法有2個(gè)基本條件，假設(shè)移動(dòng)的是盤子。

1.每次只能移動(dòng)一個(gè)盤子。
2.小盤子必須要在大盤子的上面。

分析

假設(shè)本次游戲有3根柱子，分別是 A， B， C。其中一根上已經(jīng)有排序好的盤子N個(gè)，最大的在最下面，依次向上盤子越來越小，另外2根空柱子。

初始狀態(tài)如下圖：

需要實(shí)現(xiàn)的最終目標(biāo)是把柱子上所有的盤子都移動(dòng)到另外一根柱子上。

實(shí)現(xiàn)的大概思路：

• 拋開腦子里想著的每一步要怎么走，這個(gè)很復(fù)雜，腦容量估計(jì)不夠，先想最簡單粗暴的解決邏輯。

• 要滿足大盤子在下的基本條件，肯定需要先把A上最大的盤子空出來，然后把最大的盤子放到C柱子上。假設(shè)最大的盤子編號是N。

• 因?yàn)橐苿?dòng)到C，要實(shí)現(xiàn)第一步，肯定需要把 N-1 個(gè)盤子都搬移到B柱子上，只有這樣第N個(gè)盤子（也就是最大的盤子）才能移動(dòng)到C柱子上。

• 把 N-1 個(gè)盤子移動(dòng)到B柱子上，因?yàn)橐獫M足條件大的在下，小的在上，所以這 N-1 個(gè)盤子在B柱子上也是順序的。

• 最后把這 N-1 個(gè)盤子從B柱子上移動(dòng)到C柱子上完成最終目標(biāo)。

概括下：

第一步把A上 N-1 個(gè)盤子移動(dòng)到B上。

為什么要先把 N-1 個(gè)先移動(dòng)到B上？你看，因?yàn)槟阕罱K實(shí)現(xiàn)的是把A上全部的盤子都移動(dòng)到C上，順序又不能變，只能是大的在下，小的在上。那你肯定需要先把最大號的移動(dòng)到C，不然的話就不滿足條件了。

要從A上移動(dòng)最大號盤子到C上，肯定需要把A上最大號盤子空出來，也就是最大號盤子上面的所有盤子都要搬移走。而你只有3根柱子，C上肯定是不能有別的盤子把，不然你就又不滿足條件了，所有這 N-1 個(gè)盤子只能放到B上，而且還是有序的。 也就變成了下圖：

第二步把A上第 N 個(gè)盤子（也就是最大號盤子）移動(dòng)到C上。

這個(gè)就很簡單了把，只要一步，把最大號盤子從A移動(dòng)到C就可以了。如下圖：

第三步把B上 N-1 個(gè)盤子移動(dòng)到C上。

注意：要實(shí)現(xiàn)把 N-1 個(gè)盤子移動(dòng)到C，是不是又變成了找出其中最大盤子，然后先移動(dòng)最大盤子。所以這里的話其實(shí)就變成了重復(fù)第 1，2步驟，從這 N-1 個(gè)中找出最大的先移動(dòng)到C，循環(huán)往復(fù)。

那第三步其實(shí)就等于變更了需求 假設(shè) K = N - 1。
B柱子上有K個(gè)盤子，A柱子是空的，C柱子有最大的盤子所以對于K個(gè)盤子的B柱子而言等同于空。
第一步把B上 K-1 個(gè)盤子移動(dòng)到A上。
第二步把B上第 K 個(gè)盤子移動(dòng)到C上。
第三步把A上 K-1 個(gè)盤子移動(dòng)到C上。
…

就變?yōu)榱讼聢D

先找到剩余的盤子中最大的

然后移動(dòng)最大號盤子

然后循環(huán)下去直到只剩一個(gè)盤子，直接移動(dòng)到C，游戲結(jié)束。

輔助柱子

什么是輔助柱子？假設(shè)你現(xiàn)在所有待移動(dòng)的盤子都在A上，目標(biāo)是移動(dòng)到C上，那么B就是 N-1 個(gè)盤子的輔助柱子。因?yàn)樗麄冎荒軙捍嬖谶@里，不然就不滿足游戲規(guī)則了。

這里需要先找出輔助柱子，不要想怎么實(shí)現(xiàn)，先理清邏輯。

• 要實(shí)現(xiàn)從A移動(dòng)到B，那么C就是輔助柱子

• 要實(shí)現(xiàn)從A移動(dòng)到C，那么B就是輔助柱子

• 要實(shí)現(xiàn)從B移動(dòng)到C，那么A就是輔助柱子

實(shí)現(xiàn)

通過上面的分析可以看到這其實(shí)就是一個(gè)循環(huán)往復(fù)的重復(fù)操作，很類似遞歸，所有這里可以使用遞歸來實(shí)現(xiàn)。

要使用遞歸需要有2個(gè)必要條件

1.求出遞推公式
2.找到退出條件

退出條件很好寫，肯定是只有一個(gè)盤子的時(shí)候，直接移動(dòng)到C柱子上。

那么遞推公式是什么呢？還是根據(jù)上面的邏輯分析，可以分解為3步。

第一步把 【N-1個(gè)】 盤子先從A移動(dòng)到B
第二步把 【第N個(gè)】 盤子從A移動(dòng)到C
第三步把 【剩下的N-1個(gè)】 盤子從B移動(dòng)到C

下面是PHP實(shí)現(xiàn)的偽代碼：

class HanoiTower
{
    // 計(jì)數(shù)器
    public $count = 0;
    /**
     * 漢諾塔實(shí)現(xiàn)
     * 
     * @param $n 盤子號
     * @param $A 初始柱子
     * @param $B 中轉(zhuǎn)站
     * @param $C 目標(biāo)柱子
     */
    public function hanoi($n, $A, $B, $C)
    {
        if ($n == 1) {
            // 退出條件 只剩一個(gè)盤子的時(shí)候直接從A移動(dòng)到C
            $this->biggestOne($n, $A, $B, $C);
        } else {
            // 第一步把 【n-1】 個(gè)盤子從A移動(dòng)到B 此時(shí)C為中轉(zhuǎn)站
            $this->hanoi($n - 1, $A, $C, $B);
            // 第二步把 【第n】 個(gè)盤子從A移動(dòng)到C
            $this->biggestOne($n, $A, $B, $C);
            // 第三步把B上 【剩余的n-1個(gè)】 盤子從B移動(dòng)到C 此時(shí)A為中轉(zhuǎn)站
            $this->hanoi($n - 1, $B, $A, $C);
        }
    }
    /**
     * 移動(dòng)最大的盤子
     * 直接從A移動(dòng)到C
     */
    public function biggestOne($n, $A, $B, $C)
    {
        ++$this->count;
        echo '第', $this->count, '步 ', '把 ', $n, '從 ', $A, '移動(dòng)到', $C, '<br />';
    }
}
$n = 5;
$hanoiTower = new HanoiTower();
echo '這是一個(gè)有 【', $n, '】 個(gè)盤子的漢諾塔：', '<br />';
// 調(diào)用執(zhí)行
$hanoiTower->hanoi($n, 'A', 'B', 'C');
echo '總共需要走：【', $hanoiTower->count, '】 步';

結(jié)果如下：

“PHP怎么實(shí)現(xiàn)漢諾塔算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！