Задание 4 ЕГЭ по информатике · 882400
Кратчайшее кодовое слово для буквыПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы У, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| А | 00 | Л | 1001 |
| Б | 1000 | Р | 1110 |
| Е | 010 | С | 1010 |
| И | 011 | Т | 1111 |
| К | 1011 | У |
Укажите кратчайшее кодовое слово для буквы У, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
110
Подсказки (3)
- Проверьте, не является ли предполагаемое кодовое слово началом или продолжением одного из уже имеющихся кодовых слов.
- Рассматривайте кодовые слова как вершины бинарного дерева: новое слово нельзя размещать на пути к уже существующему слову.
- Все слова длины 1 и 2 конфликтуют с уже имеющимися кодами. Среди слов длины 3 подходит 110; оно не является началом ни одного известного слова.
Решение
1. Проверим кодовые слова длины 1. Код 0 является началом кодов 00, 010 и 011, а код 1 является началом кодов 1000, 1001, 1010, 1011, 1110 и 1111. Поэтому слова длины 1 невозможны. 2. Кодовые слова длины 2 также невозможны: 00 уже занято, 01 является началом кодов 010 и 011, 10 является началом кодов 1000, 1001, 1010 и 1011, а 11 является началом кодов 1110 и 1111. 3. Проверим слова длины 3. Ветви 000 и 001 конфликтуют с кодом 00, 010 и 011 уже заняты, 100 и 101 являются началами существующих кодов, а 111 является началом кодов 1110 и 1111. Код 110 не конфликтует ни с одним существующим кодовым словом. 4. Следовательно, кратчайшее подходящее кодовое слово для буквы У — 110.
Частые ошибки
- Выбор кода, который является началом уже существующего кодового слова.
- Проверка только совпадения кодов без проверки условия, что одно слово не является началом другого.
- Выбор более длинного кода, хотя подходящее слово длины 3 уже существует.
Похожие задания
4По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У…Кратчайшее кодовое слово для буквы · 3645394По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y…Кратчайшее кодовое слово для буквы · 566A474По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т…Кратчайшее кодовое слово для буквы · 52C6F34По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т…Кратчайшее кодовое слово для буквы · B8EB094По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y…Кратчайшее кодовое слово для буквы · D496714По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т…Кратчайшее кодовое слово для буквы · 01AEBA4По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т…Кратчайшее кодовое слово для буквы · 38AA154По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т…Кратчайшее кодовое слово для буквы · FEFB2F
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.