b023: 河內塔

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 

 n---> 3
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
>>>