Задание 4 ЕГЭ по информатике · F9598B
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| А | 011 |
|---|---|
| Б | 0100 |
| В | 10 |
| Г | 0101 |
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
12
Подсказки (3)
- Рассмотрите двоичное дерево кодов и найдите свободные ветви, не нарушающие условие Фано.
- Кодовое слово 10 занимает ветвь, начинающуюся с 10; слова 0100, 0101 и 011 занимают ветви, начинающиеся с 01. Свободными остаются, например, слова 000, 001, 110 и 111.
- Четыре оставшиеся буквы можно закодировать четырьмя словами длины 3: 000, 001, 110 и 111. Суммарная длина равна 3+3+3+3=12.
Решение
1. Изобразим известные кодовые слова как ветви двоичного дерева. Слово 10 занимает ветвь 10, а слова 0100, 0101 и 011 занимают ветви под началом 01. 2. Для четырёх оставшихся букв можно выбрать свободные кодовые слова 000, 001, 110 и 111. Ни одно из них не является началом другого и не начинается с уже занятого кодового слова. 3. Все четыре выбранных слова имеют длину 3, поэтому минимальная суммарная длина равна: 3+3+3+3=12
Частые ошибки
- Считать только свободные ветви под началом 00 и не учитывать ветвь 11.
- Использовать кодовое слово, являющееся началом другого кодового слова.
- Сложить длины всех кодовых слов, включая уже заданные.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 6B09EA4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 734D404По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 7410AC4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · D779F54Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы · 460D7D4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.