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


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

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

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

Решение.

Следующая буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.

 

Ответ: 14.

Спрятать решение · · Видеокурс ·
Кирилл Кислицын 03.05.2019 12:36

Если использовать для А - 010, Б - 011, Г -100, И - 00, М - 11, Я - 101, то условие Фано выполняется, а слово МАГИЯ будет выглядеть как 11 010 100 00 101 и тогда количество двоичных знаков будет равно 13, а не 14, как написано в решении.

Сергей Никифоров

При такой кодировке невозможно подобрать кодовое слово для буквы «Р», удовлетворяющее условию Фано.