Какую программу нужно написать для подсчета минимального количества действий, чтобы цирковой обезьянке получить кучу

  • 56
Какую программу нужно написать для подсчета минимального количества действий, чтобы цирковой обезьянке получить кучу из n камней? Начально у обезьянки есть всего один камень. Формат ввода: строка, содержащая число n - количество камней в куче. Формат вывода: число - количество необходимых шагов. Пример 1: Ввод - 11, Вывод - 5. Пример 2: Ввод - 3, Вывод - 2. Напишите программу на языке Python.
Котэ
56
Конечно, вот программный код на языке Python, который решает данную задачу:

python
def calculate_steps(n):
steps = 0
while n > 1:
if n % 2 == 0:
n = n // 2
else:
n -= 1
steps += 1
return steps

# Примеры использования программы
print(calculate_steps(11)) # Вывод: 5
print(calculate_steps(3)) # Вывод: 2


Объяснение решения:
Мы можем решить задачу, используя итерацию. Предлагаем следующий подход: если количество камней в куче четное, обезьянке будет выгодно разделить кучу на половины (n//2 камней) - это будет ей дешевле. Если количество камней в куче нечетное, обезьянка будет лучше уменьшить количество камней в куче на 1 (вычесть 1) - это будет ей дешевле. Мы продолжаем повторять эти шаги до тех пор, пока куча не будет содержать только 1 камень. При этом мы подсчитываем количество шагов, чтобы узнать минимальное количество действий для достижения цели.

В предложенном программном коде функция `calculate_steps` принимает число `n` в качестве параметра и возвращает количество необходимых шагов. Мы инициализируем переменную `steps` со значением 0, которая будет использоваться для подсчета шагов. Затем мы использовали цикл `while`, который продолжается до тех пор, пока `n` больше 1. Внутри цикла мы проверяем, является ли `n` четным числом с помощью оператора `%` (остаток от деления на 2). Если `n` четное, то мы делим его на 2 с помощью оператора `//` и присваиваем результат обратно `n`. Если `n` нечетное, мы вычитаем 1 из `n`. Затем увеличиваем значение переменной `steps` на 1. После выхода из цикла, функция возвращает значение `steps`, содержащее количество шагов для получения кучи из одного камня.

Примеры использования программы показывают ответы для входных данных, указанных в задаче. При вводе значения 11, программа выводит 5, что означает, что минимальное количество шагов для получения кучи из 11 камней равно 5. При вводе значения 3, программа выводит 2, означающие, что минимальное количество шагов для получения кучи из 3 камней равно 2.