Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 100
Условие
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 11 |
| Б | 0010 |
| Г | 1011 |
| Е | 0011 |
| Буква | Кодовое слово |
И |
| М | 01 |
|---|---|
| Р | 000 |
| Т | 1010 |
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Подсказки — как подойти к решению
- Сгруппируй готовые слова по началам: так сразу видно, какие ветви дерева закрыты полностью, а в каких ещё остались свободные листья.
- Перебирай свободные слова от коротких к длинным, проверяя обе стороны условия Фано: ни готовое слово не должно быть началом кандидата, ни кандидат началом готового.
Решение
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
0 — нельзя, Б, Е, М и Р начинаются с 0.
1 — нельзя, буквы А, Г и Т начинаются с 1.
00 — нельзя, Б начинается с 00.
01 — нельзя из-за М.
10 — нельзя из-за Г.
11 — нельзя из-за А.
000 — нельзя из-за Р.
001 — нельзя из-за Е.
010 — нельзя из-за М.
011 — нельзя из-за М.
100 — можно использовать.
101 — нельзя из-за Т.
110 — нельзя из-за А.
111 — нельзя из-за А.
Таким образом, наименьшее числовое значение у кодового слова 100 для буквы И.
Ответ: 100.
Типичные ошибки
- Это слово начинается с готового слова из условия, значит условие Фано нарушено: проверяй, не является ли начало кандидата чьим-то уже выданным кодом.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике