中瑞祥解析河內塔背景由來以及算法

背景由來

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

不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢?這里需要遞歸的方法。假設有n片，移動次數是f(n).顯然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時，

算法介紹

其實算法非常簡單，當盤子的個數為n時，移動的次數應等于2^n – 1（有興趣的可以自己證明試試看）。后來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；

若n為奇數，按順時針方向依次擺放 A C B。

⑴按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。

⑵接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤。這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，。

⑶反復進行⑴⑵操作，最后就能按規定完成漢諾塔的移動。

所以結果非常簡單，就是按照移動規則向一個方向移動金片：

如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C

漢諾塔問題也是程序設計中的經典遞歸問題，下面我們將給出遞歸和非遞歸的不同實現源代碼。