Цирковая обезьянка еще не может быть полноценным игроком в Ним, но она обучена либо удваивать количество камней в куче, либо добавлять один.
Напишите программу, подсчитывающую минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней. Изначально в распоряжении циркачки всего один камень.
Строка, содержащая число n - необходимое количество камней в куче.
Число - необходимое количество шагов.
| Ввод | Вывод |
|---|---|
11 |
5 |
| Ввод | Вывод |
|---|---|
3 |
2 |
напиши код на python
Информатика 10 класс Алгоритмы и структуры данных цирковая обезьянка подсчет действий
Для решения этой задачи нужно определить минимальное количество шагов, которое потребуется обезьянке, чтобы получить кучу из n камней, начиная с одного камня. Обезьянка может либо удваивать количество камней, либо добавлять один камень за один шаг.
Мы можем решить эту задачу, двигаясь от числа n к единице, потому что так будет проще определить, какие действия нужно предпринять на каждом шаге. Попробуем объяснить это на примере:
Продолжаем эти шаги, пока не достигнем одного камня. Количество шагов, которые мы предпримем, и будет минимальным количеством действий, необходимых обезьянке.
Вот пример кода на Python, который решает эту задачу:
def min_steps_to_n_stones(n):
steps = 0
while n > 1:
if n % 2 == 0:
n //= 2
else:
n -= 1
steps += 1
return steps
# Пример использования функции
n = 11
print(min_steps_to_n_stones(n)) # Вывод: 5
n = 3
print(min_steps_to_n_stones(n)) # Вывод: 2
В этом коде мы используем цикл while, чтобы продолжать уменьшать n до тех пор, пока оно не станет равным 1, и считаем количество шагов, необходимых для этого.