Демовариант ЕГЭ по информатике 2020 года, задание 5

Задача 5

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решать данное задание мы будем при помощи дерева кодирования: которое позволяет соблюсти условие Фано. Влево будем откладывать нули, вправо — единицы. Сначала отобразим на дереве известные кодовые слова:

ege 2020 4

Напомним, чтобы соблюсти условие Фано, нельзя начинать ветвь из листа (из буквы).

Проанализировав дерево, замечаем, что имеются два узла, из которых можно начать по одной ветке:

ege 2020 4 1

Таким образом, для недостающих букв у нас получилось два кодовых слова: 011 и 10 (стоит заметить, что буквам может соответствовать любое из этих кодовых слов).

 ege 2020 4 2

В ответе необходимо указать код с наименьшим числовым значеним - 10.

Ответ: 10.

Демонстрационный вариант 2020 года

Выберите соответствующий номер задания в демонстрационном варианте ЕГЭ 2020 года

Информация

Все изображения, размещенные на сайте, изготовлены автором самостоятельно, а также взяты в сети Интернет из тех изображений, которые находятся в свободном доступе. Поиск изображений осуществлялся посредством "Яндекс. Картинки".

Версия сайта для слабовидящих

Индекс цитирования

Проект при поддержке компании RU-CENTER Рейтинг@Mail.ru