Изобразим все возможные коды длиной не больше 4 в виде дерева (см. рис.)
Красным цветом помечены вершины, которым соответствуют уже занятые коды. Условие Фано запрещает одному коду быть префиксом (началом) другого, желтым цветом отмечены коды, выбор которых будет противоречить условию Фано (например, если занят код 0010, то нельзя выбрать коды 0, 00, 001).
Оставшиеся не закрашенными коды доступны для выбора, они удовлетворяют условию Фано, а значит, код будет допускать однозначное декодирование. По рисунку видно, что наименьшая длина кода равна 3, есть два варианта: 100 и 010. В ответ пойдёт более правый код, у него числовое значение меньше.
//Обьявляем дополнительные переменные и главный массив, а также два дополнительных - они будут "половинками".
var
a, b, c: array [1..100] of longint;
i, min, n, j, t: longint;
begin
//Читаем количество элементов в нашем массиве.
readln(n);
//Читаем массив.
for i := 1 to n do read(a[i]);
//Заполняем первую "половинку".
for i := 1 to n div 2 do b[i] := a[i];
//Заполняем вторую "половинку". Но раз это уже вторая "половинка" главного массива, то и
//цикл теперь должен начинаться со второй части массива, а заканчиваться уже в его конце.
for i := n div 2 + 1 to n do c[i - n div 2] := a[i];
//Теперь отсортируем первую "половинку" методом выбора. Идея этого метода
//основывается на том, что мы ищем минимальный среди неотсортированных элемент,
//а затем аем его с тем, который стоит сразу после отсортированных.
for i := 1 to (n - 1) div 2 do
begin
min := i;
for j := i + 1 to n div 2 do
if b[min] > b[j] then
min := j;
if min <> i then begin
t := b[i];
b[i] := b[min];
b[min] := t;
end;
end;
//Затем вторую точно также, только стоит обратить внимание на сравнения.
//Так как надо отсортировать по убыванию, то теперь сравнение перед "swap"-ом
//будет другим.
for i := 1 to (n - 1) div 2 do
begin
min := i;
for j := i + 1 to n div 2 do
if c[min] < c[j] then
min := j;
if min <> i then begin
t := c[i];
c[i] := c[min];
c[min] := t;
end;
end;
//А теперь по очереди выводим готовые "половинки", не забывая ставить
//пробел после вывода каждого элемента.
for i := 1 to n div 2 do write(b[i], ' ');
for i := 1 to n - n div 2 do write(c[i], ' ');
end.
010
Объяснение:
Изобразим все возможные коды длиной не больше 4 в виде дерева (см. рис.)
Красным цветом помечены вершины, которым соответствуют уже занятые коды. Условие Фано запрещает одному коду быть префиксом (началом) другого, желтым цветом отмечены коды, выбор которых будет противоречить условию Фано (например, если занят код 0010, то нельзя выбрать коды 0, 00, 001).
Оставшиеся не закрашенными коды доступны для выбора, они удовлетворяют условию Фано, а значит, код будет допускать однозначное декодирование. По рисунку видно, что наименьшая длина кода равна 3, есть два варианта: 100 и 010. В ответ пойдёт более правый код, у него числовое значение меньше.