Для кодировки некоторой последовательности, состоящей из букв А, Б, В,

Решение (1 способ, проверка условий Фано):

1) Для конкретного декодирования довольно, чтоб производилось условие Фано либо оборотное условие Фано;

2) Проверяем последовательно варианты 1, 3 и 4; если ни один из их не подойдет, придется избрать вариант 2 (это невероятно);

3) Проверяем вариант 1: А00, Б01, В011, Г101, Д111.

прямое условие Фано не производится (код буковкы Б совпадает с началом кода буковкы В);

обратное условие Фано не производится (код буковкы Б совпадает с окончанием кода буквы Г); потому этот вариант не подходит;

4) Проверяем вариант 3: А00, Б010, В01, Г101, Д111.

прямое условие Фано не производится (код буквы В совпадает с началом кода буквы Б);

оборотное условие Фано не производится (код буквы В совпадает с окончанием кода буковкы Г); потому этот вариант не подходит;

5) Проверяем вариант 4: А00, Б010, В011, Г01, Д111.

прямое условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но обратное условие Фано выполняется (код буковкы Г не совпадает с окончанием кодов остальных буковкы); потому этот вариант подходит;

Ответ: 4

Решение (2 метод, дерево):

1) Построим двоичное дерево, в котором от каждого узла отходит две ветки, подходящие выбору последующей цифры кода 0 или 1; разместим на этом дереве буковкы А, Б, В, Г и Д так, чтоб их код выходил как последовательность чисел на рёбрах, сочиняющих путь от корня до данной буковкы (красным цветом выделен код буковкы В 011):

однозначность декодирования получается за счёт того, что при движении от корня к любой буковке в середине пути не встречается иных букв (выполняется условие Фано);

3) Сейчас проверим варианты ответа: предлагается перенести одну из букв, Б, В либо Г, в узел с кодом 01, выделенный синим цветом

4) Лицезреем, что при переносе хоть какой из этих букв нарушится условие Фано; к примеру, при переносе буквы Б в голубий узел она оказывается на пути от корня до В, и т.д.; это означает, что предлагаемые варианты не дозволяют выполнить прямое условие Фано

5) Охото уже избрать вариант 2 (это невероятно), но у нас есть еще оборотное условие Фано, для которого тоже можно выстроить аналогичное дерево, в котором движение от корня к буковке дает её код с конца (красным цветом выделен код буквы В 011, записанный с конца):

видно, что оборотное условие Фано также производится, поэтому что на пути от корня к хоть какой буковке нет других букв

6) В данных вариантах ответа предлагается переместить буковку Б, В либо Г в синий узел; понятно, что Б либо В туда перемещать нельзя перемещённая буковка отказывается на пути от корня к букве Г; а вот буковку Г переместить можно, при этом оборотное условие Фано сохранится

Ответ: 4