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