уже делаю два часа, не поучается!! Цирковая обезьянка еще не может быть полноценным игроком в Ним, но она обучена либо удваивать количество камней в куче, либо добавлять один.
Напишите программу, подсчитывающую минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней. Изначально в распоряжении циркачки всего один камень.
Для начала, нам необходимо понять, как обезьянке можно изменить количество камней в куче. Из условия задачи видно, что у обезьянки есть две опции: либо она может удвоить количество камней в куче, либо добавить один камень.
Далее, мы хотим найти минимальное количество действий, необходимых для получения кучи из n камней, при условии, что у нас изначально только один камень. Для этого мы можем использовать метод динамического программирования.
Давайте создадим массив dp, размер которого будет на 1 больше n, чтобы проиндексировать все возможные количества камней от 0 до n. Каждый элемент dp[i] будет содержать минимальное количество действий, необходимых для получения кучи из i камней.
Теперь, чтобы заполнить массив dp, мы можем использовать следующую логику:
1. Инициализация. Присвоим dp[0] значение 0, так как нам уже дана куча из одного камня.
2. Проход по массиву. Начиная с 1 и до n, мы будем пересчитывать значения dp[i] в зависимости от значения dp[i-1] и dp[i/2], если i делится нацело без остатка на 2.
Для каждого значения i:
- Если i делится на 2, мы можем получить i камней, удвоив количество камней в куче из (i/2) камней, то есть dp[i] = dp[i/2] + 1.
- В противном случае, мы можем получить i камней, добавив один камень к куче из (i-1) камней, то есть dp[i] = dp[i-1] + 1.
3. Вывод результата. В конце, когда массив dp заполнен, мы можем вернуть значение dp[n] как минимальное количество действий для получения кучи из n камней.
Вот пример кода на языке Python:
```
def minimum_actions(n):
dp = [0] * (n+1) # Создаем массив dp размером (n+1)
for i in range(1, n+1):
if i % 2 == 0:
dp[i] = dp[i//2] + 1
else:
dp[i] = dp[i-1] + 1
return dp[n]
# Тестирование кода
n = int(input("Введите количество камней: "))
result = minimum_actions(n)
print("Минимальное количество действий:", result)
```
Обратите внимание, что в данном коде не используется оптимизация с пропуском нечетных чисел, так как заданное условие требует только двух операций: удвоение или добавление одного камня.