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