Контрольные тренировочные задания
(решения)

Часть 1

Задание 6

Решение примера 3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

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

Ответ: ________

Решение.

Операция проводится два раза, значит к числу N добавляется два разряда.
Определим, что может быть окончанием числа R, то есть вот эти два разряда.
Если изначально сумма разрядов не четное, допустим 10000, то сначала оно будет преобразовано в 100001, т.к. сумма разрядов равна 1, затем в 1000010, т.к. сумма разрядов равна 2.
Если число разрядов не четное, допустим 11000, то сначала оно будет преобразовано в 110000, т.к. сумма разрядов 2, затем в 1100000, т.к. сумма разрядов не изменилась.

Проще говоря, окончанием числа может быть либо 10 (если сумма разрядов N нечетное), либо 00 (если сумма разрядов N четная), других вариантов существовать не может.

Теперь рассмотрим число 97. 97 в двоичной сс - 1100001
При этом 1100001 - это R, исходное число N на два разряда меньше, то есть 11000.
Если мы выполним алгоритм для этого числа N, у нас получится 1100000, то есть число будет меньше 97-ми. Поэтому берем N на единицу больше, то есть 11001.
11001. Сумма разрядов нечетная, добавляем 1 в конец -> 110011
110011. Сумма разрядов четная, добавляем 0 в конец -> 1100110

То есть наименьшая N, которое даёт R > 97 - 11001 в двоичной или 25 в десятичной.

Возврат на страницу    Решение примеров части 1 задание 6