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