Question

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: a) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; b) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 105. В ответе это число запишите в десятичной системе счисления.

Answer 1

1) Нам нужно число больше - 77, то возможно это число 78 или больше...

2) Переведем 78 в двоичную систему счисления:
78 = 1001110;

3) Проверим число, так как число "1001110" - это результат алгоритма, то делаем все в обратном порядке, а именно убираем два разряда с права:
1001110 = 10011;

4) Переводим это число в десятичную систему счисления:
10011=19;

Ответ: 19.

Answer 2

Давайте пошагово применяем описанный алгоритм и ищем наименьшее число N, для которого результат работы алгоритма больше 105.

Шаг 1: Пусть N = 1. Тогда двоичная запись числа N: 1.

Шаг 2: Допишем два разряда по правилу a): Складываем все цифры двоичной записи: 1 (1). Остаток от деления суммы на 2: 1. Дописываем остаток в конец числа: 11.

Шаг 3: Применяем правило b) к полученной записи (11): Складываем все цифры двоичной записи: 1+1 = 10 (2). Остаток от деления суммы на 2: 0. Дописываем остаток в конец числа: 110.

Шаг 4: Применяем правило b) к полученной записи (110): Складываем все цифры двоичной записи: 1+1+0 = 10 (2). Остаток от деления суммы на 2: 0. Дописываем остаток в конец числа: 1100.

Шаг 5: Применяем правило b) к полученной записи (1100): Складываем все цифры двоичной записи: 1+1+0+0 = 10 (2). Остаток от деления суммы на 2: 0. Дописываем остаток в конец числа: 11000.

Шаг 6: Применяем правило b) к полученной записи (11000): Складываем все цифры двоичной записи: 1+1+0+0+0 = 10 (2). Остаток от деления суммы на 2: 0. Дописываем остаток в конец числа: 110000.

Теперь у нас есть двоичная запись искомого числа R, которая равна 110000.

Переводим двоичное число 110000 в десятичную систему счисления: 110000 (в двоичной) = 32 (в десятичной).

Таким образом, наименьшее число N, для которого результат работы алгоритма больше 105, равно 32 в десятичной системе счисления.