Алгоритм на псевдокоде

Алгоритм Фано

P–массив вероятностей, упорядоченный по убыванию

L – левая граница обрабатываемой части массива P

R– правая граница обрабатываемой части массива P

k – длина уже построенной части элементарных кодов

С – массив элементарных кодов

Length – массив длин элементарных кодов.

Fano(L,R,k)

IF (L<R)

k:=k+1

m:=Med(L,R)

DO (i=L,…,R)

IF (i≤m) C[i,k]:=0, Length[i]:= Length[i]+1

ELSE C[i,k]:=1, Length[i]:= Length[i]+1

FI

OD

Fano (L,m,k)

Fano (m+1,R,k)

FI

Функция Med находит медиану массива P, т.е. такой индекс L≤m≤R, что

величина минимальна.

Med (L,R)

S_L:=0

DO (i=L,…,R-1)

S_L:=S_L+p[i] <сумма элементов первой части>

OD

S_R:=p[R] <сумма элементов второй части>

m:=R

DO (S_L ≥ S_R)

m:=m-1

S_L:=S_L-p[m]

S_R:=S_R+p[m]

OD

Med:=m