파이썬, 하노이 탑(hanoi tower) 재귀호출 및 반복문

파이썬, 하노이 탑(hanoi tower) 재귀호출 및 반복문

 

다음은 하노이 탑 재귀 호출 예제입니다. 

def hanoi(n, 시작, 보조, 목표):
    if n==1:
        print(시작, '->', 목표)
        return
    hanoi(n-1, 시작, 목표, 보조)
    print(시작, '->', 목표)
    hanoi(n-1, 보조, 시작, 목표)

print("n=1")
hanoi(1, 1, 2, 3)

print("n=2")
hanoi(2, 1, 2, 3)

print("n=3")
hanoi(3, 1, 2, 3)

 

 

다음은 하노이탑 반복문 예제입니다.

(참조: http://blog.naver.com/PostView.nhn?blogId=sexyback8034&logNo=221085188558)

 

시작=1
보조=2
목표=3
signal = 1
n = int(input())

stack = [n, 1, 2, 3]
cnt = 0

 

while stack:

    목표 = stack.pop()
    보조 = stack.pop()
    시작 = stack.pop()
    n = stack.pop()

    if n==1:
        print(시작, '->', 목표)
        cnt += 1
        signal = 0
        continue        
    if signal == 0:
        print(시작, '->', 목표)
        cnt += 1
        signal = 1
        stack.append(n-1)
        stack.append(보조)
        stack.append(시작)
        stack.append(목표)
        continue        
    stack.append(n)
    stack.append(시작)
    stack.append(보조)
    stack.append(목표)
    if signal != 0:
        stack.append(n-1)
        stack.append(시작)
        stack.append(목표)
        stack.append(보조)

print("%d번 이동" %cnt)

 

<이상>