Python으로 하노이 타워 Probelem 해결

하노이 탑 문제는 처음에 새로운 프로그래머가 문제 해결 퀴즈를 증폭시키기 위해 소개하는 기본적인 수학적 퍼즐입니다.

문제는 세 개의 막대를 포함하는 간단합니다. 하나의 막대에는 내림차순으로 여러 개의 디스크가 있으며 가장 큰 디스크는 맨 아래에 있고 가장 작은 디스크는 맨 위에 있습니다. 우리는 이것을 두 번째 막대를 사용하여 막대 1에서 막대 3으로 옮겨야합니다.

우리는 특정 규칙을 염두에 두어야합니다. 우리는 동시에 하나의 디스크 만 움직일 수 있으며 막대 상단에있는 디스크를 가져와야합니다. 또한 더 작은 디스크 위에 더 큰 디스크를 배치 할 수 없습니다.
이 모든 것을 염두에두고이 문제를 해결하고이를 해결하는 데 걸린 총 이동 횟수를 계산해야합니다.

이 튜토리얼에서는이 문제를 해결하는 방법을 소개합니다. 파이썬에서 하노이 타워 문제를 해결하기 위해 재귀 적 방법을 사용할 것입니다.

이 메서드는 하노이 타워 문제를 해결하기 위해 몇 가지 조건에 따라 자신을 재귀 적으로 호출하는 함수를 만듭니다.
다음 코드에서 이에 대한 논리를 구현합니다.

def ToH(n, A, B, C):
    if n == 1:
        print("Disk 1 from", A, "to", B)
        return
    ToH(n - 1, A, C, B)
    print("Disk", n, "from", A, "to", B)
    ToH(n - 1, C, B, A)


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

출력:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

위의 예에서는로드 C를 사용하여로드 A에서로드 B로 세 개의 디스크를 이동합니다.

보시다시피 위의 예에서 수행 된 총 이동 수는 7입니다. n 개의 디스크에 대해이 방법을 사용하여 수행 한 총 이동 수는 항상 2 ^ n -1입니다.

시간이 지남에 따라 스택을 사용하여 하노이 타워 문제를 해결하기 위해 몇 가지 다른 솔루션이 등장했습니다. 그러나 이러한 방법은 시간과 속도면에서 매우 비효율적이므로 사용하지 않는 것이 좋습니다.