9AE10D — Преобразование записи числа: ответ и решение

Впишите правильный ответ.

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

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

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

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

б) над этой записью производятся те же действия $-$ справа дописывается остаток от деления суммы цифр на 2.

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

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 110000₂ = 48₁₀, а для исходного числа 7₁₀ = 111₂ это число 11110₂ = 30₁₀.

Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 253.

В ответе запишите это число в десятичной системе счисления.

Решение задания EGEINF9AE10D

Ответ: 64

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

Пусть s — количество единиц в двоичной записи N, p — остаток s при делении на 2. Первый дописанный бит равен p. Сумма s + p всегда чётна, поэтому второй дописанный бит равен 0. Получаем окончание 00 при чётном s и 10 при нечётном s.
Общая формула: R = 4N + 2p.
Следовательно, R ≥ 4N. Проверяется чётность суммы цифр, а не самого N.

Обоснование конечного перебора.
Ниже проверяются все натуральные N от 1 до 64 включительно. Для минимального N достаточно найти первый подходящий вход: ни одно большее N уже не может улучшить ответ.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 6; N = 2, R = 10; N = 3, R = 12; N = 4, R = 18.
N = 5, R = 20; N = 6, R = 24; N = 7, R = 30; N = 8, R = 34.
N = 9, R = 36; N = 10, R = 40; N = 11, R = 46; N = 12, R = 48.
N = 13, R = 54; N = 14, R = 58; N = 15, R = 60; N = 16, R = 66.
N = 17, R = 68; N = 18, R = 72; N = 19, R = 78; N = 20, R = 80.
N = 21, R = 86; N = 22, R = 90; N = 23, R = 92; N = 24, R = 96.
N = 25, R = 102; N = 26, R = 106; N = 27, R = 108; N = 28, R = 114.
N = 29, R = 116; N = 30, R = 120; N = 31, R = 126; N = 32, R = 130.
N = 33, R = 132; N = 34, R = 136; N = 35, R = 142; N = 36, R = 144.
N = 37, R = 150; N = 38, R = 154; N = 39, R = 156; N = 40, R = 160.
N = 41, R = 166; N = 42, R = 170; N = 43, R = 172; N = 44, R = 178.
N = 45, R = 180; N = 46, R = 184; N = 47, R = 190; N = 48, R = 192.
N = 49, R = 198; N = 50, R = 202; N = 51, R = 204; N = 52, R = 210.
N = 53, R = 212; N = 54, R = 216; N = 55, R = 222; N = 56, R = 226.
N = 57, R = 228; N = 58, R = 232; N = 59, R = 238; N = 60, R = 240.
N = 61, R = 246; N = 62, R = 250; N = 63, R = 252; N = 64, R = 258.

Первый вход, для которого R больше 253: N = 64, R = 258. Все меньшие N есть в таблице и не удовлетворяют требованию.

Проверка выбранного входа: N = 64 = 1000000₂.
Количество единиц равно 1; первый добавляемый бит 1, второй 0.
Преобразованная запись: 100000010₂.
R = 256 + 2 = 258.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 64.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF9AE10D.

Сообщение увидит только команда сайта: на странице оно не публикуется.

КЭС:	3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
Тип ответа:	Краткий ответ

Задание EGEINF9AE10D: Преобразование записи числа

Решение задания EGEINF9AE10D

Помочь улучшить сайт

Комментарии к решению