1.3 移動多少盤子才能完成漢諾塔游戲

難度系數：★★★★☆

被考查系數：★★★★☆

題目描述：

漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。在一個廟里有三根金剛石棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不停地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為輔助，但每次只能搬一個，而且大的不能放在小的上面。經過運算移動圓片的次數為18446744073709551615，看來眾僧們耗盡畢生精力也不可能完成金片的移動。

后來，這個傳說就演變為漢諾塔游戲，游戲規則如下：

1）有三根柱子A、B、C，A柱上有若干盤子；

2）每次移動一塊盤子，小的只能疊在大的上面；

3）把所有碟子從A柱全部移到C柱上；

4）經過研究發現，漢諾塔的破解很簡單，就是按照移動規則向一個方向移動金片；

5）例如3階漢諾塔的移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C。

此外，漢諾塔問題也是程序設計中的經典遞歸問題。

分析與解答：

如果柱子標為ABC，那么要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子時，就將B當作輔助柱。如果盤數超過2個，那么將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A-＞B、A-＞C、B-＞C這三個步驟，而被遮住的部分，其實就是進入程序的遞歸處理。事實上，若有n個盤子，則移動完畢所需次數為2n-1，所以當盤數為64時，則所需次數為：264-1=18446744073709551615，如果對這數字沒什么概念，那么可以假設每秒鐘搬一個盤子，也要約5850億年。

實現代碼如下：

程序的運行結果為