ЕГЭ · ЗАДАНИЕ 4
Кодирование и условие Фано · №28752
Для девяти букв коды заданы. Укажите кратчайшее кодовое слово для буквы Л, удовлетворяющее условию Фано. Если вариантов несколько, выберите код с наименьшим числовым значением.
| Буква | Код | Буква | Код |
|---|---|---|---|
| А | 01 | Л | ? |
| Б | 1001 | Р | 1000 |
| Е | 001 | С | 1010 |
| И | 000 | Т | 1101 |
| К | 1011 | У | 111 |
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 1100
1. Проверим длины 1–3
Коды 0 и 1 являются началами известных кодов. На уровне 2 ветвь 01 уже занята, а 00, 10 и 11 имеют занятых потомков.
| Кандидаты длины 3 | Почему не подходят |
|---|---|
| 000, 001, 111 | Уже используются |
| 010, 011 | Начинаются с заданного кода 01 |
| 100 | Является началом 1000 и 1001 |
| 101 | Является началом 1010 и 1011 |
| 110 | Является началом 1101 |
2. Перейдём на следующий уровень
Ветвь 110 делится на 1100 и 1101. Второй код занят буквой Т, первый свободен. Остальные ветви длины 4 заняты либо начинаются с уже заданного кода.
3. Проверим обе стороны условия Фано
- Ни один известный код не является началом 1100.
- 1100 не является началом другого кодового слова.
Кратчайший допустимый код — 1100. Он единственный на этой длине, поэтому условие о наименьшем числовом значении тоже выполнено.
Частая ошибка: записать 110. Его нельзя брать, потому что он является началом 1101.
Самопроверка. Закройте разбор и повторите расчёт без подсказки.