СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 5 № 9293

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение.

Условие Фано — никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.