kod Huffmana

[pool]

Mam takie zadanie:
Opracować kod Huffmana dla alfabetu, w którym prawdopodobieństwo wystąpienia poszczególnych znaków \(\displaystyle{ X1, X2,...,Xn}\) przedstawiono poniższym szeregiem.

\(\displaystyle{ \frac{1}{2}}\) \(\displaystyle{ \frac{1}{11}}\)\(\displaystyle{ \frac{1}{14}}\)\(\displaystyle{ \frac{1}{17}}\)\(\displaystyle{ \frac{1}{20}}\)\(\displaystyle{ ...}\)

Liczba elementów szeregu(tj. liczba znaków n w alfabecie) powinna być wybrana w ten sposób, żeby suma prawdopodobieństw wszystkich n znaków była równa 1 z dokładnością \(\displaystyle{ \pm 0,02}\). Obliczenia prowadzić z dokładnością 3-4 cyfr po przecinku.

Jak się za to zabrać?

[spajder]

Najpierw musisz policzyć, ile będzie znaków, tzn. tak długo dodajesz do siebie wyrazy szeregu, aż dostaniesz 1 (z potrzebną dokładnością).
Jak już będziesz miał to prosto, bo będziesz miał posortowaną listę symboli - wtedy po prostu budujesz odpowiednie drzewo binarne (albo trójkowe, bo też można, ale to trochę bardziej skomplikowane).