#漢諾塔問題
- 傳說古老印度在一個聖廟裡，一塊黃銅闆上插着三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的６４片金片聖廟，一塊黃銅闆上插着三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的６４片金片。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片，一次隻移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一概針上時，世界就将在一聲霹靂中消滅，梵塔、廟宇和衆生都将同歸于盡。
- 遊戲規則：從左到右 A B C 柱 大盤子在下, 小盤子在上, 借助B柱将所有盤子從A柱移動到C柱, 期間隻有一個原則: 大盤子隻能在小盤子的下面.
案例1
- 隻有一個盤子時，則直接有A，移動到C 完成。
案例2
-
如果有兩個盤子時，移動方案如下：
A—>B #借助B，幫助C拿到最後一個盤子
A—>C #最後一個盤子移動完成後，剩餘的盤子已經全部到B上了
B—>C #将剩餘的盤子移動到C上，完成
案例3
- 如果有三個盤子，盤子數量N = 3,移動方案如下：
案例4
- 如果有四個盤子，盤子數量N = 4,移動方案如下：
- 經過上面例子，我們可以發現如下規律：
- 當盤子隻有一個是，即N=1,隻有一個動作，從A移動到C即結束
- 當有N個盤子時：
- 上半部分：移動一定和n-1盤子移動時的動作相同。出發地都是A,隻不過，n-1個盤子移動的目的是B，而不是C。這樣友善取出最後一個盤子
- 中間部分：一定是由A移動到C
- 下半部分：此時等待移動的盤子已經都在B上，而不是A上，移動步驟類似于n-1個盤子的移動。出發地是B，目的地是C
遞歸分析
- 經過上面例子可以得到。如果想要移動n個盤子到指定目的，那麼一定要先将n-1個盤子移動到備用柱上。
- 當n-1個盤子移動後，必定要将最後一個盤子移動到C上。
-
經過上面的調換後，剩下待處理的盤子還有n-1個，此時盤子已經在B上而不是在A上。此時需要從新判斷剩餘的盤子個數。如果依然大于1個那麼還是需要按照1的步驟移動第n-1個盤子之上的所有盤子共n-2到A上。進而好讓第n-1個盤子從B移動到C。
總結：到第3步時，發現和有和第一步第二步類似地方。隻需要改變盤子的出發點和目的點，就能剛好遞歸
對應的python實作如下：
def move(n,a,b,c):
if n == 1:
print(a,"--->",c)
else:
move(n-1,a,c,b)
print(a,"--->",c)
move(n-1,b,a,c)
move(4,"A","B","C") 第二種類似方法
n=4
arr11 = arr1 = [_ for _ in range(n,0,-1)]
arr22 = arr2 = []
arr33 = arr3 = []
def move(n,arr1,arr2,arr3):
if n==1: # 如果隻有一個 移動方法一定是由arr1到arr3
arr3.append(arr1.pop()) #arr1 移動的arr3
print(arr11,arr22,arr33,"====",arr1,arr2,arr3) #列印，參考。
else:
move(n-1,arr1,arr3,arr2) # 此時arr2為空元素，将n-1個元素移動到arr2中。
arr3.append(arr1.pop()) # 将最後一個元素，移動到arr3中
print(arr11,arr22,arr33,"====",arr1,arr2,arr3) #列印，參考
# 此時，arr1,為空，而arr2裡面有n-1個元素。重新調用遞歸，将剩餘的元素移動到arr3中（此時剩餘元素有n-1個）即，
# 将arr2中的元素移動到arr3中。
move(n-1,arr2,arr1,arr3)
move(n,arr1,arr2,arr3)