Подсчитать минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней

@msmmm · Регистрация: 09.10.2018

Студворк — интернет-сервис помощи студентам

Цирк, цирк, цирк!

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

Напишите программу, подсчитывающую минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней. Изначально в распоряжении циркачки всего один камень.

Формат ввода
Строка, содержащая число n - необходимое количество камней в куче.

Формат вывода
Число - необходимое количество шагов.

Пример 1
Ввод
11

Вывод
5
Пример 2
Ввод
3
Вывод
2

Есть код, но когда я к примеру ввожу 4, то программа ничего не делает(то есть просто зависла)

Python
1
2
3
4
5
6
7
8
9
10
11
a = int(input())
summ = 1
summ = summ + 1
h = 1
while summ != a:
    if summ * 2 < a:
        summ *= 2
    if summ * 2 > a:
        summ += 1
    h += 1
print(h)

Кто может, исправьте код пожалуйста

@Veliall · 14.11.2018, 15:01

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
count = 1
c = 0
if n == 2:
    n = 0
    c = 1
if n == 3:
    n = 0
    c = 2
while count < n:
    if n / 2 != n // 2:
        n = n - 1
        c = c + 1      
    if n / 2 == n // 2 and n >= 2:
        n = n // 2 - 1
        c = c + 2
print(c)

Код вроде полностью исправен, но случай с 2 и 3 написаны на отвали.

@Eneanuch · 21.10.2019, 16:55

Берешь число которое вводит пользователь, проверяешь четное или нет, делишь на два или вычитаешь один, соответственно, и так пока не останется единица, и считаешь ходы

@iluxa100 · 23.10.2019, 17:31

Сообщение от grizlik78

Python
1
2
3
4
5
6
7
a = int(input())
count = 0
 
while a > 1:
    count += 1 + a % 2
    a //= 2
print(count)

можешь обьяснить как нибудь, пожалуйста

@grizlik78 · 23.10.2019, 17:50

Было б что объяснять. Если очередное число чётное, то оно получено из предыдущего только умножением на 2, поэтому увеличиваем счётчик на 1. Если число нечётное, то кроме умножения на 2 использовалось ещё прибавление 1, поэтому увеличиваем счётчик на 2. Делим число нацело на 2, чтобы перейти к предыдущему. И так до тех пор, пока не дойдём до единицы.

a % 2 равно единице для нечётного и нулю для чётного.
a //= 2 уменьшает число в 2 раза с отбрасыванием дробной части.

Новые блоги и статьи Все статьи Все блоги /
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений

@Eneanuch 0 / 0 / 0 Регистрация: 19.10.2019 Сообщений: 1
	21.10.2019, 16:55
	Берешь число которое вводит пользователь, проверяешь четное или нет, делишь на два или вычитаешь один, соответственно, и так пока не останется единица, и считаешь ходы 0

@grizlik78 2383 / 1667 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	23.10.2019, 17:50
	Было б что объяснять. Если очередное число чётное, то оно получено из предыдущего только умножением на 2, поэтому увеличиваем счётчик на 1. Если число нечётное, то кроме умножения на 2 использовалось ещё прибавление 1, поэтому увеличиваем счётчик на 2. Делим число нацело на 2, чтобы перейти к предыдущему. И так до тех пор, пока не дойдём до единицы. a % 2 равно единице для нечётного и нулю для чётного. a //= 2 уменьшает число в 2 раза с отбрасыванием дробной части. 0

Подсчитать минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней

Решение