ЕГЭ Информатика 2020: Разбор алгоритма задачи 6

icoder
20 апреля 2020

Задание основано на алгоритме преобразования натуральных чисел.

Постановка задачи

Алгоритм принимает на вход натуральное число n и строит число r следующим образом:

  1. Строится двоичная запись числа n.
  2. К этой записи справа дописываются два разряда:
      1. Складываются все цифры двоичной записи числа n.
      1. Остаток от деления этой суммы на 2 записывается в конец. Это действие повторяется ещё раз.

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

Разбор алгоритма на примере

Рассмотрим работу алгоритма для n = 10.

  1. Перевод в двоичную систему: 10<sub>10</sub> = 1010<sub>2</sub>.
  2. Вычисление суммы цифр и остатка:
    • Сумма цифр: 1 + 0 + 1 + 0 = 2. Остаток от деления 2 на 2 равен 0. Дописываем 0.
    • Новое число: 10100<sub>2</sub>.
    • Сумма цифр: 1 + 0 + 1 + 0 + 0 = 2. Остаток от деления 2 на 2 равен 0. Дописываем 0.
    • Конечное число r: 101000<sub>2</sub>.

Таким образом, для n = 10, алгоритм выдает r = 101000<sub>2</sub> = 40<sub>10</sub>.

Решение задачи

Найдём минимальное число r > 97, являющееся результатом работы алгоритма. Возьмём число r, близкое к 97, например, 98. Переведём его в двоичную систему: 98<sub>10</sub> = 1100010<sub>2</sub>.

Число r состоит из двоичной записи исходного числа n и двух добавленных разрядов. Удалим два последних разряда: 11000<sub>2</sub>. Переведём обратно в десятичную систему: 11000<sub>2</sub> = 24<sub>10</sub>. Проверим алгоритм для n = 24:

  1. 24<sub>10</sub> = 11000<sub>2</sub>
  2. Сумма цифр: 1 + 1 + 0 + 0 + 0 = 2. Остаток 0.
  3. Сумма цифр: 2. Остаток 0.
  4. Результат: 1100000<sub>2</sub> = 64<sub>10</sub>. Не подходит.

Попробуем число r = 102. Переведём в двоичную систему: 102<sub>10</sub> = 1100110<sub>2</sub>. Удалив два последних разряда, получаем 11001<sub>2</sub> = 25<sub>10</sub>. Проверим алгоритм для n = 25:

  1. 25<sub>10</sub> = 11001<sub>2</sub>
  2. Сумма цифр: 1 + 1 + 0 + 0 + 1 = 3. Остаток 1.
  3. Сумма цифр: 3. Остаток 1.
  4. Результат: 1100111<sub>2</sub> = 103<sub>10</sub>. Не подходит.

Проверим n=26: 26<sub>10</sub> = 11010<sub>2</sub>. Сумма цифр = 3, остаток 1. Сумма цифр = 4, остаток 0. Результат: 1101010<sub>2</sub> = 106<sub>10</sub>. Не подходит.

Проверим n=27: 27<sub>10</sub> = 11011<sub>2</sub>. Сумма цифр = 4, остаток 0. Сумма цифр = 4, остаток 0. Результат: 1101100<sub>2</sub> = 108<sub>10</sub>. Не подходит.

Проверим n=28: 28<sub>10</sub> = 11100<sub>2</sub>. Сумма цифр = 3, остаток 1. Сумма цифр = 4, остаток 0. Результат: 1110010<sub>2</sub> = 114<sub>10</sub>. Не подходит.

Проверим n = 50: 50<sub>10</sub> = 110010<sub>2</sub>. Сумма цифр = 3, остаток 1. Сумма цифр = 4, остаток 0. Результат: 11001010<sub>2</sub> = 202<sub>10</sub>. Не подходит.

Попробуем другое число. Пусть r = 102. Тогда n = 25. 25<sub>10</sub> = 11001<sub>2</sub>. Сумма цифр 3, остаток 1. Сумма цифр 4, остаток 0. Результат 1100110<sub>2</sub> = 102<sub>10</sub>. Подходит!

Минимальное число r > 97, являющееся результатом работы алгоритма, равно 102.

Нравится: 1

Что будем искать? Например,программа