Python: 한 노 타 이동 경로 인쇄 실현

python 소 백 으로서 python 을 처음 배 운 요 며칠 동안 재 미 있 는 문 제 를 만 났 습 니 다. 바로 한 노 타 이동 경로 의 인쇄 입 니 다. 여기 서 간단하게 말씀 드 리 겠 습 니 다.
       한 노 타 문제: 한 노 타 는 세 개의 막대기 A, B, C 로 구성 되 어 있다.A 레버 에는 N 개 (N > 1) 피 어 싱 원반 이 있 고 디스크 의 사 이 즈 는 아래 에서 위로 순서대로 작 아진 다.다음 규칙 에 따라 모든 원반 을 C 대로 옮 겨 야 합 니 다. 매번 원반 하나만 이동 할 수 있 습 니 다.큰 접시 가 작은 접시 위 에 겹 쳐 서 는 안 된다.
       처음에 문 제 를 보고 멍 해 졌 습 니 다. 그래서 저 는 가장 멍청 한 방법 으로 규칙 이 있 는 지 보기 로 했 습 니 다. 저 는 n = 1, 2, 3, 4 시의 모든 이동 경 로 를 썼 습 니 다. 다음 표 와 같 습 니 다.
n=1
n=2
n=3
n=4
A->C
A->B
A->C
A->B
 
A->C
A->B
A->C
 
B->C
C->B
B->C
 
 
A->C
A->B
 
 
B->A
C->A
 
 
B->C
C->B
 
 
A->C
A->B
 
 
 
A->C
 
 
 
B->C
 
 
 
B->A
 
 
 
C->A
 
 
 
B->C
 
 
 
A->B
 
 
 
A->C
 
 
 
B->C
       표 의 경로 에 따라 나 는 경로 절차 수 = 2^ n - 1 을 발 견 했 고 모두 A - > C 에 의 해 등 절차 수의 두 부분 으로 나 뉘 었 다. 이 두 부분 은 n - 1 개의 원반 을 A - > B 와 n - 1 개의 원반 을 B - > C 에서 나 누 는 것 으로 볼 수 있다. 예 를 들 어 n = 4 시 에 모두 2 ^ 4 - 1 = 15 걸음 으로 A - > C 에 의 해 상하 각 7 걸음 으로 나 뉘 었 고 곧 3 개의 원반 을 A - > B 와 3 개의 원반 을 B - > C 에서 나 눌 것 이다.그리고 우 리 는 n = 3 시 A - > C 의 모든 절 차 를 알 고 있 기 때문에 이 두 부분 은 n = 3 시 A - > C 의 변형 으로 볼 수 있 고 자모 가 다 를 뿐이다.
       이로써 이 문 제 는 재 귀 문제 로 볼 수 있 고 논리 도 간단 해 졌 다. 실현 코드 는 다음 과 같다.
    

def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
    else:
        move(n-1, a, c, b) #n-1    a->b               
        print(a, '-->', c) # a->c                  
        move(n-1, b, a, c) #n-1    b->c

       이제 이 문제 의 현실 논 리 를 이해 하 겠 습 니 다.이 문 제 는 n - 1 개의 원반 을 B - > C 에서 시작 하 는 것 과 같 고, 이전의 절 차 는 n - 1 개의 원반 을 A - > B 에서 시작 하 는 것 과 같 습 니 다. 왜 일 까요?
       A 에 있 는 n 개의 원반 중 맨 밑 에 있 는 하 나 를 C 의 맨 밑 에 이동 시 키 려 면 나머지 n - 1 개 를 B 에 놓 아야 가장 큰 원반 을 A 에서 C 로 옮 길 수 있 고, 최대 원반 이 C 로 이동 하면 C 에 원반 이 없 는 것 으로 볼 수 있 기 때문이다.즉 n - 1 개의 원반 은 B - > C 에서 나온다.
       따라서 모든 이동 과정 을 고려 하지 않 고 귀착점 을 찾 아 논 리 를 정리 하면 된다.
       That's all, good luck.