Tower of Hanoi
編輯歷史
| 時間 | 作者 | 版本 |
|---|---|---|
| 2017-07-19 14:10 – 14:10 | r0 – r1 | |
顯示 diff+ 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 ]
+ *'''
|
||