2021年4月15日 星期四

Python 河內塔 (漢諾塔)

河內塔（中國大陸：漢諾塔，香港：河內塔）是根據一個傳說形成的數學問題

有三根杆子A，B，C。A杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：

A.每次只能移動一個圓盤；
B.大盤不能疊在小盤上面。

提示：可將圓盤臨時置於 B 杆，也可將從 A 杆移出的圓盤重新移回 A 杆，但都必須遵循上述兩條規則。

先用迴圈來寫，但寫得不好，有些違反 "每次只能移動一個圓盤" ，下次再修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
start_list=list()
Buffer_list=list()
End_list=list()

def print_list():
    print("START  : ",start_list)
    print("BUFFER : ",Buffer_list)
    print("END    : ",End_list)
    print("=================================")

Level_num=int(input("請輸入Hanoi塔層數 (>2) : "))
End_num=0

for i in range(1,Level_num+1):
    start_list.append(i)

print (start_list)
if len(Buffer_list)==0:
    Buffer_list.append(start_list[0])
    del start_list[0]
if len(End_list)==0:    
    End_list.append(start_list[0])
    del start_list[0]
print_list()

while True:
    if len(Buffer_list)>0:
        if Buffer_list[0]< End_list[0]:
            End_list.insert(0,Buffer_list[0])
            del Buffer_list[0]
        print_list()
    if len(End_list)>=2 and len(Buffer_list)==0:
        for x in range(len(End_list)):
            Buffer_list.append(End_list[x])
        del End_list[:]
    print_list()
    if len(End_list)==0:    
        End_list.append(start_list[0])
        del start_list[0]
    print_list()
    if len(End_list)>0 and Buffer_list[-1]<End_list[0]:
        for x in range(len(Buffer_list)):
            End_list.insert(x,Buffer_list[x])
        del Buffer_list[:]
    print_list()

    End_num=len(End_list)
    if End_num==Level_num:
        break

再來用遞迴寫，參考一些作法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
start_list=list()
Buffer_list=list()
End_list=list()

def print_list():
    print("START  : ",start_list)
    print("BUFFER : ",Buffer_list)
    print("END    : ",End_list)
    print("=================================")

def hanoi(n,x,y,z):
    if n==1 : 
        if len(z)==0: z.append(x[0])
        else:z.insert(0,x[0])
        del x[0]
        print_list()
    else:
        hanoi(n-1,x,z,y)
        z.insert(0,x[0])
        del x[0]
        print_list()
        hanoi(n-1,y,x,z)

Level_num=int(input("請輸入Hanoi塔層數 (>2) : "))

for i in range(1,Level_num+1):
    start_list.append(i)
print_list()

hanoi(Level_num,start_list,Buffer_list,End_list)

執行結果：


請輸入Hanoi塔層數 (>2) : 3
START  :  [1, 2, 3]
BUFFER :  []
END    :  []
=================================
START  :  [2, 3]
BUFFER :  []
END    :  [1]
=================================
START  :  [3]
BUFFER :  [2]
END    :  [1]
=================================
START  :  [3]
BUFFER :  [1, 2]
END    :  []
=================================
START  :  []
BUFFER :  [1, 2]
END    :  [3]
=================================
START  :  [1]
BUFFER :  [2]
END    :  [3]
=================================
START  :  [1]
BUFFER :  []
END    :  [2, 3]
=================================
START  :  []
BUFFER :  []
END    :  [1, 2, 3]
=================================



張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)