Задание 4 ЕГЭ по информатике · 9A6792
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 1000 |
| В | 101 |
| Г | 1001 |
| Д | 01 |
| Е | 110 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
8
Подсказки (3)
- Рассмотрите двоичное дерево кодов и найдите свободные ветви, не являющиеся продолжением уже заданных кодовых слов.
- Кодовые слова 00 и 01 занимают ветви после 0, а слова 1000, 1001 и 101 — ветви после 10 и 100. Слово 110 уже занимает одну из ветвей после 11.
- Для двух оставшихся букв свободными кодовыми словами минимальной длины будут 1110 и 1111. Их суммарная длина равна 4+4=8.
Решение
1. Построим двоичное дерево кодовых слов. Слова 00 и 01 полностью занимают ветви, начинающиеся с 0. 2. В ветви, начинающейся с 1, кодовые слова 1000, 1001 и 101 занимают соответствующие свободные участки. Кодовое слово 110 занимает одну из ветвей после 11. 3. Оставшиеся две буквы нельзя закодировать словом 111, поскольку тогда для второй буквы пришлось бы использовать продолжение 111, а кодовое слово стало бы началом другого. Поэтому минимальные подходящие слова — 1110 и 1111. 4. Суммарная длина двух кодовых слов равна: 4+4=8
Частые ошибки
- Использовать кодовое слово 111 для одной буквы и продолжение 1110 или 1111 для другой, нарушив условие Фано.
- Считать свободными ветви, которые уже являются продолжениями заданных кодовых слов.
Похожие задания
4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи…Наименьшая суммарная длина кодов · 76E4A0
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.