Python을 사용하여 하노이 타워 문제를 구현하는 방법

머리말

하노이탑 문제는 고전적인 문제입니다. 하노이 타워라고도 알려진 하노이 타워는 인도의 고대 전설에서 유래되었습니다. 브라흐마는 세상을 창조했을 때 세 개의 다이아몬드 기둥을 만들었고, 한 기둥에는 64개의 금 원반이 아래에서 위로 크기대로 쌓여 있었습니다. 브라흐마는 브라만에게 디스크를 바닥부터 크기 순서대로 다른 기둥에 재배치하라고 명령했습니다. 또한 원반은 작은 원반 위에서 언제든지 확대될 수 없으며 세 개의 기둥 사이에서 한 번에 하나의 원반만 이동할 수 있다고 규정되어 있습니다. 작동 방법을 물어보십시오.

1. 먼저 재귀가 무엇인지부터 이야기해볼까요?

제가 이해한 바는, 문제가 줄어들 수 없는 지점까지 줄어들 때까지 문제의 크기를 계속해서 줄이는 것입니다. (재귀의 종료 조건에 도달) 그런 다음 작은 문제를 하나씩 해결하면 큰 문제가 해결됩니다. (재귀가 돌아옵니다)

2. 계속해서 원래 문제의 작은 규모로 축소되고, 작은 규모의 원래 문제가 해결되어 원래의 큰 문제가 해결됩니다!

3. 과정은 다음과 같습니다.

규모를 줄이고, 작은 크기부터 해결하고, 다시 되돌아와서 원래 문제를 해결합니다! ! !

4. 재귀의 핵심은 다음과 같습니다.

(1) 재귀 종료 조건이 있습니다.

(2) 끊임없이 자신을 호출하여 문제의 크기를 줄이고 재귀의 끝 조건에 더 가까이 다가갑니다.

하노이 탑 문제

1. 문제 설명

A, B, C라는 세 개의 기둥이 있습니다. 처음에는 기둥 A에 n개의 디스크가 있고, 아래에서 위로, 디스크의 크기는 큰 것부터 작은 것 순입니다. 이동 및 배치 중에는 작은 접시가 큰 접시 위에 있어야 합니다. 규칙을 준수하면서 A기둥에 있는 접시를 모두 C기둥으로 옮기세요. 이동 중에는 B기둥을 사용해도 되지만, 이동 시 작은 접시는 큰 접시 위에 올려 놓아야 한다는 점을 꼭 확인해주세요! ! ! 이사과정을 출력해 주시겠어요?

2. 문제 분석 재귀 프로세스:

(1) C

의 도움을 받아 위쪽 n-1개 판을 A에서 B로 이동합니다. (2) 아래쪽 판을 A에서 C로 이동합니다

(3 ) A의 도움으로 상단 n-1 플레이트를 B에서 C로 이동

재귀의 종료 조건:

문제 규모는 플레이트 수가 0일 때입니다. 왜냐하면 플레이트 수가 0일 때 필요하지 않기 때문입니다. 이동! ! !

3. 코드(Python)

# coding:utf-8

"""
    n为初始时A柱上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""


def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("盘子从%s移动到%s" % (a, c))
        hanoi(n-1, b, a, c)



hanoi(3, "A", "B", "C")

4. 결과 표시

위 내용은 Python을 사용하여 하노이 타워 문제를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!