Ханойская башня

Теоретический материал

Башня Ханоя — это классическая математическая головоломка, придуманная французским математиком Эдуардом Люкасом в 1883 году. Суть головоломки заключается в следующем:

• Имеются три стержня и несколько дисков разного диаметра, которые можно надевать на стержни.
• В начале игры диски укладываются на один из стержней по убыванию диаметра, формируя конус.
• Цель головоломки — переместить всю стопку дисков на другой стержень, соблюдая следующие правила:
  • За один ход можно переносить только один диск.
  • Каждый диск можно класть только на более крупный диск или на пустой стержень.
  • Можно использовать любой из трёх стержней как промежуточный для перекладывания дисков.

Сложность головоломки экспоненциально увеличивается с добавлением дисков, делая задачу всё более захватывающей и сложной. Эта головоломка широко используется для демонстрации рекурсивных алгоритмов и алгоритмического мышления в программировании.

Задача

Ваша задача — написать функцию, которая определяет минимальное количество шагов, необходимых для переноса всех дисков с одного стержня на другой.

Функция:

def tower_hanoi(discs):
    # Ваш код здесь

Аргументы:

• discs (int): Количество дисков на начальном стержне. Количество дисков является положительным целым числом.

Возвращает:

• int: Минимальное количество шагов, необходимых для решения головоломки.

Примеры

tower_hanoi(3) ➞ 7

tower_hanoi(5) ➞ 31

tower_hanoi(0) ➞ 0

Примечание

• Важно помнить, что за один ход можно переместить только один диск.
• Используйте данную задачу как возможность попрактиковаться в реализации рекурсивных функций.

Удачи в решении этой классической задачи, которая является отличным способом развить навыки алгоритмического мышления и понимания рекурсии!