Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 5
Условие
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 0, Б — 1011. Укажите сумму длин кратчайших кодовых слов для букв В и Г, которые будут удовлетворять условию Фано.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Подсказки — как подойти к решению
- Готовые слова закрывают часть дерева: посмотри, какие ветви свободны, и распредели по ним две оставшиеся буквы так, чтобы каждое слово вышло как можно короче.
- Подбирай слова по отдельности, но проверяй совместно: два коротких кандидата могут оказаться в отношении «начало — продолжение», и тогда один из них придётся удлинить.
Решение
Для двух букв кодовые слова уже известны, осталось подобрать для оставшихся двух букв такие кодовые слова, которые будут являться кратчайшими и удовлетворять условию Фано.
Кодовые слова не могут начинаться с 0, поскольку 0 является кодовым словом для буквы А. Кодовым словом для буквы В будет являться 11. Кодовым словом для буквы Г будет являться 100, кодовое слово 101 взять не можем, поскольку кодовым словом для буквы Б является 1011.
Таким образом, сумма длин кратчайших кодовых слов для букв В и Г будет равна 2 + 3 = 5.
Ответ: 5.
Типичные ошибки
- Сумма занижена: один из выбранных коротких кодов служит началом готового слова из условия, поэтому его нельзя использовать — для этой буквы нужен более длинный код.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике