Задание 4 ЕГЭ по информатике · D779F5
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| Д | 00 |
|---|---|
| Е | 011 |
| Ж | 111 |
| З | 010 |
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
14
Подсказки (3)
- Какие ветви двоичного дерева ещё можно использовать, чтобы ни одно новое кодовое слово не начиналось с уже заданного?
- Ветвь 10 свободна, поэтому можно взять коды 100 и 101. В ветви 11 код 111 уже занят, но можно использовать 1100 и 1101.
- Суммарная длина четырёх новых кодов равна 3+3+4+4.
Решение
1. Рассмотрим двоичное дерево кодов. Код 00 уже занят, поэтому все слова, начинающиеся с 00, использовать нельзя. Аналогично ветвь 01 занята словами 010 и 011. 2. В свободной ветви 10 можно разместить два кодовых слова одинаковой длины: 100 и 101. l(100)+l(101)=3+3 3. В ветви 11 слово 111 уже занято. В свободной части этой ветви можно разместить слова 1100 и 1101. l(1100)+l(1101)=4+4 4. Полученные слова не являются началами друг друга или известных кодовых слов, поэтому условие Фано выполнено. Минимальная сумма длин равна: 3+3+4+4=14
Частые ошибки
- Использовать код, начинающийся с 00, 010, 011 или 111.
- Забыть, что новое кодовое слово не должно быть началом другого слова.
- Сложить количество кодовых слов вместо их суммарной длины.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 5A9AE04Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 6B09EA4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 734D404По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 7410AC4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · F9598B4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы · 460D7D
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.