На вход алгоритма подаётся натуральное число N


На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 57 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Рейтинг: 5.0/1
Просмотров: 308 | Добавил: Ferst (22.01.2019)

Всего ответов: 1

Обсуждение вопроса:
Всего ответов: 1
0 Люсси
22.01.2019 оставил(а) комментарий:
Решение:
Заметим, что после выполнения шага а) всегда получится чётное число единиц. Шаг б) всегда добавит ноль. Таким образом, в конце числа стоит
знак 0, следовательно, оно — чётное. Найдём минимальное чётное число, которое превышает 57 и может являться результатом работы алгоритма.
Проверим число 58.
Отбросим последний ноль — получим число 29.
Найдём двоичное представление 292 = 111012.
Видим, что в двоичном представлении числа 29 чётное число нулей. Поэтому оно могло быть получено после шага а) алгоритма. Если бы число нулей было бы нечётным, то необходимо рассмотреть следующее чётное число –60.

Ответ: 58.
avatar