Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 19
Условие
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б — кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подсказки — как подойти к решению
- Начни с дерева: одно из заданных слов закрывает всю ветвь с нулём, другое — одну из ветвей второго уровня. Посчитай, сколько свободных листьев остаётся для остальных букв.
- Здесь есть ловушка: слово из двух единиц формально свободно, но если занять его под букву, все его продолжения использовать уже нельзя, и места для остальных букв может не хватить. Сравни два плана — занять эту ветвь или оставить её для длинных слов.
- Выбрав план, распредели оставшиеся буквы по самым коротким свободным листьям и сложи длины всех слов. Убедись, что ни одно слово не является началом другого.
Решение
Для нахождения кодовых слов будем использовать двоичное дерево, в котором от каждого узла отходит две ветви, соответствующие выбору следующей цифры кода. Буквы будем размещать на конечных узлах дерева — листьях. Условие Фано выполняется, поскольку при проходе от корня дерева к букве в середине пути не встречается других букв.
Пример дерева, обеспечивающего минимальную сумму длин всех шести кодов, изображен на рисунке.
Суммарная длина такого кода 1 + 2 + 4 + 4 + 4 + 4 = 19.
Ответ: 19.
Типичные ошибки
- Занято короткое слово из двух единиц, и при этом его продолжения тоже посчитаны свободными — условие Фано нарушено. Заняв слово, вычёркивай всю его ветвь.
- Подобраны более длинные слова, чем нужно: среди свободных листьев есть более короткие. Сравни свой набор с альтернативой, где короткая ветвь оставлена для нескольких длинных слов.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике