Tower of Hanoi

百千.IO河內塔

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 ]
• '''