한 노 타 문제 깊이 분석 (python 실현)

우리 가 프로 그래 밍 언어 를 배 울 때 재 귀 함수 라 는 문 제 를 만 날 수 있다.학습 순환 의 대표 적 인 사례 는 바로 한 노 타 문제 이다.이 글 을 통 해 세 개의 접시 와 네 개의 접 시 를 이동 하 는 상세 한 과정 을 관찰 하면 귀 하 는 재 귀 를 깊이 이해 할 수 있 을 뿐만 아니 라 한 노 타의 게임 방법 도 더욱 잘 알 게 될 것 입 니 다.
더 좋 은 읽 기 체험 은 이곳 을 방문 할 수 있다.
규칙.
a, b, c 세 개의 기둥 이 있 고 a 는 위 에서 아래로, 어 릴 때 부터 n 개의 접시 가 있 습 니 다.a 위의 모든 접 시 를 c 로 옮 기 고 한 번 에 한 접시 만 옮 길 수 있 으 며 큰 접 시 는 작은 접시 에 놓 을 수 없습니다.
방법.
  • a 에 접시 가 있 을 때 이 접 시 를 c 로 옮 깁 니 다.
  • a 에 n 개의 접시 가 있 을 때 (n > 1):
    먼저 a 위의 n - 1 접 시 를 b 로 옮 긴 다음 에 a 위의 마지막 접 시 를 c 로 옮 긴 다음 에 b 위의 모든 접 시 를 c 로 옮 깁 니 다.

  • 코드 구현
    def mov(n,a,b,c):
        if n == 1:
            #   a       ,   a   c
            print(a,'-->',c)
        else:
            #   a  n-1      b
            mov(n-1,a,c,b)
            #   a          c
            mov(1,a,b,c)
            #    b     (n-1 )   c
            mov(n-1,b,a,c)
    
    num = abs(int(input('       :')))
    print('
    :') mov(num,'A','B','C')

    세 접시 의 실례
  • a 에 있 는 2 개 를 b 로 옮 겨 주세요.
    먼저 a 의 1 개 를 c 로 옮 긴 다음 에 a 의 마지막 1 개 를 b 로 옮 긴 다음 에 c 에 있 는 하나 만 b 로 옮 깁 니 다.
  • a 의 마지막 하 나 를 c
  • 로 이동 합 니 다.
  • b 에 있 는 두 개 를 c 로 이동 합 니 다.
    먼저 b 위의 하 나 를 a 로 옮 긴 다음 에 b 위의 마지막 하 나 를 c 로 옮 긴 다음 에 a 에 있 는 유일한 하 나 를 c 로 옮 깁 니 다.

  • 즉:
    A --> C A --> B C --> B A --> C B --> A B --> C A --> C
    네 접시 의 실례
  • 먼저 a 에 있 는 세 개 를 b 로 옮 깁 니 다.
    일단 a 에 있 는 2 개 를 c 로 옮 겨 주세요.
    먼저 a 의 1 개 를 b 로 옮 긴 다음 에 a 의 마지막 1 개 를 c 로 옮 긴 다음 에 b 에 있 는 하나 만 c 로 옮 깁 니 다.
    a 의 마지막 하 나 를 b 로 이동 합 니 다.
    c 에 있 는 두 개 를 b 로 옮 겨 주세요.
    먼저 c 의 하 나 를 a 로 옮 긴 다음 c 의 마지막 하 나 를 b 로 옮 긴 다음 에 a 에 있 는 유일한 하 나 를 b 로 옮 깁 니 다.
  • a 의 마지막 하 나 를 c
  • 로 이동 합 니 다.
  • b 에 있 는 3 개 를 c 로 옮 겼 다.
    b 에 있 는 2 개 를 a 로 옮 겨 주세요.
    b 에 있 는 1 개 를 c 로 옮 긴 다음 b 에 있 는 마지막 1 개 를 a 로 옮 긴 다음 c 에 있 는 1 개 를 a 로 옮 깁 니 다.
    b 의 마지막 하 나 를 c 로 이동 합 니 다.
    a 에 있 는 두 개 를 c 로 옮 겨 주세요.
    먼저 a 의 하 나 를 b 로 이동 시 킨 다음 에 a 의 마지막 하 나 를 c 로 이동 시 킨 다음 에 b 에 있 는 하 나 를 c 로 이동 시 킵 니 다.
    즉:
    A --> B A --> C B --> C A --> B C --> A C --> B A --> B A --> C B --> C B --> A C --> A B --> C A --> B A --> C B --> C

  • 이렇게 하면 이동 의 각 절 차 를 뚜렷하게 볼 수 있다.
    총결산
    다시 한 번 거꾸로 분석 해 보면 한 접 시 를 이동 할 때 한 걸음 이면 완성 할 수 있 고 코드 에 대응 하 는 것 이다.
        if n == 1:
            #   a       ,   a   c
            print(a,'-->',c)

    접시 두 개 를 옮 길 때 는 세 걸음 이 걸 려 야 완성 할 수 있다.예 를 들 어 a 위의 두 접 시 를 c 로 이동 합 니 다.
  • a 에 있 는 1 개 를 b
  • 로 먼저 이동
  • a 의 마지막 1 개 를 c
  • 로 이동
  • b 에 있 는 하나 만 c
  • 로 이동 합 니 다.
    세 접 시 를 옮 길 때 는 두 접 시 를 먼저 옮 기 고 한 접 시 를 옮 기 는 것 으로 분해 된다.네 개의 접 시 를 옮 길 때 세 개의 접 시 를 먼저 옮 기 고 한 접 시 를 옮 기 는 것 으로 분해 된다.순서대로 유추 하 다.
    두 개 또는 두 개 이상 의 접 시 를 움 직 일 때 모두 세 걸음 이면 완성 할 수 있다 는 것 을 알 수 있다.그 중 한 걸음 한 걸음 은 접시 가 하나 남 을 때 까지 세 걸음 으로 나 눌 수 있다.코드 에 대응 하 는
        else:
            #   a  n-1      b
            mov(n-1,a,c,b)
            #   a          c
            mov(1,a,b,c)
            #    b     (n-1 )   c
            mov(n-1,b,a,c)

    그래서 한 노 타 문제, 알 겠 나?
    참고: python 에서 한 노 타 실현

    좋은 웹페이지 즐겨찾기