Дано число n. Какое наименьшее число перекладываний дисков в головоломке «Ханойские башни»* нужно совершить для переноса пирамидки из n дисков c одного стержня на другой?
ВХОДНЫЕ ДАННЫЕ
Программа получает на вход одно натуральное число n, 1≤n≤15.
ВЫХОДНЫЕ ДАННЫЕ
Программа должна вывести одно натуральное число — минимальное число перекладываний дисков, необходимых для переноса пирамидки из n стержней с одного диска на другой.ПРИМЕР
ввод
2
вывод
3
Для решения данной задачи можно использовать рекурсивный подход. Количество перекладываний дисков в головоломке «Ханойские башни» для переноса пирамидки из n дисков можно вычислить с помощью следующей формулы:
количество_перекладываний = 2^n - 1
Вот как это можно реализовать на языке Python:
n = int(input("Введите число n: "))
moves = 2**n - 1
print("Минимальное число перекладываний:", moves)
В этом коде мы сначала получаем входное число n от пользователя. Затем, используя формулу 2^n - 1
, вычисляем минимальное количество перекладываний дисков и сохраняем его в переменной moves
. Наконец, мы выводим результат на экран.
Например, если пользователь вводит число n = 3, то минимальное количество перекладываний будет равно 2^3 - 1 = 7
.