5 задание ЕГЭ информатика
Анализ алгоритма с двоичной записью
1 балл ≈ 4 мин уровень Б Исполнение простого алгоритма
Задание 5 – алгоритм строит по числу N новое число R: переводит N в двоичную (или другую) систему, дописывает или меняет разряды по правилам, переводит обратно. Нужно найти минимальное N или R при условии. 1 балл. Решается перебором на Python за минуту.
Полезные функции Python
- bin(n)[2:] – двоичная запись числа строкой (без префикса 0b).
- int(s, 2) – строка из 0 и 1 в десятичное число.
- s.count("1") – количество единиц, s[-3:] – три последние цифры, s[::-1] – разворот.
- Для системы с основанием b пиши функцию перевода с остатками от деления.
Алгоритм
- Перенеси правила построения R в код дословно, по шагам.
- Проверь код на примере из условия (там всегда есть пример: «для N = 12 получится R = 100»).
- Перебери N по возрастанию и выведи первое подходящее.
Разобранный пример. К двоичной записи N справа дописывается 0, если N чётное, и 1, если нечётное; затем к новой записи дописывается остаток от деления количества её единиц на 2. Найди наименьшее N, для которого R > 77.
for n in range(1, 1000):
s = bin(n)[2:]
s = s + ("0" if n % 2 == 0 else "1")
s = s + str(s.count("1") % 2)
r = int(s, 2)
if r > 77:
print(n, r)
breakОтвет: N = 19 (10011 → 100111 → 1001110 = 78).
Ловушки: перепутать «не меньше» (>=) и «больше» (>); спрашивают N, а ты выводишь R (или наоборот); не проверить код на примере из условия.
- Первым делом проверь программу на примере из условия – это ловит 90 % ошибок.
- Внимательно: «наименьшее N» или «наименьшее R» – печатай нужное.
- Диапазон перебора бери с запасом, например до 10 000.
Разобранные задания 5 из открытого банка ФИПИ
Пример 1 · код ФИПИ 89FBC4
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N нечётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если N чётное, справа дописывается сначала единица, а затем ноль.
Например, двоичная запись 1001 числа 9 будет преобразована в 100101,
а двоичная запись 1100 числа 12 будет преобразована в 110010.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R результата работы данного алгоритма.
Укажите максимальное число R, которое меньше 89 и может являться результатом работы данного алгоритма. В ответе это число запишите
в десятичной системе счисления.
Показать ответ и решение
Ответ: 85
Возможные R: нечётные N дают окончание 01, чётные – 10. Наибольшее R < 89: 85 = 1010101₂ (N = 21 – нечётное).
Пример 2 · код ФИПИ A7196F
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 134. В ответе это число запишите в десятичной системе счисления.
Показать ответ и решение
Ответ: 33
R = 4N (чётное N) или 4N + 3 (нечётное).
N = 33: R = 135 > 134; N = 32: R = 128. Ответ 33.
Пример 3 · код ФИПИ B933D5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 1110 = 1023 результатом является число 1021013 = 30710, а для исходного числа 610 = 203 это число 20203 = 6010.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее 242.
Показать ответ и решение
Ответ: 11
N = 11 = 102₃: остаток 2·5 = 10 = 101₃ → 102101₃ = 307 ≥ 242. Для N ≤ 10 перебор даёт R < 242.
Ответ: 11.
Частые вопросы о задании 5
Сколько баллов даёт задание 5 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 4 мин. Уровень сложности – Б.
Что проверяет задание 5?
Задание 5 – алгоритм строит по числу N новое число R: переводит N в двоичную (или другую) систему, дописывает или меняет разряды по правилам, переводит обратно. Нужно найти минимальное N или R при условии. 1 балл. Решается перебором на Python за минуту.
Как подготовиться к заданию 5?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.