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

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали кодовые слова 100, 101, 00, 01 соответственно. Для двух оставшихся букв — Д и Е — коды неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

1. Кодовые слова 00 и 01 занимают всю ветвь, начинающуюся с 0, а слова 100 и 101 — две ветви после 10.

2. Код 11 длины 2 использовать для буквы Д нельзя: после него не останется отдельной ветви для кодового слова буквы Е, не нарушающего условие Фано.

3. Минимальная подходящая длина — 3. Свободные кодовые слова 110 и 111 не являются началами друг друга, поэтому их можно назначить буквам Д и Е.

4. Из двух возможных кодов для буквы Д выбираем код с наибольшим числовым значением.
111>110