4 Три типа задач в задании 4
Три типа задач в задании 4
Формулировки разные, но типов всего три. Узнаёшь тип — знаешь, что делать.
Тип 1. Наименьшая сумма длин кодовых слов
Даны несколько букв, для части известны коды. Нужно достроить коды для остальных так, чтобы условие Фано выполнялось, а сумма длин всех кодов была наименьшей.
Идея: свободные буквы надо посадить в самые короткие свободные ветки. Чем короче код — тем меньше вклад в сумму.
Тип 2. Кратчайший код для конкретной буквы
Даны коды для всех букв, кроме одной (или двух). Нужно подобрать самый короткий код для указанной буквы, а если таких несколько — с наименьшим (или наибольшим) числовым значением.
Идея: найти самые короткие свободные ветки и, если букв ещё несколько, оставить место и для соседей.
Тип 3. Сколько бит уйдёт на кодирование слова
Даны коды части букв, остальные надо достроить оптимально, а затем посчитать, сколько двоичных знаков займёт конкретное слово (например, «КОСОГОР»).
Идея: частым буквам слова — короткие коды, редким — длинные. Это тот же принцип, что и в сжатии данных.