ЕГЭ информатика 5 задание разбор, теория, как решать.

Задание 5. Алгоритм с переводом в систему счисления

В этом типе заданий по информатике (ЕГЭ / СтатГрад) даётся алгоритм обработки числа N:
сначала число переводится в другую систему счисления (чаще в двоичную, иногда в троичную),
потом к полученной записи что-то дописывается по условию (в зависимости от делимости),
после чего результат снова переводится в десятичную систему. Вопрос обычно формулируется так:
«найдите минимальное N, для которого …» или «каково наибольшее значение R».

Что нужно знать

Перевод в двоичную систему в Python: bin(n)[2:]
Пояснение: bin(n) даёт строку вида '0b1011', поэтому берём срез с 3-го символа.
Перевод в троичную систему: в Python нет готовой функции, поэтому пишем свою:

Python

def to_base3(n): s = '' while n > 0: s = str(n % 3) + s n //= 3 return s or '0'

1
2
3
4
5
6

def to_base3(n):
    s = ''
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s or '0'
Обратный перевод:
- из двоичной строки: int(s, 2)
- из троичной строки: int(s, 3)
Целочисленное деление: n // 5 — поделить на 5 и отбросить дробную часть.
Перебор N: такие задачи почти всегда решаются перебором чисел снизу:

Python

for n in range(1, 10000): ...

1
2

for n in range(1, 10000):
...

Общий алгоритм решения

Организовать перебор возможных значений N (например, от 1 до 10000).
Построить запись числа в нужной системе счисления (2 или 3).
Применить правило из условия:
- если N делится на указанное число → приписать одну строку;
- иначе → приписать другую строку (или приписать запись другого числа).
Полученную строку перевести обратно в десятичную систему — это и есть R.
Проверить условие из задачи (например, R >= 783 и N нечётное).
В зависимости от формулировки:
- либо вывести первое подходящее N (если просят «минимальное»);
- либо просмотреть все и взять максимальное R (если просят «наибольшее R»).

Пример (двойичная версия, как в демо / СтатГрад)

Условие типа: «Записать число N в двоичной системе. Если N делится на 5, то приписать справа
две единицы. Иначе приписать справа двоичную запись числа N // 5. Полученную двоичную запись считать двоичным числом.
Найти минимальное нечётное N, для которого результат не меньше 783.»

Функция правила:

def R(n):
    b = bin(n)[2:]          # двоичная запись N
    if n % 5 == 0:          # условие из задачи
        b = b + '11'
    else:
        b = b + bin(n // 5)[2:]
    return int(b, 2)        # обратно в десятичную

def R(n):

b = bin(n)[2:] # двоичная запись N

if n % 5 == 0: # условие из задачи

b = b + '11'

else:

b = b + bin(n // 5)[2:]

return int(b, 2) # обратно в десятичную

1. Поиск минимального N

Использовать, когда в задаче: «укажите минимальное N …».

for n in range(1, 10000):          # перебор снизу
    r = R(n)                        # применяем правило
    if r >= 783 and n % 2 == 1:     # нужное условие
        print(n)                    # нашли минимальное
        break                       # дальше искать не нужно

for n in range(1, 10000): # перебор снизу

r = R(n) # применяем правило

if r >= 783 and n % 2 == 1: # нужное условие

print(n) # нашли минимальное

break # дальше искать не нужно

Идея: перебираем по возрастанию и останавливаемся на первом подходящем — это и есть минимальное.

2. Поиск максимального R

Использовать, когда в задаче: «каково наибольшее значение R»,
«при каком N алгоритм выдаст максимальный результат» и т.п.

max_r = -1
max_n = None

for n in range(1, 10000):
    r = R(n)
    if r > max_r:
        max_r = r
        max_n = n

print(max_r, max_n)

max_r = -1

max_n = None

for n in range(1, 10000):

r = R(n)

if r > max_r:

max_r = r

max_n = n

print(max_r, max_n)

Идея: просматриваются все возможные N, запоминается самое большое значение R
и то N, при котором оно получилось. В отличие от случая «минимальное N», здесь нельзя делать break сразу.

Троичная версия

Если в условии: «запишите число в системе счисления с основанием 3», нужно заменить только две части:
функцию перевода и основание при обратном переводе.

def to_base3(n):
    s = ''
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s or '0'

def R(n):
    t = to_base3(n)
    if n % 3 == 0:
        t = t + '12'        # конкретная приписка из условия
    else:
        t = t + to_base3(n // 3)
    return int(t, 3)        # переводим из троичной в десятичную

def to_base3(n):

s = ''

while n > 0:

s = str(n % 3) + s

n //= 3

return s or '0'

def R(n):

t = to_base3(n)

if n % 3 == 0:

t = t + '12' # конкретная приписка из условия

else:

t = t + to_base3(n // 3)

return int(t, 3) # переводим из троичной в десятичную

Дальше используется тот же шаблон: либо «поиск минимального N», либо «поиск максимального R».

Типичные ошибки

не убирают префикс '0b' у двоичной строки;
используют деление / вместо целочисленного //;
сначала переводят в десятичную, а потом пытаются дописать — нужно наоборот;
забывают ограничение «чётное/нечётное N» в условии;
для задачи «найти наибольшее R» преждевременно выходят из цикла.

Примечание. Такой шаблон покрывает задания из демоверсий, СтатГрада и большинства региональных вариантов, где нужно «приписать что-то к записи числа». В реальном варианте меняются только: основание (2 или 3), условие приписки и проверка в конце (поиск минимального N или максимального R).