Задание: На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 31. В ответе это число запишите в десятичной системе счисления.
Решение: Обратите внимание, нужно найти наименьшее число N, то есть исходное число, для которого R будет больше 31.
Переведем 31 в двоичную систему счисления:
3110 = 111112
111112 — максимально возможное пятизначное двоичное число, нам нужно, чтобы результат был больше него, значит результат должен быть как минимум шестизначным числом. Наименьшее двоичное шестизначное число — 1000002.
Алгоритм добавляет к исходному числу два разряда, значит число R на два разряда больше числа N. Отсечём от числа 1000002 два последних разряда:
1000
В принципе, уже понятно, что 10002 — подходящее число N, но давайте проверим на нем работу алгоритма.
Алгоритм складывает разряды исходного числа, и остаток от деления на 2 этой суммы дописывает в конец. Сумма разрядов числа 1000 — 1, остаток от деления на 2 равен 1, значит к 1000 справа добавится единица:
10001
Теперь алгоритм снова складывает разряды, и остаток от деления на 2 дописывает справа. Сумма разрядов равна 2, остаток от деления на 2 равен 0, справа добавляется ноль:
100010
То есть исходное число 10002 алгоритм преобразует в число 1000102, и 1000102 — наименьший возможный результат работы алгоритма, который больше числа 31.
Но по заданию мы должны определить N, исходное число. Результат мы получили из числа 10002, то есть 810
Ответ: 8