Задание 5: Исполнитель. Формальные алгоритмы

• Тема: анализ и построение алгоритмов для формальных исполнителей.
• Ответ: целое число или слово.
• Балл: 1. Время: 4 мин. Сложность: базовый (средний процент выполнения: 45%).

Общая информация

Задание 5 проверяет умение работать с формальными исполнителями - алгоритмами, которые выполняют строго определённый набор команд над данными.

Задания: N5.Исполнитель. Формальные алгоритмы | Исполнитель. Формальные алгоритмы. Повышенная сложность

Описание заданий

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

Необходимо определить такое максимальное/минимальное N, чтобы R была в диапазоне (указано в задании, например, R меньше 100)

Имеем число N. Затем шаги:

1. Число преобразуется в 2-чную / 3-чную / 4-чную систему счисления (СС)
2. Задается условие, если оно соблюдено, происходит а), если нет - б) (например: если число четное - слева приписывается "01", если число нечетное - справа убиваются два разряда). После прохождения условия получаем число R в системе счисления, которая задана в 1 пункте
3. Результат переводится в 10-чную сс

Памятка Python для задания 5

Перевод в разные системы счисления

Для перевода в произвольную СС (например, троичную) встроенной функции нет - используем функцию:

def to_base(N): # base - основание сс (3/4-ичная и т.д)
    zapis = "" # пустая строка для записи остатков от деления
    while N > 0: # цикл пока будет идти пока будут числа, которые можно поделить на base
        zapis += str(N % base) # добавляем остаток от деления в строку
        N //= base # целочисленное деление, после именно это число будем делить на base
    return zapis[::-1] # из цикла достаем строку в обратном порядке

Срезы строк

Строковые методы

Проверки чётности и делимости

Конструкция range()

Таблица: формулировка задачи -> код

Алгоритм решения

Чтобы решить задание, нужно уметь переводить числа из десятичной системы в другие системы счисления и обратно. Обратите внимание на один нюанс: многие функции программирования работают только с системами счисления, основания которых находятся в диапазоне от 2 до 36. Это связано с тем, что в алфавите этих функций используются цифры и латинские буквы для представления чисел.

Разберёмся, как решать задание аналитически. Сначала напомним правила Python для перевода числа в разные системы счисления.

# Перевод в двоичную
b = bin(x)[2:]
b = f'{x:b}'
b = format(x, 'b')
# Перевод в восьмеричную
b = oct(x)[2:]
b = f'{x:o}'
b = format(x, 'o')
# Перевод в шестнадцатеричную
b = hex(x)[2:]
b = f'{x:x}'
b = format(x, 'x')
# Перевод в десятичную
a = int(x, b)
где b — основание системы счисления, в которой записано число x (в виде строки).

В режиме Shell можно легко использовать функции для перевода чисел между системами счисления. Для этого не требуется использование команды print или создание переменных — просто введите нужную команду и нажмите Enter, чтобы сразу увидеть результат.

>>> bin(123)
'0b1111011'

Функция возвращает строку, в начале которой префикс '0b'. Чтобы избавиться от него и получить только двоичную запись, используют срез от второго элемента и до конца строки либо другие варианты получения двоичной записи.

>>> bin(123)[2:]
'1111011'
>>> f'{123:b}'
'1111011'
>>> format(123, 'b')
'1111011'

В режиме Shell удобно делать однократные переводы. Чтобы не набирать команду заново, достаточно использовать сочетание Alt + P. Тогда последняя набранная команда вновь появится в строке ввода. Но если нужно много переводов, удобнее написать цикл.

>>> for i in range(100, 110):
...     i, format(i, 'b')
...
(100, '1100100')
(101, '1100101')
(102, '1100110')
(103, '1100111')
(104, '1101000')
(105, '1101001')
(106, '1101010')
(107, '1101011')
(108, '1101100')
(109, '1101101')

Пример использования функции int:

# перевод числа 10110101 из двоичной системы счисления в десятичную 181
>>> int('10110101', 2)
# перевод числа 123 из четверичной в десятичную 27 
>>> int('123', 4)

В Python нет встроенной функции для перевода из десятичной в другие системы счисления, поэтому понадобится написать алгоритм. Его можно оформить, например, в виде следующей функции:

def to_base(x, b):
    s = []
    while x > 0:
        s.append(x % b)
        x //= b
    s.reverse()
    return s

Функция вычисляет список из остатков деления числа на новое основание. Список пригодится для универсальности, так как для систем счисления с основанием больше 10 нужно использовать буквы в качестве цифр.

Элементы в списке представляют собой числовые значения цифр. Например, если в числе есть буквы, они будут записаны как числа больше 9. Так, буква A будет обозначена числом 10.

>>> to_base(123, 2)
[1, 1, 1, 1, 0, 1, 1]
>>> to_base(123, 12)
[10, 3]

Теперь рассмотрим, как использовать электронные таблицы для решения задания № 5. В MS Excel и Libre Office Calc есть функция «основание (число, основание)». Она позволяет переводить числа из десятичной в любую систему счисления и принимает два аргумента:

• число для перевода
• основание системы счисления, в которую требуется перевести

Противоположная ей по действию функция «дес (число; основание)» переводит число в десятичную систему счисления.

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

Задача 1. Аналитическое решение с помощью Python

Для практики решим несколько задач. Вот первая из них.

Обратите внимание на шаг 2. После его выполнения возможны два результата. Если выполнен пункт «а», число заканчивается на *01, где * — любая последовательность нулей и единиц. Если выполнен пункт «б», число имеет вид 1 × 1.

Решать будем с конца. Нам нужно найти минимальное исходное число. Оба пункта увеличивают число на два разряда, поэтому начнём с минимального возможного результата алгоритма. Например, берём число 157 (минимальное значение после 156) и переводим его в двоичную систему с помощью Python.

>>> bin(157)
'0b10011101'

Число оканчивается на 01, поэтому, возможно, подходит пункт «а». Уберём 01 с конца числа и получим 100111₂. Пункт «а» применяется, если число чётное. Число 100111₂ нечётное, поскольку оканчивается на 1, но в этом можно убедиться, переведя его в десятичную систему счисления.

>>> int('100111', 2)
39

Следовательно, пункт «а» тут неприменим.

Проверим пункт «б». Если убрать первую и последнюю единицу из числа, останется 001110₂. Но число не могло начинаться с нулей, поэтому пункт «б» тоже не применим. Возьмём следующее по величине число — 158.

>>> bin(158)
'0b10011110'

Оно тоже не могло быть результатом, поскольку не оканчивается на 01 и не подходит под маску 1 × 1. Следующее подходящее число — 161.

>>> bin(161)
'0b10100001'

Оно оканчивается на 01. До того, как дописали 01, число было 101000₂.

>>> int('101000', 2)
40

Если бы в задаче спрашивали о минимальном R, мы бы нашли ответ. Но вопрос о минимальном N. Поэтому, возможно, пунктом «б» можно получить подходящее число из меньшего N.

Найдём минимальное число, большее 156, которое начинается с двух единиц в двоичной записи и оканчивается на единицу. Это число 193.

>>> int('11000001', 2)
193

До добавления единиц в начало и конец число было 100000₂. Оно чётное, поэтому нам не подходит. Возьмём число на 1 больше, 100001₂. Оно нечётное, поэтому к нему допишется 1 в начало и конец.

>>> int('100001', 2)
33

Число 33 меньше, чем 40, подходит под все требования и является минимальным.

На первый взгляд решение кажется сложным, но многие задания получится выполнить значительно быстрее, чем написать программу, если разобраться во всех этапах. К тому же решить задание двумя способами куда надёжнее, чем одним.

Задача 2. Аналитическое решение с помощью электронных таблиц

Перейдём ко второй задаче.

Поскольку мы используем троичную систему, обратимся к электронным таблицам. Рассмотрим форму итогового числа:

1. Если выполнен пункт «а», то последние две цифры равны предпоследним и число будет выглядеть как *abab.
2. Если выполнен пункт «б», число не делится на 3, то его остаток при делении на 3 равен 1 или 2. После умножения на 5 это будут числа 5 и 10 соответственно. Поэтому число будет оканчиваться этими числами, переведёнными в троичную систему.

Начнём с перевода чисел 5 и 10 в троичную систему.

Теперь перейдём к поиску R. Начиная с числа 134 будем строить троичную запись. Так мы найдём три числа, каждое из которых можно получить, используя этот алгоритм.

Возьмём первое число, 12012₃. До добавления 12 в конец число было равно 120₃. Переведём его в десятичную систему счисления.

Следующее число 12020₃. При дублировании добавились бы цифры 2 и 0, поэтому исходное число — это 120₃. Его мы уже переводили в десятичную систему счисления, это 15. Следовательно, оно нам подходит. Ответ 141.

Задача 3. Решение с помощью программирования

Рассмотрим задачу на преобразование двоичной записи числа.

Условие задачи:

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

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
   • а) если число N чётное, то в этой записи каждая единица заменяется на 11;
   • б) если число N нечётное, то в этой записи каждый нуль заменяется на 00.

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

Примеры:

• Для исходного числа 4₁₀ = 100₂ результатом является число 1100₂ = 12₁₀ (чётное: 1 - 11, 0 - 0, 0 - 0).
• Для исходного числа 5₁₀ = 101₂ это число 1001₂ = 9₁₀ (нечётное: 1 - 1, 0 - 00, 1 - 1).

Вопрос: Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 70.

Пошаговое решение:

Шаг 1. Анализ алгоритма

Для чётных N: каждая единица в двоичной записи удваивается (1 -> 11), нули остаются без изменений. Это увеличивает длину записи и значение числа.

Для нечётных N: каждый нуль удваивается (0 -> 00), единицы остаются без изменений. Это также увеличивает длину записи.

Шаг 2. Написание программы

Используем перебор натуральных чисел от 1 и проверяем результат алгоритма:

for N in range(1, 1000):
    binary = bin(N)[2:]  # двоичная запись N без префикса "0b"
    if N % 2 == 0:  # если число чётное
        binary = binary.replace("1", "11")  # каждая единица заменяется на 11
    else:  # если число нечётное
        binary = binary.replace("0", "00")  # каждый нуль заменяется на 00
    R = int(binary, 2)  # переводим двоичную запись в десятичную
    if R > 70:
        print(N)  # минимальное N, для которого R > 70
        break

Шаг 3. Трассировка для понимания

Проверим несколько значений вручную:

• N = 4 (чётное): 100 -> 1100 -> R = 12
• N = 5 (нечётное): 101 -> 1001 -> R = 9
• N = 6 (чётное): 110 -> 11110 -> R = 30
• N = 7 (нечётное): 111 -> 111 -> R = 7 (нет нулей)
• N = 8 (чётное): 1000 -> 110000 -> R = 48
• N = 9 (нечётное): 1001 -> 100001 -> R = 33
• N = 10 (чётное): 1010 -> 110110 -> R = 54
• N = 12 (чётное): 1100 -> 111100 -> R = 60
• N = 14 (чётное): 1110 -> 1111110 -> R = 126 > 70 ✓

Шаг 4. Ответ

Программа найдёт N = 14 как минимальное число, для которого R = 126 > 70.

Почему именно 14?

Для чётных чисел с большим количеством единиц результат растёт быстрее:

• 1110 содержит 3 единицы
• После замены: 11 + 11 + 11 + 0 = 1111110
• Это даёт R = 126, что превышает 70

Для меньших чётных чисел результат меньше:

• N = 12: 1100 -> 111100 = 60 < 70
• N = 10: 1010 -> 110110 = 54 < 70

Вывод: Программное решение позволяет быстро найти ответ перебором, не требуя глубокого аналитического анализа структуры двоичных записей.

Заключение

Хотя большинство выпускников решают задание № 5 с помощью программирования, аналитический метод часто бывает таким же эффективным, а иногда и быстрее. Поэтому при подготовке важно пробовать разные способы решения.

Составлено: Лилия С., Андрей Рогов Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике

Удачи на экзамене! 🎓