Каталог: Задание №4. Условие Фано: код без путаницы

Банк задач: 237 Формат ЕГЭ 2026 Базовый (1 балл) 3-5 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №4

Тема кодификатора Однозначно декодируемые коды, прямое и обратное условие Фано

Сложность и баллы Базовый (1 балл)

Рекомендуемое время 3-5 мин

Инструменты решения Двоичное дерево, Прямое условие Фано, Обратное условие Фано, Python

Буквам назначены двоичные коды, часть кодов известна. Надо подобрать коды остальным буквам так, чтобы сообщение декодировалось однозначно, а длина получилась наименьшей. Решается деревом на бумаге или коротким перебором на Python.

Основные прототипы и разновидности

Тип 1: Код для одной буквы

Найти кодовое слово наименьшей длины, а при равных длинах с наименьшим числовым значением.

Тип 2: Длина слова при оптимальном кодировании

Часть букв без кода. Подбираем коды так, чтобы заданное слово получилось как можно короче.

Тип 3: Количество подходящих слов

Считаем, сколько существует кодовых слов нужной длины, которые не нарушают условия.

Теоретический фундамент и алгоритмы

Что от тебя хотят

Есть алфавит из нескольких букв. Для некоторых букв коды уже известны. Остальным нужно выдать коды так, чтобы закодированное сообщение, склеенное в одну строку из нулей и единиц, всегда читалось одним способом. Классический вопрос: «какова наименьшая возможная длина закодированного слова».

Когда код читается однозначно

Достаточно выполнить одно из двух условий:

Прямое условие Фано: ни одно кодовое слово не является началом другого. Читаем слева направо и всегда знаем, где кончилась буква.
Обратное условие Фано: ни одно кодовое слово не является концом другого. Тогда читаем справа налево.

В условии про «однозначное декодирование» годится любое из двух. Нельзя смешивать: весь набор целиком должен подчиняться одному условию.

Старые разборы учили только прямое условие. Этого мало: в реальных вариантах обратное условие даёт ответ короче, и без него получится на единицу больше.

Дерево кодов

Рисуем двоичное дерево: из каждого узла идут две ветки, 0 влево и 1 вправо. Каждой букве соответствует свой узел. Для прямого условия буква ставится в конец ветки, и всё, что растёт ниже неё, закрыто. Так видно, какие свободные узлы остались, и какой самый короткий из них.

Разбор 1: прямое условие

Буквам А, Б, В, Г назначены коды А: 00, Б: 010, В: 011, Г: 10. Для букв Д и Е нужно выбрать коды по условию Фано так, чтобы код Д был как можно короче, а среди равных по длине имел наименьшее значение. Какой код у Д?

Занято: 00, 010, 011 и 10. Ветка 0 закрыта полностью: 00 внизу слева, а 010 и 011 заняты внизу справа.
Свободная ветка одна: 11. Если отдать её букве Д целиком, для Е ничего не останется.
Значит узел 11 надо разделить: 110 и 111.
Наименьший по значению из них 110.

Ответ: 110.

Разбор 2: можно и обратное условие

Для букв П, Р, О, Б использовали коды 00, 1001, 0101, 111. Алфавит ещё содержит К, Н и И. Код должен допускать однозначное декодирование. Найдите наименьшую возможную длину закодированного слова КОРОН.

Слово КОРОН состоит из К, О, Р, О, Н. Известные части: О = 0101 (дважды) и Р = 1001, это 4 + 4 + 4 = 12 бит. Остаётся длина кодов К и Н.
Свободных кодов длины 2 в прямом режиме нет: ветки 01 и 10 уже заняты (0101 и 1001 растут внутри них). Длины 3 свободны три: 011, 101 и 110. К и Н получат по 3 бита, и всё слово займёт 12 + 6 = 18.
А теперь обратное условие. В нём ни один код не заканчивается другим. Код 10 не заканчивает ни один из известных, и сам не заканчивается на них. Подходит К = 10 (2 бита). Для Н найдём 3 бита: 011. Для И подойдёт 0001, это не мешает, так как И в слове нет.
Итого 12 + 2 + 3 = 17.

Ответ: 17. Проверено перебором: прямое условие даёт 18, обратное даёт 17.

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

Лайфхаки и фишки для ускорения

Совет

При равной длине берут код с наименьшим числовым значением: нули раньше. 100 меньше 101 и 110.

Совет

Проверка на бумаге: сумма 2 в степени минус длина каждого кода не больше единицы (неравенство Крафта). Если больше, кодов не хватит.

Совет

Длину слова считай по буквам с учётом повторов: О в КОРОН входит дважды, и её код тоже дважды.

Частые ошибки и экзаменационные ловушки

❌ Растить ветку из занятого узла
Если у А код 01, нельзя дать Б код 010: 01 стало бы началом 010.

✅ Занятый узел закрывает всё, что ниже него.

❌ Забыть про оставшиеся буквы
Отдать последний свободный узел одной букве, а ещё двум не оставить ничего.

✅ Свободных узлов должно хватить на все буквы без кода, даже на те, которых нет в слове.

❌ Проверять только прямое условие
Задача говорит «однозначно декодируется», а ты отбросил более короткий код с обратным условием.

✅ Проверить оба условия и взять лучшее. Смешивать их внутри одного набора нельзя.

💀 ГРОБ №4: Слово с повторяющимися буквами

В слове «АНАНАС» буква А повторяется три раза, а Н два. Если отдать им одинаковые по длине коды, слово окажется длиннее нужного.

Алгоритм решения: Считай, сколько раз каждая буква входит в слово. Чем чаще буква, тем короче должен быть её код: самым частым отдавай самые короткие свободные узлы.

Практические задачи из банка КИМ (Всего: 237)

Решать в песочнице СмартКИМ

Задача #9072 №4 ЕГЭ

Каталог: Задание №4. Условие Фано: код без путаницы

Спецификация и суть задания №4

Основные прототипы и разновидности

Теоретический фундамент и алгоритмы

Что от тебя хотят

Когда код читается однозначно

Дерево кодов

Разбор 1: прямое условие

Разбор 2: можно и обратное условие

Лайфхаки и фишки для ускорения

Частые ошибки и экзаменационные ловушки

Практические задачи из банка КИМ (Всего: 237)

Готовьтесь к ЕГЭ эффективно со СмартКИМ