PHP怎么實現漢諾塔算法

本篇內容介紹了“PHP怎么實現漢諾塔算法”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

起源

傳說最早發明這個問題的人是法國數學家『愛德華·盧卡斯』。

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

這個傳說有很多的變本具體是誰就不得而知了，但是留下的數學問題卻是很經典的。

其留下的數學知識：金片的個數和移動步數的關系為 2^n - 1。

• 1個金片的移動次數 2的1次方減1

• 2個金片的移動次數 2的2次方減1

• 3個金片的移動次數 2的3次方減1

• …

• 個金片的移動次數 2的n次方減1

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

基本規則

漢諾塔算法有2個基本條件，假設移動的是盤子。

1.每次只能移動一個盤子。
2.小盤子必須要在大盤子的上面。

分析

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

初始狀態如下圖：

需要實現的最終目標是把柱子上所有的盤子都移動到另外一根柱子上。

實現的大概思路：

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

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

• 因為要移動到C，要實現第一步，肯定需要把 N-1 個盤子都搬移到B柱子上，只有這樣第N個盤子（也就是最大的盤子）才能移動到C柱子上。

• 把 N-1 個盤子移動到B柱子上，因為要滿足條件大的在下，小的在上，所以這 N-1 個盤子在B柱子上也是順序的。

• 最后把這 N-1 個盤子從B柱子上移動到C柱子上完成最終目標。

概括下：

第一步把A上 N-1 個盤子移動到B上。

為什么要先把 N-1 個先移動到B上？你看，因為你最終實現的是把A上全部的盤子都移動到C上，順序又不能變，只能是大的在下，小的在上。那你肯定需要先把最大號的移動到C，不然的話就不滿足條件了。

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

第二步把A上第 N 個盤子（也就是最大號盤子）移動到C上。

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

第三步把B上 N-1 個盤子移動到C上。

注意：要實現把 N-1 個盤子移動到C，是不是又變成了找出其中最大盤子，然后先移動最大盤子。所以這里的話其實就變成了重復第 1，2步驟，從這 N-1 個中找出最大的先移動到C，循環往復。

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

就變為了下圖

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

然后移動最大號盤子

然后循環下去直到只剩一個盤子，直接移動到C，游戲結束。

輔助柱子

什么是輔助柱子？假設你現在所有待移動的盤子都在A上，目標是移動到C上，那么B就是 N-1 個盤子的輔助柱子。因為他們只能暫存在這里，不然就不滿足游戲規則了。

這里需要先找出輔助柱子，不要想怎么實現，先理清邏輯。

• 要實現從A移動到B，那么C就是輔助柱子

• 要實現從A移動到C，那么B就是輔助柱子

• 要實現從B移動到C，那么A就是輔助柱子

實現

通過上面的分析可以看到這其實就是一個循環往復的重復操作，很類似遞歸，所有這里可以使用遞歸來實現。

要使用遞歸需要有2個必要條件

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

退出條件很好寫，肯定是只有一個盤子的時候，直接移動到C柱子上。

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

第一步把 【N-1個】 盤子先從A移動到B
第二步把 【第N個】 盤子從A移動到C
第三步把 【剩下的N-1個】 盤子從B移動到C

下面是PHP實現的偽代碼：

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

結果如下：

“PHP怎么實現漢諾塔算法”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！