Задание 4 ЕГЭ по информатике · 40E3DC

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв — П и Р — длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

1. Кодовое слово длины 1 не подходит: 0 является началом слов 000, 001 и 010, а 1 является началом слова 11.

2. Проверим слова длины 2. Слова 00 и 01 являются началами уже заданных кодовых слов, а слово 11 совпадает с уже использованным кодовым словом.

3. Слово 10 не является началом ни одного заданного кодового слова и не содержит их как начало. Для второй неизвестной буквы можно выбрать, например, слово 101, не нарушив условие Фано.

4. Следовательно, кратчайшее возможное кодовое слово для буквы П имеет длину 2 и равно 10.