Наименьшая суммарная длина

Наименьшая суммарная длина

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

Задача звучит как оптимизация, но никакого перебора вариантов в голове не нужно — работает то же дерево и одно простое правило.

Раздаём оставшиеся буквы

Классика экзамена: буквы А, Б, В, Г, Д, для А взяли 0, для Б — 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Смотрим на дерево. Ветка нуля занята буквой А целиком. Под единицей занято 10. Свободна ровно одна точка — 11, а разместить надо три буквы.

Отдать 11 одной букве нельзя — двум остальным ничего не достанется. Спускаемся: под 11 лежат 110 и 111. Одну точку отдаём букве В. Вторую снова делим — на 1110 и 1111, туда садятся Г и Д.

Приём в двух словах

Строим дерево, отмечаем занятое, а оставшиеся буквы сажаем как можно выше — но так, чтобы всем хватило места.

Полезное наблюдение, которое экономит время: каждый спуск на уровень вниз удваивает число свободных точек. Была одна — стало две, было две — стало четыре. Отсюда прикидка: если свободна одна точка, а букв три, спускаться придётся дважды.

И не путай два вопроса. «Сумма длин всех кодовых слов» — складываем по всем буквам алфавита, включая те, что даны в условии. «Сумма для оставшихся букв» — только по тем, чьи коды мы придумали. В нашем примере это 14 и 11 соответственно.

Проверь себя