[Python 하노이 탑] 하노이 탑

 

💡 하노이 탑

하노이탑은 프랑스 수학자인 루카스가 1883년에 만들어 낸 문제이다.
가운데 기둥을 중심으로 이 기둥을 이용하여 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽기둥으로 옮기는 문제로 이때 원판은 한 번씩만 옮길 수 있고
작은 원판 위에 큰 원판이 놓을 수 없다.

💡 공식

하노이 탑의 원판이 n개 일 때, 이동 횟수 공식 

💡 설명

이 하노이탑 문제를 풀어내기 위해 원판이 이동해야 하는 횟수를 구하는 공식으로 하노이탑공식을 알고 있다면
굳이 직접 하노이탑퍼즐을 풀지 않아도 몇번을 이동해야 하는지 알 수 있다.

하노이탑 공식은 원판이 n개가 있을 경우 2의 n제곱 -1인데요.
만약 4개의 원판이 있을 경우 최소 이동횟수는 2의4제곱-1
16-1이 되므로 총 15번이 되는 공식이다.

💡 코드

def hanoi(n, a, b):
    if n > 1:
        hanoi(n-1, a, 6-a-b)              # 기둥이 1개 이상이면 그룹으로 묶인 n-1개 원판을 
                                          # 중간으로 먼저 다 옮긴다
    print('원반 {}를 {} 기둥에서 {} 기둥으로 옮깁니다.'.format(n, a, b))

    if n > 1:
        hanoi(n-1, 6-a-b, b)

n = int(input())

print(2**n -1)                               #총 이동해야 하는 횟수
hanoi(n, 1, 3)

 

프로그램 시작 시 input 을 통하여 원반 개수를 입력한다.

hanoi(n, 1, 3) 함수는 1기둥에 쌓인 원반 n 개를 3기둥으로 옮긴다.

위에 작성한 공식대로 2**n 2 의 n 제곱 (n은 입력받은 수) 8-1 = 7로 총 이동해야 하는 횟수를 알 수 있다.

코드 : print(2**n -1)

 

n개의 원판이 있을때, n - 1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을

1번에서 2번으로 옮긴 뒤, 맨 밑의 원판을 1번에서 3번으로 옮긴다.

그리고 n - 1개의 원판들을 다시 2번에서 3번으로 옮긴다.

 

💡 실행 결과