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


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

По каналу связи передаются сообщения, содержащие только пять букв: Ш, К, О, Л, А. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы О используется кодовое слово 0; для буквы А используется кодовое слово 10.

Какова минимальная общая длина кодовых слов для всех пяти букв?

Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение.

Следующая буква кодового слова должна кодироваться как 110, т.к. 11 мы взять можем, но тогда для всех кодов больше 2 не будет выполнено условие Фано (т.к. они начинаются на 10 или 11 и уже будут заняты). 100 мы взять не можем, как и 101. Следующая за ней буква имеет код 1110 для выполнения условия, а последующая — 1111. Тогда длина равна 4 + 4 + 3 + 2 + 1 = 14.

 

Ответ:14.

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