하노이의 탑
이 연습 문제에서는 재귀 알고리즘으로 하노이의 탑 퍼즐을 구현해 보겠습니다. 이 게임의 목표는 다음 규칙을 지키면서 세 개의 막대 중 하나에서 다른 하나로 모든 디스크를 옮기는 것입니다:
- 한 번에 하나의 디스크만 옮길 수 있습니다.
- 각 스택의 맨 위 디스크만 꺼내어 다른 스택의 맨 위에 올릴 수 있습니다.
- 큰 디스크를 작은 디스크 위에 올릴 수는 없습니다.
아래 알고리즘은 네 개의 디스크와 'A', 'B', 'C'라는 세 개의 막대로 이 게임을 구현한 예시입니다. 코드에는 두 가지 실수가 있습니다. 그대로 실행하면 최대 재귀 깊이를 초과하여 콘솔이 멈추게 됩니다. 버그를 찾아서 고칠 수 있을까요?
이 연습은 강의의 일부입니다
Python으로 배우는 자료구조와 알고리즘
연습 안내
- 기본 사례를 수정하세요.
hanoi()함수 호출을 수정하세요.
실습형 인터랙티브 연습
이 예제를 이 샘플 코드를 완성하여 풀어보세요.
def hanoi(num_disks, from_rod, to_rod, aux_rod):
# Correct the base case
if num_disks >= 0:
# Correct the calls to the hanoi function
hanoi(num_disks, from_rod, aux_rod, to_rod)
print("Moving disk", num_disks, "from rod", from_rod,"to rod",to_rod)
hanoi(num_disks, aux_rod, to_rod, from_rod)
num_disks = 4
source_rod = 'A'
auxiliar_rod = 'B'
target_rod = 'C'
hanoi(num_disks, source_rod, target_rod, auxiliar_rod)