Задача 6
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
— складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
— над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
1. Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то это число четное). Таким образом, нас будут интересовать только четные числа.
2. Наименьшим возможным числом, превышающим число 83, является число 84. Начнем с него.
3. Переведем 84 в двоичную систему счисления:
84 = 1010100
Выделенная часть — это N. Необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как сумма чисел нечетная. А мы имеем 0. Соответственно, это число не подходит.
4. Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:
86 = 1010110
Выделенная часть — это N. Необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Соответственно, это число подходит.
Ответ: 86
