9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

Кодовые слова 0, 10, 110 и 1110 образуют ветви двоичного дерева. Код для Д не может совпадать с уже имеющимся словом, начинаться с одного из них или быть началом уже имеющегося слова.

Наименьший свободный вариант — 1111: он не является началом другого имеющегося кодового слова, и ни одно из имеющихся слов не является его началом.

Ответ: кратчайшее возможное кодовое слово для Д — 1111.