Формат ввода

Формат вывода

Пример 1

11

5

Пример 2

3

2

напиши код на python

Информатика 10 класс Алгоритмы и структуры данных цирковая обезьянка подсчет действий Новый

Для решения этой задачи нужно определить минимальное количество шагов, которое потребуется обезьянке, чтобы получить кучу из n камней, начиная с одного камня. Обезьянка может либо удваивать количество камней, либо добавлять один камень за один шаг.

Мы можем решить эту задачу, двигаясь от числа n к единице, потому что так будет проще определить, какие действия нужно предпринять на каждом шаге. Попробуем объяснить это на примере:

1. Если n четное, то, чтобы получить его, нам нужно было удвоить количество камней на предыдущем шаге. Таким образом, мы можем перейти от n к n/2.
2. Если n нечетное, то на предыдущем шаге мы могли получить его, добавив один камень к n-1. Поэтому мы переходим от n к n-1.

Продолжаем эти шаги, пока не достигнем одного камня. Количество шагов, которые мы предпримем, и будет минимальным количеством действий, необходимых обезьянке.

Вот пример кода на 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, и считаем количество шагов, необходимых для этого.