Задание 5. Алгоритмы для исполнителя – ЕГЭ по информатике

Что проверяет задание

Задание 5 – словесно описанный алгоритм: он переделывает запись числа N в другой системе счисления и выдаёт число R. Спрашивают либо минимальное или максимальное R с ограничением, либо минимальное или максимальное N.

1 балл, норматив 4 минуты. Рекомендую решать программированием.Перебор в уме дольше и опаснее, чем написать пять строк.

Что нужно знать заранее:

перевод в двоичную и обратно: bin(n)[2:] даёт запись без приставки 0b, int(s, 2) читает строку как двоичное число. Подробно – в учебнике: двоичная система;
дописать разряд слева или справа – это склейка строк, а не арифметика: '1' + s и s + '00';
перебор в range и отбор минимума или максимума по условию;
запись по любому основанию: если в варианте алгоритм строит троичную запись, понадобится int(s, 3) и свой перевод в систему по основанию. Подробно – в учебнике: позиционные системы счисления.

Типовой пример

Задание 5 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

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

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
а) если число N чётное, то к этой записи справа и слева дописываются по две единицы;
б) если число N нечётное, то в конец двоичной записи (справа) дописываются два нуля, а в начало (слева) дописывается единица.
Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа $13_{10} = 1101_2$ результатом является число $1110100_2 = 116_{10}$, а для исходного числа $6_{10} = 110_2$ это число $1111011_2 = 123_{10}$.

Укажите наименьшее число R, превышающее 95, которое может быть результатом работы данного алгоритма. В ответе запишите это число в десятичной системе счисления.

Два примера в условии даны не для красоты: это готовая проверка будущей программы, и запускать её надо первым делом. Оба примера стоит разобрать по разрядам. 13 нечётное, поэтому единица идёт слева, а два нуля справа: 1101 → 1110100, то есть 116. 6 чётное, поэтому по две единицы с обеих сторон: 110 → 1111011, то есть 123.

Как рассуждать

Правило – это функция от N. Весь текст условия сводится к четырём строкам кода: взять двоичную запись числа, приписать по правилу, прочитать получившуюся строку обратно как число.
Перебирайте N, а не R. Соблазн начать с 96 и идти вверх, проверяя каждое число, велик, но ответить на вопрос «может ли данное R быть результатом» труднее, чем построить все R подряд.
Диапазон перебора берите с запасом. Нужное N маленькое, но заранее неизвестно какое; range(1, 10000) считается мгновенно, а лишние значения отсекает условие отбора. Экономить тут нечего.
R не растёт вместе с N. Длина записи R зависит от чётности N: у чётного дописываются четыре разряда, у нечётного три. Поэтому соседние N дают числа вразнобой: N = 8 даёт R = 227, а следующее же N = 9 даёт R = 100. Останавливаться на первом подходящем нельзя – надо пройти весь диапазон и уже среди отобранных взять минимум.

N	N в двоичной	Чётность	R в двоичной	R
1	`1`	нечётное	`1100`	12
2	`10`	чётное	`111011`	59
3	`11`	нечётное	`11100`	28
4	`100`	чётное	`1110011`	115
5	`101`	нечётное	`110100`	52
6	`110`	чётное	`1111011`	123
7	`111`	нечётное	`111100`	60
8	`1000`	чётное	`11100011`	227
9	`1001`	нечётное	`1100100`	100
10	`1010`	чётное	`11101011`	235
11	`1011`	нечётное	`1101100`	108
12	`1100`	чётное	`11110011`	243
13	`1101`	нечётное	`1110100`	116
14	`1110`	чётное	`11111011`	251
15	`1111`	нечётное	`1111100`	124

Подсвечена строка с ответом. Обратите внимание, что она идёт после строки с R = 227: перебор по возрастанию N прошёл бы мимо неё.

Порядок действий: написать функцию → проверить её на двух примерах из условия → перебрать диапазон → отобрать подходящие R и взять минимум.

Решение

def r(n):
    s = bin(n)[2:]              # двоичная запись без приставки '0b'
    if n % 2 == 0:
        s = '11' + s + '11'     # чётное: по две единицы с обеих сторон
    else:
        s = '1' + s + '00'      # нечётное: единица слева, два нуля справа
    return int(s, 2)

# Проверка функции на примерах из условия
print(r(13))                    # Должно быть 116
print(r(6))                     # должно быть 123

print(min(r(n) for n in range(1, 10000) if r(n) > 95)) # 100

Если условие другое

Каркас не меняется никогда: правило живёт внутри r, а правят всегда одно из трёх – само правило, условие отбора и то, что печатают, N или R.

Что в условии	Что править в коде
«минимальное N, при котором R не меньше 190»	`min(n for n in range(1, 10000) if r(n) >= 190)`
«максимальное N, при котором R меньше 100»	`max(...)` с тем же отбором
«минимальное нечётное R, большее 520»	добавить в отбор `and r(n) % 2 == 1`
«R, ближайшее к 130»	`min(..., key=lambda n: abs(r(n) - 130))`
«если сумма цифр в двоичной записи чётная»	`if s.count('1') % 2 == 0:` вместо проверки чётности N
«два левых разряда заменяются на 10»	`s = '10' + s[2:]`
«строится троичная запись»	свой перевод в систему по основанию 3, чтение – `int(s, 3)`

Троичные варианты – единственное место, где задание 5 требует больше трёх строк: bin для них не годится, перевод в систему по основанию пишется вручную – делением на 3 с записью остатков справа налево.

def to_base(n, b):
    s = ''
    while n:
        s = str(n % b) + s
        n //= b
    return s

Ответ этой задачи – всё равно int(s, 3) от собранной строки: меняется только сборка записи, чтение остаётся прежним.

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