Задание 4 ЕГЭ по информатике · 5A9AE0
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| А | 000 |
|---|---|
| Б | 001 |
| В | 01 |
| Г | 11 |
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
16
Подсказки (3)
- Какие ветви двоичного дерева ещё свободны после размещения известных кодовых слов?
- Кодовые слова 01 и 11 занимают целые ветви, а слова 000 и 001 занимают ветви под 00. Четыре оставшиеся буквы нужно разместить в ветви 10.
- Разделите ветвь 10 сначала на 100 и 101, а затем каждую из них ещё на две ветви. Получатся четыре слова длины 4, поэтому сумма равна 4⋅4.
Решение
1. Известные кодовые слова занимают ветви 01 и 11, а также две ветви 000 и 001 внутри ветви 00. 2. Единственная свободная крупная ветвь — 10. Чтобы разместить в ней четыре кодовых слова и сохранить условие Фано, её нужно разделить до четырёх листьев: 1000, 1001, 1010 и 1011. 3. Каждое из четырёх оставшихся кодовых слов имеет длину 4, поэтому суммарная длина равна: 4+4+4+4=16
Частые ошибки
- Используют ветви 00, 01 или 11, уже занятые известными кодовыми словами или их продолжениями.
- Считают количество кодовых слов вместо суммы их длин.
- Размещают новое кодовое слово так, что оно становится началом другого слова, нарушая условие Фано.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 32DCC74По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 3B93844Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 4E2FD74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 50D35E4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 6B09EA4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 734D404По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 7410AC4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · D779F5
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.