Задание 4

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.

Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Теория

Для решения подобного вида задач удобно нарисовать бинарное (двоичное) дерево. Причем в данной задаче говорится о прямом условии Фано (сначала), если это не оговорено, то придется проверить и обратное условие (с конца).

Кодирование может быть равномерное и неравномерное, в большинстве задач речь идет о неравномерных кодах. Если будет задача про кратчайший код для какой-либо фразы - используйте алгоритм Хаффмана - использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины

Решение

Строим бинарное дерево и отмечаем на конце отрезков буквы. Свободное место зеленым, значит этот код буквы B.

Ответ

1000 (Время не более 5 минут)