Ханойская башня
В этом упражнении вы реализуете головоломку «Ханойская башня» с помощью рекурсивного алгоритма. Цель игры — перенести все диски с одного из трёх стержней на другой, соблюдая следующие правила:
- За один ход можно переместить только один диск.
- Можно взять лишь верхний диск одного стека и положить его поверх другого.
- Нельзя класть больший диск на меньший.
Представленный алгоритм реализует эту игру с четырьмя дисками и тремя стержнями: «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)