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