Пробный урок
📘 ЕГЭ по информатике 2027 · задание 5 из 27

Задание 5 ЕГЭ по информатике: Формальное исполнение линейного алгоритма для исполнителя

Что проверяет задание 5, сколько баллов оно приносит и сколько времени на него закладывать — и 3 примера в формате ФИПИ с подробным решением и ответом.

Уровень
базовый
Максимум
1 балл
Время
~4 минуты
Компьютер
не нужен

Примеры задания 5 с решениями

Сначала попробуйте решить сами, затем откройте решение и сверьте ответ

Пример 1

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R так: 1. Строится двоичная запись числа N. 2. К этой записи справа дописывается остаток от деления суммы её цифр на 2. 3. К полученной записи справа ещё раз дописывается остаток от деления суммы её цифр на 2. Полученная запись является двоичной записью числа R. Укажите минимальное число R, которое больше 97 и может быть получено в результате работы алгоритма.
Показать решение и ответ
1. Разбираемся, что дописывается в конце. Если в записи N чётное число единиц, дописывается 0, единиц остаётся чётное число — дописывается ещё 0: окончание 00. Если нечётное — дописывается 1, единиц становится чётное число — затем 0: окончание 10. 2. Значит, R чётное, и его две последние цифры определяются чётностью числа единиц в остальной части. 3. Проверяем чётные числа больше 97: 98 = 1100010: остальная часть 11000 — две единицы, нужно окончание 00, а стоит 10 — не подходит. 100 = 1100100: часть 11001 — три единицы, нужно 10, а стоит 00 — не подходит. 102 = 1100110: часть 11001 — три единицы, окончание 10 — подходит. Проверка программой:
for n in range(1, 100):                 # перебираем исходные N по возрастанию
    b = bin(n)[2:]                      # двоичная запись N без префикса 0b
    for _ in range(2):                  # шаг дописывания выполняется дважды
        b += str(b.count('1') % 2)      # дописываем остаток от деления суммы цифр на 2
    r = int(b, 2)                       # переводим запись обратно в число
    if r > 97:                          # R растёт вместе с N, поэтому первое R > 97 — минимальное
        print(r)                        # печатаем ответ
        break                           # дальше перебирать незачем

Ответ: 102

Пример 2

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R так: 1. Строится двоичная запись числа N. 2. Если N делится на 3, к записи справа дописываются три её последние двоичные цифры; иначе справа дописывается двоичная запись числа (N mod 3) · 3. Полученная запись является двоичной записью числа R. Укажите минимальное число N, для которого R больше 151.
Показать решение и ответ
1. Перебираем N по возрастанию и строим R. R растёт не монотонно, поэтому проверяем подряд, а не ищем «первое большое N». 2. N = 15 (1111, делится на 3): 1111 + 111 = 1111111 = 127. 3. N = 16 (10000, остаток 1 → 3 = 11): 1000011 = 67. N = 17 (остаток 2 → 6 = 110): 10001110 = 142. N = 18 (делится): 10010 + 010 = 10010010 = 146. N = 19: 1001111 = 79. 4. N = 20 (10100, остаток 2 → 110): 10100110 = 166 > 151. Проверка программой:
for n in range(1, 1000):                      # перебираем N по возрастанию
    b = bin(n)[2:]                            # двоичная запись N
    if n % 3 == 0:                            # N делится на 3
        b += b[-3:]                           # дописываем три последние цифры
    else:                                     # не делится
        b += bin(n % 3 * 3)[2:]               # дописываем двоичную запись остатка, умноженного на 3
    if int(b, 2) > 151:                       # R больше 151
        print(n)                              # первое такое N — минимальное
        break                                 # остановка

Ответ: 20

Пример 3

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R так: 1. Строится двоичная запись числа N. 2. Все цифры записи инвертируются (0 заменяется на 1, 1 — на 0), незначащие нули слева отбрасываются. Получается число M. 3. R = N − M. Укажите наименьшее N, большее 100, для которого R = 29.
Показать решение и ответ
1. Если в записи N ровно k цифр, то N и M вместе дают k единиц: N + M = 2ᵏ − 1. 2. Значит, R = N − M = 2N − 2ᵏ + 1, откуда N = (R − 1 + 2ᵏ) / 2 = 14 + 2ᵏ⁻¹. 3. N должно иметь k двоичных цифр, то есть 2ᵏ⁻¹ ≤ N < 2ᵏ — это выполняется всегда. 4. k = 7: N = 14 + 64 = 78 < 100. k = 8: N = 14 + 128 = 142 > 100. 5. Проверка: 142 = 10001110₂, M = 01110001₂ = 113, R = 142 − 113 = 29. Проверка программой:
for n in range(101, 10000):                                  # N больше 100, по возрастанию
    b = bin(n)[2:]                                           # двоичная запись N
    inv = ''.join('1' if c == '0' else '0' for c in b)       # инвертируем каждую цифру
    m = int(inv, 2)                                          # int сам отбросит незначащие нули
    if n - m == 29:                                          # R = N − M равно 29
        print(n)                                             # первое такое N — наименьшее
        break                                                # остановка

Ответ: 142

Не получается задание 5? Разберём на пробном уроке

Бесплатно покажем, как решать задание 5 и похожие, определим пробелы и составим план подготовки к ЕГЭ.

Записаться бесплатно

Все задания ЕГЭ по информатике

Структура экзамена, баллы и темы — на странице программы ЕГЭ по информатике