Ответ:
Поскольку кодовое слово A — 0, остальные слова не могут начинаться с 0. Слово Б — 10, поэтому другие кодовые слова не могут начинаться и с 10. Значит, каждое из слов для В, Г, Д, Е должно начинаться с 11.
Чтобы получить четыре различных префиксно-свободных слова в ветви 11 с наименьшей суммой длин, разделим эту ветвь на две части, а каждую из них — ещё на две. Получатся четыре слова длины 4: 1100, 1101, 1110, 1111. Более короткий набор из четырёх слов невозможен: в двоичном дереве четыре конечные вершины требуют не менее восьми шагов суммарно от вершины 11; к ним добавляются по два начальных бита.
Например, можно назначить: В — 1100, Г — 1101, Д — 1110, Е — 1111. Все четыре слова имеют длину 4, и ни одно не является началом другого.
Сумма длин: 4 + 4 + 4 + 4 = 16.
Ответ: 16.
Поскольку кодовое слово A — 0, остальные слова не могут начинаться с 0. Слово Б — 10, поэтому другие кодовые слова не могут начинаться и с 10. Значит, каждое из слов для В, Г, Д, Е должно начинаться с 11.
Чтобы получить четыре различных префиксно-свободных слова в ветви 11 с наименьшей суммой длин, разделим эту ветвь на две части, а каждую из них — ещё на две. Получатся четыре слова длины 4: 1100, 1101, 1110, 1111. Более короткий набор из четырёх слов невозможен: в двоичном дереве четыре конечные вершины требуют не менее восьми шагов суммарно от вершины 11; к ним добавляются по два начальных бита.
Например, можно назначить: В — 1100, Г — 1101, Д — 1110, Е — 1111. Все четыре слова имеют длину 4, и ни одно не является началом другого.
Сумма длин: 4 + 4 + 4 + 4 = 16.
Ответ: 16.
