010
Объяснение:
Изобразим все возможные коды длиной не больше 4 в виде дерева (см. рис.)
Красным цветом помечены вершины, которым соответствуют уже занятые коды. Условие Фано запрещает одному коду быть префиксом (началом) другого, желтым цветом отмечены коды, выбор которых будет противоречить условию Фано (например, если занят код 0010, то нельзя выбрать коды 0, 00, 001).
Оставшиеся не закрашенными коды доступны для выбора, они удовлетворяют условию Фано, а значит, код будет допускать однозначное декодирование. По рисунку видно, что наименьшая длина кода равна 3, есть два варианта: 100 и 010. В ответ пойдёт более правый код, у него числовое значение меньше.
198416 = 1∙163+9∙162+8∙161+4∙160 = 4096+2304+128+4 = 65321
Десятичное в двоичную:
6532/2=3266 (остаток 0)
3266/2=1633 (остаток 0)
1633/2=816 (остаток 1)
816/2=408 (остаток 0)
408/2=204 (остаток 0)
204/2=102 (остаток 0)
102/2=51 (остаток 0)
51/2=25 (остаток 1)
25/2=12 (остаток 1)
12/26 (остаток 0)
6/2=3 (остаток 1)
3/2=1
Теперь справа налево собираем наши остатки (ответную единицу тоже)
Получаем: 1100110000100
Теперь нам нужно сделать нашу двоичную систему отрицательной:
Делаем реверс (справа налево) нашей двоичной системы (1100110000100)
Получаем: 0011001111011 (Заменили все наши нули на единицы, а единицы на нули)
Теперь мы должны прибавить единицу к нашей двоичной системе:
Получаем: 0011001111100
Единицу мы прибавили так:
0011001111011
+
1
1+1=10 (единицу запомнили, переходим к следующей цифре, с.л. единица уже перейдёт в 0)
1+1=10 (опять запомнили и опять единица перешла в 0, переходим к следующей)
1+0=1 (записываем единицу)
Правила прибавления:
1+1=10
0+1=1
0+0=0