Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 20
Условие
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Подсказки — как подойти к решению
- Построй дерево по заданным словам и определи, какие участки полностью закрыты: одно слово закрывает целую ветвь, а слова из второй ветви отрезают её части.
- Обрати внимание на ловушку: заняв слово, ты закрываешь все его продолжения, поэтому нельзя занять и слово, и его «потомка» одновременно. Ищи свободные листья, продвигаясь от корня вниз по незанятым ветвям.
- Сложи длины трёх данных слов с длинами трёх подобранных: чтобы сумма была минимальной, занимай самые короткие свободные листья. В конце проверь каждую пару слов на условие Фано.
Решение
Заметим, что для алфавита из трёх букв, код с наименьшей суммарной длиной кодовых слов, удовлетворяющий условию Фано имел бы длину 1 + 2 + 2 = 5. Для алфавита из четырёх букв: 1 + 2 + 3 + 3 = 9. Аналогично можно получить минимальную длину суммарную длину кодовых слов для алфавита, содержащего произвольное число символов.
Удостоверимся, что, используя кодовые слова, приведённые в условии, можно построить код, удовлетворяющий условию Фано и имеющий наименьшую суммарную длину. Будем использовать для буквы D кодовое слово 1000, для буквы E — кодовое слово 10010, для буквы F — 10011.
Суммарная длина такого кода 1 + 2 + 3 + 4 + 5 + 5 = 20.
Ответ: 20.
Типичные ошибки
- Взяты слова, одно из которых является началом другого, — такой код не допускает однозначного декодирования. Проверяй, что ни одно выбранное слово не лежит на пути к другому.
- Из одной ветви взято и короткое, и длинное слово, поэтому часть набора не может использоваться одновременно с другой. Перед тем как брать слово, проверь все его начала, а не только конец.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике