В этой статье мы решим задачу № 4 из демонстрационного варианта ЕГЭ-2021 года по информатике и рассмотрим, какие задачи этого типа встречались раньше. Задача № 4 встречается почти в неизменном виде, начиная с ЕГЭ-2016. До 2016 года задача была в тестовом виде, где нужно было выбрать один из четырёх вариантов. Рекомендуемое время на решение этой задачи составляет 2 минуты, задача оценивается в 1 балл. Для решения требуется внимательность и аккуратность. В конце статьи будет ссылка на тест на портале Эрудит.Онлайн. В этом тесте вы сможете потренироваться в решении задач такого типа. Обращайте внимание не только на правильность решения, но и на затраченное время.
Демонстрационный вариант ЕГЭ-2021 по информатике
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв — П и Р — кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Для построения кода с таким условием удобно использовать особое дерево. Оно начинается двумя ветвями, одна из которых соответствует 0 (нулю), а вторая – 1 (единице). От каждой ветви можно строить дополнительные ветви, также соответствующие либо 0, либо 1. Чтобы не запутаться, ветви одного значения лучше рисовать только в одном направлении. Например, ветви, соответствующие 1, будем всегда строить вправо. Если какому-то коду мы хотим сопоставить букву, то её следует изобразить у конца этой ветви и больше не продолжать её.
Изобразим подобное дерево для нашей задачи.
Нам нужно закодировать ещё 2 буквы и, поскольку уже 3 ветви больше нельзя продлевать, продлим ветвь, начинающуюся с 1 в сторону 0. Получим
Мы не можем остановить построение дерева кодирования здесь, поскольку нам нужно обязательно закодировать 2 буквы, поэтому продолжим эту ветку дальше. Получим
Теперь в нашем дереве есть 2 свободные ветви как раз для двух букв. Коды у этих букв будут 100 и 101. В условии сказано, что в ответе нужно указать код с наименьшим числовым значением, а, значит, 100.
Получим ответ: 100
Рассмотрим, какие задачи аналогичного типа встречались в демонстрационных вариантах ЕГЭ прошлых лет, начиная с 2016 года. Ранее 2016 года аналогичная задача встречалась в тестовой форме с выбором одного из четырёх вариантов. В условиях демонстрационных вариантов с 2016 по 2021 год изменяются только известные коды и вопрос: в одних заданиях просят указать кратчайший код, либо код с наименьшим числовым значением, а в других – сумму длин кратчайших кодов.
Демонстрационный вариант ЕГЭ-2020 по информатике
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв — П и Р — длины кодовых слов неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ-2019 по информатике
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ-2018 по информатике
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова. Для буквы А − 00, Е — 010, И — 011, К — 1111, Л — 1101, Р — 1010, С — 1110, Т — 1011, У — 100.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ-2017 по информатике
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ-2016 по информатике
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Потренироваться в решении задач такого типа можно в тесте на портале Эрудит.Онлайн «ЕГЭ-2021 Задача № 4».
Также можете посмотреть разбор других задач:
- Задача № 1 из ЕГЭ-2021 по информатике
