Задание 4 ЕГЭ по информатике · 3B9384
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| А | 10 |
|---|---|
| Б | 011 |
| В | 110 |
| Г | 1110 |
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
13
Подсказки (3)
- Представьте кодовые слова как листья двоичного дерева и найдите свободные вершины, которые не являются продолжением уже занятого кодового слова.
- Коды 10, 011, 110 и 1110 уже занимают соответствующие ветви дерева. Для минимальной суммарной длины выбирайте самые короткие допустимые кодовые слова.
- Можно взять кодовые слова 000, 001, 010 и 1111. Их суммарная длина равна 3+3+3+4.
Решение
1. Размещаем известные кодовые слова в двоичном дереве: 10, 011, 110 и 1110. Ни одно новое слово не может иметь уже использованное слово своим началом и само не может быть началом другого слова. 2. Наиболее короткий набор из четырёх свободных листьев можно выбрать как 000, 001, 010 и 1111. Все эти слова удовлетворяют условию Фано. 3. Складываем длины выбранных кодовых слов. 3+3+3+4=13
Частые ошибки
- Использование кодового слова, начинающегося с уже существующего слова 10, 011, 110 или 1110.
- Выбор кодовых слов, одно из которых является началом другого.
- Суммирование самих кодовых слов вместо их длин.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется…Наименьшая суммарная длина кодов4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 20A17C4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 32DCC74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 4E2FD74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 50D35E4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 5A9AE04Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 6B09EA
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.