Tower of Hanoi

河內塔

N塊盤從A塔到C塔 = N-1塊盤從A塔到B塔 + 1塊盤從A塔到C塔 + N-1塊盤從B塔到C塔

用數學計算移動次數

move(N)      = move(N-1)*2 + 1

move(N-1)*2 = move(N-2)*4 + 2

move(N-2)*4 = move(N-3)*8 + 4

move(N-3)*8 = move(N-4)*16 + 8

點點點

move(1)*2^(N-1) = move(0)*2^N + 2^(N-1)

加總等於

move(N) = 1 + 2 + 4 + 8 + ... + 2^(N-1) = 2^N -1 (等比級數)

用程式計算移動次數

• import time
•  
• def printABC():
•     global A,B,C
•     print(A)
•     print(B)
•     print(C)
•     print(’’)
•  
• def hanoi(number, from_tower, to_tower, thru_tower):
•     global count
•     if number == 1:
•         to_tower.append(from_tower.pop())
•         count+=1
•         #printABC()
•         return
•     hanoi(number-1, from_tower, thru_tower, to_tower)
•     to_tower.append(from_tower.pop())
•     count+=1
•     #printABC()
•     hanoi(number-1, thru_tower, to_tower, from_tower)
•  
• A = list(range(21,0,-1))
• B = []
• C = []
• count = 0
• #printABC()
•  
• t0 = time.time()
• hanoi(len(A),A,C,B)
• print(time.time()-t0)
• print(count)

http://zerojudge.tw/ShowProblem?problemid=a268

• import time
•  
• def hanoi(moving_n,from_tower,to_tower):
•     global state, count
•     if moving_n == 1:
•         state[0] = to_tower
•         count+=1
•         #print(state)
•         return
•     hanoi(moving_n-1, from_tower, int(6/from_tower/to_tower))
•     state[moving_n-1] = to_tower
•     count+=1
•     #print(state)
•     hanoi(moving_n-1, int(6/from_tower/to_tower), to_tower)
•  
• state = [1] * 21
• count = 0
• #print(state)
•  
• t0 = time.time()
• hanoi(21,1,2)
• print(time.time()-t0)
• print(count)
•  
• ’’’
• while True:
•     N = int(input())
•     if N == 0:
•         break
•     ini_state = input().split(’ ’)
•     tar_state = input().split(’ ’)
•     ini_state = [ int(item) for item in ini_state ]
•     tar_state = [ int(item) for item in tar_state ]
• ’’’