Пусть A и B - двоичные последовательности (последовательности из 0 и 1).
Если A равно length(A) крайним левым битам B, то говорят, что A, является префиксом B.
Например, 00110 является префиксом 001101001, но не 00111 или 100110.
Беспрефиксный код размером n - это такой набор из n отличных битовых последовательностей, в котором ни одна последовательность не является префиксом другой последовательности. К примеру, ниже представлен беспрефиксный код размером 6:
0000, 0001, 001, 01, 10, 11
Теперь предположим, что цена передачи бита '0' - один пенс, а цена передачи бита '1' составляет 4 пенса.
Тогда, общая стоимость выше указанного беспрефиксного кода составляет 35 пенсов, что, как оказалось, является наименьшей возможной стоимостью при несимметричной ценовой политике.
Сокращенно, запишем Cost(6) = 35.
Чему равна стоимость Cost(109)?