В прошлой статье мы разобрали алгоритм решения задания 4 ЕГЭ по информатике первого типа. Научились строить двоичные деревья и корректно подбирать кодовое слово для заданной буквы. В этой статье перейдём ко второму типу заданий и будем работать с закодированными словами.
Здесь потребуется не только найти кодовые слова для нескольких букв, но и подсчитать количество двоичных знаков, необходимое для кодирования слова из условия.
Но в основном алгоритм останется тем же: строим двоичное дерево, определяем, в какие узлы можно поставить букву, а в какие нельзя. Затем распределяем допустимые коды с учётом частоты букв и складываем длины всех кодовых слов.
Главное в этих заданиях, как и во всём ЕГЭ, – внимательность! Всегда учитывайте количество повторений букв в слове. Самый короткий из доступных кодов выгодно отдавать букве, которая встречается чаще.
Что же, давайте сразу перейдём к разбору первой формулировки:
По каналу связи передаются сообщения, содержащие только буквы: Б, К, Л, О, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны: Б – 1001, К – 11.
Для трёх оставшихся букв Л, Н и О кодовые слова неизвестны. Какое наименьшее количество двоичных знаков требуется для кодирования слова КОЛОКОЛ?
Давайте сразу определим количество повторений каждой буквы в слове «колокол»:
Нам нужно стремиться к тому, чтобы у буквы «О» был самый короткий код из возможных. Буква «Н» в слове «КОЛОКОЛ» не встречается, поэтому длина её кода не влияет на ответ. Но сам код для неё всё равно должен существовать и удовлетворять условию Фано.
Итак, давайте нарисуем двоичное дерево.
Сразу отметим на нём данные в условии коды для букв «К» и «Б» и отметим листы, в которые нельзя будет поместить буквы из-за условия Фано.
Мы видим, что левый, «нулевой», лист свободен. Значит, сюда можно поместить самую частую букву «О». После этого останутся два подходящих листа: с коротким кодом «101» и более длинным «1000».
Короткий код «101» логично присвоить букве «Л», чтобы сократить общую длину слова «КОЛОКОЛ». Оставшийся код «1000» отдадим букве «Н».
Теперь каждая буква имеет своё кодовое слово. Давайте вычислим количество двоичных знаков, которое требуется для кодирования слова «КОЛОКОЛ»:
Складываем все длины и получаем ответ на это задание – число 13.
Перейдём к следующей формулировке:
Давайте подсчитаем количество повторений каждой буквы в слове «коробок»:
Наша задача – подобрать максимально короткий код для буквы «О» и следующий по выгодности код для буквы «К».
Построим симметричное двоичное дерево.
Теперь отметим на нём буквы «Б», «Н» и «Р», кодовые слова к которым даны в условии.
На дереве видны три кратчайших доступных листа с кодами «01», «001» и «111». Для букв «К» и «О» достаточно выбрать два из них.
Самый короткий код «01» отдадим самой частой букве «О». Для буквы «К» можно выбрать любой из оставшихся кодов – «111» или «001»: они имеют одинаковую длину. Для примера выберем код «111».
Готово, каждая буква имеет своё кодовое слово. Теперь можем вычислить количество двоичных знаков, которое требуется для кодирования слова «коробок»:
Сложим все длины кодовых слов: 6 + 6 + 3 + 2 = 17. Таким образом, для кодирования слова «коробок» нам потребуется 17 двоичных знаков. Это число и запишем в ответ.
И последняя формулировка 4 задания звучит так:
По каналу связи передаются сообщения, содержащие только буквы из набора: В, Е, М, Н, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны: В – 1, М – 001.
Для трёх оставшихся букв Е, Н и Р кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова ВЕРМЕЕР, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Имеем слово «ВЕРМЕЕР». Давайте определим частоту вхождения каждой буквы:
Для буквы «Е» нужно найти самый короткий код, для «Р» – наиболее короткий из оставшихся, а для буквы «Н», которой нет в слове, – любой допустимый код.
Правую ветвь дерева строить не имеет смысла: код 1 уже отведён под букву «В», поэтому его потомки использовать нельзя. Построим только «нулевую» ветвь.
Отметим на дереве известную нам букву «М».
На рисунке показаны шесть доступных листьев, но занять их одновременно нельзя. Есть два основных варианта: выбрать «01» вместе с «0000» и «0001» либо выбрать три трёхбитовых кода «010», «011» и «000».
Здесь необходимо рассмотреть разные варианты. Для буквы «Е» нужен самый короткий код, так как она встречается чаще всего – 3 раза.
Можем рассмотреть такие варианты:
Давайте считать. В первом случае суммарная длина кодовых слов для трёх букв «Е» и двух «Р» будет составлять: 2 + 2 + 2 + 4 + 4 = 14 символов.
Во втором случае получаем 3 + 3 + 3 + 3 + 3 = 15 символов. Значит, выгоднее поместить букву «Е» в лист с двухбитовым кодом, а два оставшихся четырёхбитовых кода отдать буквам «Р» и «Н».
Теперь вычислим количество двоичных знаков, необходимое для кодирования слова «вермеер»:
Складываем все полученные значения и пишем в ответ число 18.
На этом мы закончили разбор алгоритма решения обоих типов 4 задания ЕГЭ по информатике. А попрактиковаться в решении заданий данного типа вы можете в нашем тренажёре.
