Какова наименьшая возможная сумма длин всех шести кодовых слов?
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано . Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ 2017 г. – задание №5
Ответ:
Решение:
Для нахождения кодовых слов будем использовать данную таблицу.
Если коды остальных букв будет начинаться на 0, код буквы А=0 будет являться началом их кодов , поэтому этот вариант не подходит. Если код Б=10, коды букв В, Г, Д, Е начинаются на11. Чтобы получить 4 разных кода, нужно использовать коды, состоящие из 4-х символов (1111, 1110, 1101, 1100) .
| 0
0-А |
1 | ||||
| 1 |
0 10-Б |
||||
| 1 | 0 | ||||
| 1
1111-В |
0
1110-Г |
1
1101-Д |
0
1100-Е |
||
А — 0 (1 символ)
Б — 10 (2 символа)
В — 1100 (4 символа)
Г — 1101 (4 символа)
Д — 1110 (4 символа)
Е — 1111 (4 символа)
1+2+4+4+4+4 = 19
Ответ: 19