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




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

По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.

Какова минимальная общая длина кодовых слов для всех пяти букв? Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение.

Следующая буква кодового слова должна кодироваться кодом длины 3, т. к. 0, 11 и 10 мы взять не можем. Подходящий трехзначный код — 000 или 001. Если мы возьмем оба, то тогда наша пятая буква не может начинаться на 1, 01, 0, 00, 000, 001. Такого кода не существует, значит, мы можем взять только 1 из них. Тогда четвертая и пятая буква будут кодироваться минимум четыремя битами. Можно заметить, что нам подойдет код 0001 и 0000. Тогда длина равна 4 + 4 + 3 + 2 + 1 = 14.

 

Ответ:14.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10504