漢諾塔
文章目錄
- 漢諾塔
- 前言
- 時間線
- 故事背景
- 問題延申：經典漢諾塔
- 邏輯演算
- 代碼處理
- 物件定義
- 動作定義
- 遞回
- 計數
- 代碼實作
- 總結
前言
關于漢諾塔的記憶很早就有了，無論還是益智玩具，還是電影片段
漢諾塔一直都是智力游戲的象征，
在后來的編程中，也接觸到了漢諾塔，
時間線
| 時間 | 內容 |
|---|---|
| 2021年5月1日 | 完成初稿 |
故事背景
漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，
問題延申：經典漢諾塔
在上面的故事背景中，如果有3根柱子，一根柱子上有n個盤子，盤子的大小從上往下逐漸增大，如何將一根柱子上的全部圓盤移動到另一個柱子上，進行場景模擬和統計移動次數，
邏輯演算
假設3根柱子分別是柱子a，b，c，柱子a上有n個盤子，設定為盤子1，盤子2等，大的盤子不可以在小的盤子的上面，即盤子2只能在盤子1的下面，
當n=1，n=2或者n=3很容易就能夠演算出來，如下：
- n=1
直接將盤子1從柱子a遷移到柱子c即可，如圖
- n=2
主要有3個步驟：
- 將盤子1從柱子a移動到柱子b
- 將盤子2從柱子a移動到柱子c
- 將柱子b的盤子1移動到柱子c
如圖
如果說n=1或者n=2的移動中沒有發現些什么線索，那么下面的n=3將會是非常好的突破點
- n=3
按照游戲規則，則有以下步驟：
- 將盤子1從柱子a移動到柱子c
- 將盤子2從柱子a移動到柱子b
- 將盤子1從柱子c移動到柱子b
- 將盤子3從柱子a移動到柱子c
- 將盤子1從柱子b移動到柱子a
- 將盤子2從柱子b移動到柱子c
- 將盤子1從柱子a移動到柱子c
如下：
正如前面所說，當n=1，n=2或者n=3時，移動的步驟很容易演算，但是如果n=4，或者n=100，那么步驟將會非常的多，所以需要對上面的演算結果進行分析，即對3種情況進行分析，
分析
-
當n=1時是非常簡單的，將盤子1從柱子a移動到柱子c即可；
-
當n=2時，為了將最大的盤子2移動到柱子c，首先需要將盤子1移開后，才能進行，
當盤子1從柱子a移開后，此時有個非常關鍵的資訊—柱子a就剩下一個盤子2了，
處理邏輯就變成了n=1的情況，即將盤子2從柱子a移動到柱子c；
此時，柱子a沒有盤子，柱子b有一個盤子1，柱子c有一個盤子2
將盤子1從柱子b移動到柱子c即結束
拋開其它規則進行分析，移動的目的是將柱子a上除最大的盤子之外的盤子全部從柱子a上移開，**
**以保證將柱子a的最大的盤子移動到沒有任何盤子的柱子c
有兩個關鍵的資訊：最大的盤子（即最底下的盤子），沒有任何盤子的柱子c
根據這兩個關鍵資訊，則會有以下大體步驟：
- 將除最大的盤子之外的盤子全部移動到柱子b
- 最大的盤子移動到柱子c
- 將柱子b的盤子全部移動到柱子c
注意一個細節：步驟1和步驟3的盤子規模是減1的
那么，根據這個原則，處理n=3的情況時，則有
- 當n=3時，將盤子1和盤子2移動到柱子b，將盤子3移動到柱子c
對n=3移動的步驟進行分析，有：
- 將盤子1從柱子a移動到柱子c
- 將盤子2從柱子a移動到柱子b
- 將盤子1從柱子c移動到柱子b
對應步驟1：將除最大的盤子之外的盤子全部移動到柱子b
此時，問題規模減1，即如何將2個盤子從柱子a移動到柱子b
- 將盤子3從柱子a移動到柱子c
對應步驟2：將最大的盤子移動到柱子c
- 將盤子1從柱子b移動到柱子a
- 將盤子2從柱子b移動到柱子c
- 將盤子1從柱子a移動到柱子c
對應步驟3：將柱子b的盤子全部移動到柱子c
此時，問題規模減1，即如何將2和盤子從柱子b移動到柱子c
（關鍵）那么，當問題規模為n時，則會有
- 將柱子a上的盤子1到盤子n-1移動到柱子b
- 將柱子a的盤子n移動到柱子c
- 將柱子b上的盤子1到盤子n-1全部移動到柱子c
總結
其實對上面的內容進行總結，可以發現處理的程序使用的是遞回，理解的程序可以使用整體思想
拿n=3來說，盤子可以分為2類，將最大的盤子3和除最大的盤子之外的盤子（盤子1和盤子2）
可以將盤子1和盤子2看成是一個整體，那么問題就是如何將2個盤子從柱子a移動到柱子c了，所以也就有了3大步驟，
如下圖：
圖中，
背景綠色的對應步驟1（將除最大盤子之外的盤子移動到柱子b）
背景藍色對應步驟2（將最大盤子移動到柱子c）
背景橙色對應步驟3（將柱子b上的盤子全部移動到柱子c）
所以，無論是多少個盤子，都可以按照n=2的模式解決，
代碼處理
物件定義
最初的打算，是列印移動的資訊就可以了，但是想了一下，還是使用資料結構模擬更真實的漢諾塔，
所以，使用面向物件的思想，定義柱子的資料結構和使用整形定義盤子的大小，
定義柱子
柱子主要有兩個屬性，分別是名稱和容器，即柱子有自己的名稱，也可以裝盤子，
當然，還有一個特點，柱子類似于堆疊，即只能從堆疊頂彈出，裝入堆疊頂，
定義盤子
相對于柱子的定義，盤子使用數值代表大小即可，所以直接使用整形即可，
動作定義
整個程序有一個動作，即將盤子從這個柱子移動到另一個柱子，可以拆解成兩個動作—彈出和裝入，
即將盤子從這個柱子彈出，再裝入另一個柱子上
這里可以使用串列（從尾部放入，從尾部彈出）模擬堆疊
遞回
可以發現，上面總結的3個步驟，其中步驟2是一次移動，而步驟1和步驟3是遞回處理方式，
所以需要注意問題規模和遞回出口
問題規模
由于每一次處理，問題規模都會-1，則遞回函式的引數需要有一個問題規模，即n
遞回出口
遞回出口即只有一個盤子的時候，即n=1時，遞回結束
計數
在問題延申中，有一個統計移動次數的要求，
這個要求的實作有兩種方式—計算和推導，
計算，非常簡單就能實作，即每移動一次，統計次數加1，
在代碼實作中，只要定義全域變數即可，
其實從上面的邏輯演算，可以發現，最少移動次數是有規律的，
如
-
n=1時，需要移動1次；
-
n=2時，需要移動3次；
-
n=3時，需要移動7次；
則很容易就能得到
c
o
u
n
t
=
2
n
?
1
count = 2^{n}-1
count=2n?1
分析（為什么會出現這一結果）
假設f(n)為移動n個盤子的次數，則f(n-1)為移動n-1個盤子的次數，
根據上面步驟，發現移動次數也是由3部分組成
-
當柱子a上有n個盤子時，需要將上面的n-1個盤子移動到柱子b，則移動次數為f(n-1)
-
將盤子n從柱子a移動到柱子c，則移動次數為1
-
將柱子b上的n-1個盤子移動到柱子c，則移動次數為f(n-1)
有
f
(
n
)
=
f
(
n
?
1
)
+
1
+
f
(
n
?
1
)
=
2
f
(
n
?
1
)
+
1
f
(
n
)
+
1
=
2
(
f
(
n
?
1
)
+
1
)
g
(
n
)
=
f
(
n
)
+
1
g
(
n
)
=
2
g
(
n
?
1
)
f(n) = f(n-1)+1+f(n-1)=2f(n-1)+1\\ f(n)+1 = 2(f(n-1)+1)\\ g(n) = f(n)+1\\ g(n) = 2g(n-1)
f(n)=f(n?1)+1+f(n?1)=2f(n?1)+1f(n)+1=2(f(n?1)+1)g(n)=f(n)+1g(n)=2g(n?1)
當n=1時，表示只有1個盤子，移動次數為1，
g
(
n
)
=
f
(
n
)
+
1
=
2
g(n) = f(n)+1 = 2
g(n)=f(n)+1=2
則有
g
(
n
)
=
2
n
f
(
n
)
=
g
(
n
)
?
1
=
2
n
?
1
g(n) = 2^{n}\\ f(n) = g(n)-1=2^{n}-1
g(n)=2nf(n)=g(n)?1=2n?1
當n=1時，
f
(
n
)
=
f
(
1
)
=
1
f(n)=f(1)=1
f(n)=f(1)=1
所以有
c
o
u
n
t
=
f
(
n
)
=
2
n
?
1
count=f(n) = 2^n-1
count=f(n)=2n?1
代碼實作
class Pillar:
def __init__(self,name):
self.name = name
self.res = []
def pop(self):
return self.res.pop(-1)
def push(self,ele):
self.res.append(ele)
def print(self):
print("柱子{}上的盤子:{}".format(self.name,self.res[::-1]))
class Hanoi:
def __init__(self,n:int,a:str,b:str,c:str):
self.count = 0
self.a = Pillar(a)
self.a.res = [n-i for i in range(n)]
self.b,self.c = Pillar(b),Pillar(c)
def print(self):
print("當前柱子的情況（從上往下數）:")
self.a.print()
self.b.print()
self.c.print()
def move(self,f,t):
''' 將柱子f的最上面的盤子ele移動到柱子t '''
if len(f.res) > 0 :
t.res.append(f.res.pop(-1))
self.count += 1
print("第{}次移動：將柱子{}上的盤子{}移動到柱子{}".format(self.count,f.name,t.res[-1],t.name))
def run(self,a,b,c,n):
if n == 1:
self.move(a, c)
else:
self.run(a, c, b, n-1)
self.move(a, c)
self.run(b, a, c, n-1)
if __name__ == "__main__":
number = int(input("請輸入一個數字："))
a,b,c = "a","b","c"
hanoi = Hanoi(number,a,b,c)
hanoi.print()
print("==========游戲開始==========")
hanoi.run(hanoi.a,hanoi.b,hanoi.c,number)
print("經歷{}次移動".format(hanoi.count))
print("==========游戲結束==========")
hanoi.print()
運行結果
總結
其實，在編程中，漢諾塔往往與遞回進行掛鉤，
在經典漢諾塔中，從上面的推理和實作可以發現，并沒有過多的描述遞回，因為遞回就像是俄羅斯套娃，一層套著一層，只有當最底下的娃娃打開以后，才知道最外層的娃娃有什么東西，因為在漢諾塔游戲中，通過腦力計算個位數的移動方式可以說都是一個挑戰了，對于計算機并不是如此，但是如果盤子的數量達兩位數，甚至更多，即使計算機也需要耗費時間，
所以，更多的是推導如何處理，在遞回的處理方式下，使用整體的思想看待漢諾塔游戲，將盤子分為兩類，即無論多少個盤子，都將盤子看成是兩個整體—除最底下盤子之外的盤子和最底下的盤子，這么問題規模逐漸變小，
當然，由漢諾塔延申出來的問題也非常多，如多柱漢諾塔等等，也將會是非常有趣的問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282738.html
標籤：其他
上一篇：canvas個性化時鐘