b023: 河內塔
Tower of Hanoi algorithm
We will be using Java Recursion to solve this problem and the below step will be performed. Let’s assume there are ‘n’ discs and 3 poles (pole1, pole2, pole3)
Step 1: Move (n-1) discs from pole1 to pole2
Step 2: Move the nth disc (last disc) from pole1 to pole3.
Step 3: Now move the n-1 discs which is present in pole2 to pole3.
河內塔(Tower of Hanoi)這個遊戲源自古印度的一個傳說，它的規則如下：
有 1、2、3 等3根柱子。
一開始在 1 號柱子上由上到下有 1、2、3、…、N 等 N個環。
每次只能移動一個環到另一根柱子，而且號碼大的環不可以放在比它小的環上。
反覆移動這些環，直到所有的環都移到 3 號柱子上。
要完成這個動作，你可以先把 1~N-1 號環移到 2 號柱子上，然後把 N 號環移到 3 號柱子上，
再把 1~N-1 號環移到 3 號柱子上。而如何將 1~N-1 號環移到另一根柱子上，
其實可以再分解成把 1~N-2 號先移走，再移動 N-1 號的方式，
然後再把 1~N-2 號移回來，
注意到了嗎，這就是遞迴。
現在請你寫一個程式，印出將這 N 個環移到另一根柱子的過程。
輸入說明：
輸入一個正整數 N (3<=N<=15)。
輸出說明：
請依照下面輸出範例的格式，印出這些環移動的過程。
範例輸入：
3
範例輸出 ：
Ring 1 from 1 to 3
Ring 2 from 1 to 2
Ring 1 from 3 to 2
Ring 3 from 1 to 3
Ring 1 from 2 to 1
Ring 2 from 2 to 3
Ring 1 from 1 to 3
"""
#def move(n,a,b,c):
# if n == 1:
# print a,'-->',c
# else:
# move(n-1,a,c,b) #将n-1个圆盘最终挪到B柱子上
# move(1,a,b,c) #将A柱子上最大的圆盘挪到已被清空的C柱子上
# move(n-1,b,a,c) #将n-1个圆盘从B柱子上挪回C柱子上
"""
def hanoi(n, A, B, C):
if n == 1:
return [(A, C)]
else:
return hanoi(n-1, A, C, B) + hanoi(1, A, B, C) + hanoi(n-1, B, A, C)
n = int(input("請輸入整數："))
for move in hanoi(n, '1', '2', '3'):
print(move)
print("盤由 %c 移至 %c" % move)
print()
hanoi2(n, '1', '2', '3')
def hanoi3(ndisks, startPeg=1, endPeg=3):
if ndisks:
hanoi(ndisks-1, startPeg, 6-startPeg-endPeg)
print ("Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg))
hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)
hanoi3(ndisks=n) """
def hanoi(ndisks, startPeg=1, endPeg=3):
if ndisks:
hanoi(ndisks-1, startPeg, 6-startPeg-endPeg)
print ("Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg))
hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)
n=int(input(" n---> " ))
hanoi(ndisks=n)
def hanoi(n,source,dest,inter): #inter=intermediate , dest=destination
if n==1:
print ("move 1 from",source,"to",dest)
return
else:
hanoi(n-1,source,inter,dest)
print ("move",n,"from",source,"to",dest)
#function values on hold in memory will be executed....
hanoi(n-1,inter,dest,source)
#main(driver code)
n=int(input("n--> "))
hanoi(n,"a","b","c") #function call
Move disk 1 from peg 1 to peg 3
Move disk 2 from peg 1 to peg 2
Move disk 1 from peg 3 to peg 2
Move disk 3 from peg 1 to peg 3
Move disk 1 from peg 2 to peg 1
Move disk 2 from peg 2 to peg 3
Move disk 1 from peg 1 to peg 3
n--> 4
move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c
move 4 from a to b
move 1 from c to b
move 2 from c to a
move 1 from b to a
move 3 from c to b
move 1 from a to c
move 2 from a to b
move 1 from c to b
>>>
沒有留言:
張貼留言