4 Три типа задач в задании 4

Три типа задач в задании 4

Формулировки разные, но типов всего три. Узнаёшь тип — знаешь, что делать.

Тип 1. Наименьшая сумма длин кодовых слов

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

Идея: свободные буквы надо посадить в самые короткие свободные ветки. Чем короче код — тем меньше вклад в сумму.

Иллюстрация к заданию 4, рисунок 4

Тип 2. Кратчайший код для конкретной буквы

Даны коды для всех букв, кроме одной (или двух). Нужно подобрать самый короткий код для указанной буквы, а если таких несколько — с наименьшим (или наибольшим) числовым значением.

Идея: найти самые короткие свободные ветки и, если букв ещё несколько, оставить место и для соседей.

Иллюстрация к заданию 4, рисунок 5

Тип 3. Сколько бит уйдёт на кодирование слова

Даны коды части букв, остальные надо достроить оптимально, а затем посчитать, сколько двоичных знаков займёт конкретное слово (например, «КОСОГОР»).

Идея: частым буквам слова — короткие коды, редким — длинные. Это тот же принцип, что и в сжатии данных.

Три типа задач в задании 4 — Задание 4 ЕГЭ 2027 | Методички — Профиматика