Задание 4 ЕГЭ по информатике · 15013A
Сумма длин всех кодовых словПовышеннаяКЭС 2.1КЭС 2.2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0.
Какова наименьшая возможная сумма длин всех пяти кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Какова наименьшая возможная сумма длин всех пяти кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
13
Подсказки (3)
- Так как кодовое слово А равно 0, остальные кодовые слова не могут начинаться с 0.
- Размещайте остальные кодовые слова в ветви, начинающейся с 1, каждый раз соблюдая условие Фано.
- Минимальная сумма длин кодовых слов для оставшихся букв равна 2+3+4+4=13.
Решение
1. Кодовое слово буквы А равно 0, поэтому ни одно из кодовых слов для букв Б, В, Г и Д не может начинаться с 0: иначе слово 0 было бы началом другого слова. A=0 2. Чтобы соблюсти условие Фано и получить минимальные длины, оставшиеся слова размещают в ветви, начинающейся с 1. Их минимально возможные длины дают сумму 2+3+4+4. 2+3+4+4=13 3. Следовательно, минимальная возможная сумма длин кодовых слов равна 13.
Частые ошибки
- Размещают другое кодовое слово в ветви 0, из-за чего код 0 становится началом этого слова.
- Не проверяют условие Фано для всех пар кодовых слов.
- Считают количество кодовых слов вместо суммы их длин.
Похожие задания
4Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать…Сумма длин всех кодовых слов · 44DD034Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать…Сумма длин всех кодовых слов · EE6A5E4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы · 460D7D4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Кратчайшее кодовое слово для буквы · 3263954Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать…Кратчайшее кодовое слово для буквы · 40E3DC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.