Алгоритм решения задания 4 ЕГЭ по информатике. Часть 2

Тип 2

В прошлой статье мы разобрали алгоритм решения 4 задания ЕГЭ по информатике первого типа. Научились строить двоичные деревья и корректно подбирать кодовое слово для заданной буквы. В этой статье уже перейдём ко второму типу 4 заданий и будем работать уже с закодированными словами.

От нас потребуется здесь не только найти кодовое слово для нескольких букв, но и подсчитать количество двоичных знаков, необходимое для кодирования слова из условия.

Но по большей части алгоритм решения будет все такой же: строим двоичное дерево, определяем, в какие листы можно поставить букву, а в какие нельзя. При этом стараемся найти самый короткий из допустимых кодов для этой буквы. А в конце просто складываем длины всех кодовых слов.

Главное в этих заданиях, как и во всём ЕГЭ, – внимательность! Всегда обращайте внимание на количество повторений букв в слове. Как мы уже рассматривали ранее, для наиболее часто встречающейся буквы следует выбирать самый короткий код.

Что же, давайте сразу перейдём к разбору первой формулировки:

Задание 400

«По каналу связи передаются сообщения, содержащие только буквы: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – 1001, К – 11.

Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова КОЛОКОЛ?»

Давайте сразу определим количество повторений каждой буквы в слове «колокол»:

1. К – 2 повторения
2. О – 3 повторения
3. Л – 2 повторения

Нам нужно стремиться к тому, чтобы у буквы «О» был самый короткий код из всех возможных. При этом букву «Н» можем поместить на абсолютно любой из допустимых листов дерева – длина её кодового слова нас не интересует вовсе.

Итак, давайте нарисуем двоичное дерево.

Сразу отметим на нём данные в условии коды для букв «К» и «Б» и отметим листы, в которые нельзя будет поместить буквы из-за условия Фано.

Мы видим, что левый, нулевой, лист свободен. Значит, сюда мы можем поместить наиболее встречающуюся букву «О». И у нас останутся свободными только 2 листа: с коротким кодом «101» и длинным «1000».

Логично предположить, что короткий код «101» следует присвоить букве «Л», чтобы тем самым сократить длину двоичных символов в слове «колокол». А оставшийся код «1000» отдадим букве «Н».

Теперь каждая буква имеет своё кодовое слово. Давайте вычислять количество двоичных знаков, которое требуется для кодирования слова «колокол»:

1. К – 2 повторения – код 2 символа (11) – итоговая длина 4
2. О – 3 повторения – код 1 символ (0) – итоговая длина 3
3. Л – 2 повторения – код 3 символа (101) – итоговая длина 6

Складываем все длины и получаем ответ на это задание – число 13.

Пример 1

Перейдём к следующей формулировке:

Задание 406

«По каналу связи передаются сообщения, содержащие только буквы из набора: Б, К, Р, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известные Б – 10, Н – 110, Р – 000. Для двух оставшихся букв К и О кодовые слова неизвестны.
Какое количество двоичных знаков требуется для кодирования слова КОРОБОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?»

Давайте подсчитаем количество повторений каждой буквы в слове «коробок»:

1. К – 2 повторения
2. О – 3 повторения
3. Р – 1 повторение
4. Б – 1 повторение

Наша задача подобрать максимально короткое кодовое слово для буквы «О» и для буквы «К» тоже короткое, но из оставшихся.

Построим симметричное двоичное дерево.

Теперь отметим на нём буквы «Б», «Н» и «Р», кодовые слова к которым даны в условии.

Мы видим, что на дереве остались только три доступных листа с кодами «01», «001» и «111».

Тогда самый короткий код «01» отдадим под наиболее часто встречающуюся букву «О». Для буквы «К» можем выбрать любой из оставшихся кодов – «111» или «001», они все равно имеют одинаковую длину. Для примера выберем код «111».

Готово, каждая буква имеет своё кодовое слово. Теперь можем вычислить количество двоичных знаков, которое требуется для кодирования слова «коробок»:

1. К – 2 повторения – код 3 символа (111) – итоговая длина 6
2. О – 3 повторения – код 2 символа (01) – итоговая длина 6
3. Р – 1 повторение – код 3 символа (000) – итоговая длина 3
4. Б – 1 повторение – код 2 символа (10) – итоговая длина 2

Сложим все длины кодовых слов: 6 + 6 + 3 + 2 = 17. Таким образом, для кодирования слова «коробок» нам потребуется 17 двоичных знаков. Это число и запишем в ответ.

Пример 2

И последняя формулировка 4 задания звучит так:

Задание 408

«По каналу связи передаются сообщения, содержащие только буквы из набора: В, Е, М, Н, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано.

Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: В – 1, М – 001. Для трёх оставшихся букв Е, Н и Р кодовые слова неизвестны.

Какое количество двоичных знаков потребуется для кодирования слова ВЕРМЕЕР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?»

Имеем слово «вермеер», давайте определим частоту вхождения каждой буквы:

1. В – 1 повторение
2. Е – 3 повторения
3. Р – 2 повторения
4. М – 1 повторение

Для буквы «Е» нужно найти самое короткое кодовое слово, для «Р» – наименьшее по длине из оставшихся, для буквы «Н» – абсолютно любое из доступных.

Сразу отметим, что правую ветку дерева строить не имеет смысла. По условию видно, что единственный лист на этом дереве отведён под букву «В». Построим дерево только с «нулевой веткой».

Отметим на дереве известную нам букву «М».

Итак, у нас осталось доступно 6 листов. Правда, одновременно мы можем занять либо лист «01» и листы «0000» и «0001», либо листы «010», «011» и «000».

Тут необходимо рассмотреть разные варианты. Что мы знаем? Для буквы «Е» нужен самый короткий код так, как она встречается чаще всего – 3 раза.

Можем рассмотреть такие варианты:

1. Буква «Е» имеет кодовое слово «01» из двух символов, тогда букве «Р» достанется кодовое слово из четырёх символов.
2. Обе буквы имеют кодовые слова по 3 символа.

Давайте считать. В первом случае суммарная длина кодовых слов для трёх букв «Е» и двух «Р» будет составлять: 2 + 2 + 2 + 4 + 4 = 14 символов.

Во втором случае: 3 + 3 + 3 + 3 + 3 = 15 символов. Таким образом, целесообразно будет разместить букву «Е» на листе с кодовым словом в 2 символа. А оставшиеся два отведём под буквы «Р» и «Н».

Теперь вычислим количество двоичных знаков, необходимое для кодирования слова «вермеер»:

1. В – 1 повторения – код 1 символ (1) – итоговая длина 1
2. Е – 3 повторения – код 2 символа (01) – итоговая длина 6
3. Р – 2 повторения – код 4 символа (0001) – итоговая длина 8
4. М – 1 повторения – код 3 символа (001) – итоговая длина 3

Складываем все полученные значения и пишем в ответ число 18.

На этом мы закончили разбор алгоритма решения обоих типов 4 задания ЕГЭ по информатике. А больше задач вы всегда можете найти на нашем сайте.

<<< Предыдущая статья Первая статья >>>