В этом задании мы должны написать программу, которая будет подсчитывать минимальное количество действий, необходимых обезьянке, чтобы получить кучу из n камней. Изначально у обезьянки есть только один камень.
Чтобы решить эту задачу, нам нужно использовать динамическое программирование. Мы можем создать массив dp размером (n + 1), где dp[i] будет содержать минимальное количество действий для получения кучи из i камней.
Изначально все значения в массиве dp можно заполнить бесконечно большим числом, чтобы показать, что они пока неизвестны. За исключением dp[1] = 0, так как нам не нужно совершать никаких действий, чтобы получить кучу из одного камня.
Затем мы можем перебрать все значения от 2 до n и заполнить массив dp следующим образом:
Для каждого значения i мы можем рассмотреть два возможных действия обезьянки:
1. Удвоить количество камней в куче: dp[i] = dp[i/2] + 1
2. Добавить один камень в кучу: dp[i] = dp[i-1] + 1
Мы выбираем минимальное количество действий из этих двух вариантов и присваиваем его элементу dp[i].
В конечном итоге, после прохода по всем значениям от 2 до n, мы получаем минимальное количество действий для получения кучи из n камней в переменной dp[n].
for i in range(2, n + 1):
dp[i] = min(dp[i], dp[i-1] + 1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
return dp[n]
# Пример использования:
n = int(input("Введите количество камней: "))
result = min_actions(n)
print("Минимальное количество действий:", result)
```
При вводе значения n = 10, программа выведет "Минимальное количество действий: 4", что значит, что обезьянке понадобится выполнить 4 действия, чтобы получить кучу из 10 камней.
Обратите внимание, что вводимые данные должны быть целыми числами, иначе программа может выдать ошибку. Также, данная программа работает эффективно даже для больших значений n, благодаря использованию динамического программирования.
Нужно удалить ексель
Объяснение: