資訊專欄INFORMATION COLUMN
摘要：概述漢諾塔是一個經典的遞歸問題，雖說看人家寫好的算法程序就那么幾行，但著實理解有一定的難度。查閱了一些資料，參閱別人的思路，對漢諾塔算法進行一番梳理。問題來源有一個梵塔，塔內有三個座，座上有若干個盤子，盤子大小不等，大的在下，小的在上如圖。
概述
漢諾塔是一個經典的遞歸問題，雖說看人家寫好的算法程序就那么幾行，但著實理解有一定的難度。查閱了一些資料，參閱別人的思路，對漢諾塔算法進行一番梳理。
問題來源有一個梵塔，塔內有三個座A、B、C，A座上有若干個盤子，盤子大小不等，大的在下，小的在上（如圖）。
需要把這些個盤子從A座移到C座，中間可以借用B座，但每次只允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。
實例我們從簡單的來看一下如何移動。
只有一個盤子
傻子也知道，直接移動到C座就OK了。
有兩個盤子 [1 2]
把1移動到B
把2移動到C
把1移動到C
有三個盤子 [1 2 3]
把1移動到C
把2移動到B
把1移動到B
把3移動到C
把1移動到A
把2移動到C
把1移動到C
雖說好像感覺有一定規律，但好像說不出來個所以然。
規律對于上面的例子，我們可以總結出兩點：
最后一步肯定是把1移動到C
如果盤子數大于1（1就直接移了），肯定要把最大的盤子上面的全部盤子放到B上，然后將最大的放到C上
由上面的兩點，我們來探究一下遞歸關系。
假設有n個盤子，分別標記為 [1 2 3... n] 大數表示大盤子，已經在A座上放好。
初始狀態
A：有n個盤子 B：空 C：空
我們現在有一個方法：hanoi(int n, String a, String b, String c) ，作用就是將n個盤子從a座借助b座移動到c座。
我們先不考慮它是怎么移過去的。
下面我們使用這個方法，結合上面我們總結的規律進行移動盤子。
第一步，將[1 2 3... n-1]個盤子從A移動到B上，再將 n 盤子移動到C上
hanoi(n-1, A, C, B) // 將A上的n-1個盤子移動到B上 hanoi(1, A, B, C) // 將A上的一個盤子移動到C
現在我們的盤子情況為
A：空 B：有n-1個盤子 C：最大的n盤子
由于最大的n盤子上可以放任何盤子，你可以完全忽略它的存在，不用管它，這時候的情形（忽略n盤子的存在）是不是跟初始狀態類似呢（一個有盤子，其余的沒有盤子）？是的，只不過順序發生的變化并且盤子的數量減少了一個。
我們的總盤子數為：n-1
我們的B座就是初始狀態的A座，A座就是初始狀態的B座，C座還是C座。
第二步，將B座上的[1 2 3... n-1-1] 從B移動到A上，將n-1盤子從B移動到C
hanoi(n-2, B, C, A) // 將B上的n-1-1個盤子移動到A上 hanoi(1, B, A, C) // 將B上的一個盤子移動到C
現在我們的盤子情況為
A：有n-1-1個盤子 B：空 C：最大的n盤子和倒數第二個n-1盤子
C上的盤子已經擺好，可以認為是空座，是不是又回到了初始狀態的情形呢？是的，盤子數減一。
第三步，將A座上的[1 2 3... n-2-1] 從A移動到B上，將n-2盤子從A移動到C
hanoi(n-3, A, C, B) // 將A上的n-2-1個盤子移動到A上 hanoi(1, A, B, C) // 將A上的一個盤子移動到C
又回到類似第一步執行后的情形了，如此反復，直到所有盤子都成功移動到C上為止。
經過上述的推敲，我們知道，每經過一步，盤子數少一個，并且A和B兩座的位置互換（這里指他們輪流充當初始狀態A的角色）。
代碼實現(Java)public static void hanoi(int n, String a, String b, String c) {
if (n == 1) {
System.out.println("將" + a + "最上面的盤子移動到" + c);
return;
}
// 當前盤子在a上，將當前盤子數-1放到b上
hanoi(n-1, a, c, b);
// 剩下一個放到c上
hanoi(1, a, b, c);
// 當前盤子在b上，b是下一輪的a， a b 換位置，進行下一輪
hanoi(n-1, b, a, c);
}
調用：
hanoi(1, "A", "B", "C"); // 將A最上面的盤子移動到C hanoi(2, "A", "B", "C"); // 將A最上面的盤子移動到B // 將A最上面的盤子移動到C // 將B最上面的盤子移動到C hanoi(3, "A", "B", "C"); // 將A最上面的盤子移動到C // 將A最上面的盤子移動到B // 將C最上面的盤子移動到B // 將A最上面的盤子移動到C // 將B最上面的盤子移動到A // 將B最上面的盤子移動到C // 將A最上面的盤子移動到C
解釋一下a b c 和A B C的關系
A B C是實際的盤子座，a b c表示的是一種狀態，即初始狀態a 表示有待移動的若干個盤子的座，b c始終表示空座（c上可能有盤子，但已經擺好，可以認為為空）。
每移動一輪，A座與B座交換存盤子，若A有盤子，A就是參數a，若B有盤子，B就是參數a，C位置不動。
總之a 始終代表堆著盤子的座。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65418.html
摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...
摘要：漢諾塔問題有三根柱子，源桿，暫存桿，目的桿上有層盤子，由小到大向下排列，現需要將桿的盤子移到桿中要求大的盤在下面，小的盤在上面一次只能移動一個盤子個人思路先分析問題，用數學的歸納法當只有一個盤時，直接移動當有兩個盤時，先將小的移到暫存桿，再 漢諾塔問題： 有三根柱子，源桿A，暫存桿temp，目的桿C A上有n層盤子，由小到大向下排列，現需要將A桿的盤子移到C桿中 ...
摘要：由此可知在前柱是中轉柱在之后也有兩種情況只有上有圓盤。并且我們的游戲目標從一開始的把上所有圓盤移到柱變成了把上所有圓盤移到柱上而在這時中轉柱是柱。現在將步驟分為三個小步驟將上個圓盤全部移到柱上中轉柱柱。 一.漢諾塔問題 ? 漢諾塔是一種古印度游戲，該游戲的實質就是在一塊木板上有三根固定的柱子...
閱讀 3094·2021-09-22 15:54
閱讀 3981·2021-09-09 11:34
閱讀 1767·2019-08-30 12:48
閱讀 1161·2019-08-30 11:18
閱讀 3431·2019-08-26 11:48
閱讀 913·2019-08-23 17:50
閱讀 2119·2019-08-23 17:17
閱讀 1240·2019-08-23 17:12
