Задание 4 ЕГЭ по информатике: Условие Фано
Часть букв уже закодирована двоичными словами, для остальных нужно подобрать коды так, чтобы ни один не был началом другого, а суммарная длина оказалась наименьшей. Проверяют понимание префиксного кода и умение работать с двоичным деревом кодов.
Страница обновлена 5 сентября 2026
Коротко о задании
| Уровень сложности | базовый |
|---|---|
| Максимальный балл | 1 балл |
| Форма ответа | целое число |
| Сколько минут закладывать | 2 минуты |
| Коды кодификатора |
|
Проект демоверсии
Структура по проекту демоверсии ФИПИ 2027; официальную версию ФИПИ публикует в ноябре. По проекту спецификации ФИПИ 2027 (обсуждение до 30 сентября 2026). Число заданий, баллы и продолжительность прежние, переписаны формулировки номеров 10, 13, 23 и форма записи ответа в 27.
Источник — ФИПИ, проект спецификации КИМ ЕГЭ 2027 по информатике (28 августа 2026).
Как решать
- Постройте двоичное дерево и отметьте на нём заданные коды.
- Вычеркните все ветви, идущие ниже занятых узлов.
- Возьмите свободные узлы наименьшей глубины по числу оставшихся букв.
- Сложите длины подобранных кодов и запишите сумму.
Типичные ошибки
- Дают коду длину, при которой он оказывается началом уже занятого кода.
- Отвечают максимальной длиной кода вместо суммарной.
- Забывают, что свободных узлов малой глубины может не хватить на все буквы.
Дерево на черновике надёжнее рассуждений в уме: занятые ветви видно сразу, а свободные узлы просто пересчитываются.