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