Ханойская башня — это классическая головоломка, состоящая из трех стержней и нескольких дисков разного размера. Цель состоит в том, чтобы переместить все диски из первой башни в третью башню, соблюдая правила, согласно которым за раз можно перемещать только один диск и что диск большего размера не может быть помещен поверх диска меньшего размера. В этом посте я расскажу о решении головоломки Ханойской башни с использованием рекурсии в Python.
Наша цель — построить рекурсивную функцию, которая принимает 4 аргумента: целое число n, представляющее количество дисков, и 3 строки, представляющие имена 3 башен (например, «Башня1», «Башня2», «Башня3»).
Ниже я построил функцию, которая сначала проверяет, есть ли только 1 диск. Если есть, он напечатает сообщение о том, что диск следует переместить из первой башни в третью башню. Если имеется более 1 диска, функция вызовет себя дважды, каждый раз с уменьшением количества дисков на 1. Между этими двумя рекурсивными вызовами будет напечатано сообщение о том, что самый верхний диск следует переместить из первой башни в третья башня.
Список steps предназначен для отслеживания количества шагов, выполненных функцией. При каждом вызове функции к списку steps добавляется значение 1. В конце печатается общее количество шагов путем суммирования значений в списке steps.
Приведенный ниже код является решением головоломки «Ханойская башня».
steps=[]
def tower_of_hanoi(n, Tower1, Tower2, Tower3):
steps.append(1)
if n==1:
print ("Move disk from Tower", Tower1," to Tower", Tower3)
return
tower_of_hanoi(n-1, Tower1, Tower3, Tower2)
print ("Move disk"," from Tower", Tower1," to Tower", Tower3)
tower_of_hanoi(n-1, Tower2, Tower1, Tower3)
# n = number of disks
n = 3
# Run the Tower of Hanoi recursive function
tower_of_hanoi(n,' 1','2','3')
print(f'\nTotal number of steps: {sum(steps)}')
Когда функция вызывается с n = 3 и именами башен как «1», «2» и «3», она решит головоломку «Ханойская башня» для 3 дисков, распечатав шаги, предпринятые для этого, а также печать общего количества пройденных шагов.
Move disk from Tower 1 to Tower 3 Move disk from Tower 1 to Tower 2 Move disk from Tower 3 to Tower 2 Move disk from Tower 1 to Tower 3 Move disk from Tower 2 to Tower 1 Move disk from Tower 1 to Tower 3 Total number of steps: 7
Вот и все, головоломка Ханойской башни решена с помощью рекурсии в питоне.
Спасибо за чтение!
Подпишитесь на эту учетную запись и нажмите кнопку хлопка, чтобы поддержать меня.
Дополнительные материалы на PlainEnglish.io.
Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord.
Повысьте узнаваемость и признание вашего технического стартапа с помощью Circuit.
