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