logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Inne, zadanie nr 4737

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

gumisafc
postów: 16
2016-06-20 18:36:52

Częstość występowania znaków podaje tabelka :
Znak a b c d e f
Częstość 27 87 17 77 47 57
Tworzymy drzewo Huffmana tak, że lewym poddrzewem
staje się zawsze drzewo o mniejszej częstości. Kody
tworzymy w ten sposób, że każda lewa krawędź
otrzymuje wartość 0, a prawa 1. Podaj wartości kodu znaków.
Czy jest ktoś w stanie pomóc mi z tym zadaniem ?


tumor
postów: 8070
2016-06-20 18:54:33

zapis (x,y) będzie oznaczał drzewo o poddrzewach x,y
W korzeniu takiego drzewa sumujemy częstości elementów.

Wyjściowo mamy oddzielne drzewa
a,b,c,d,e,f
Łączymy dwa o najniższej częstości, teraz jest
(c,a),b,d,e,f
(elementy c,a mają w sumie częstość 44)
Łączymy dwa o najniższej częstości
((c,a),e),b,d,f
(elementy c,a,e mają w sumie częstość 91)
Łączymy dwa o najniższej częstości
(f,d),((c,a),e),b
(elementy f,d mają w sumie częstość 134)
Łączymy dwa o najniższej częstości
(b,((c,a),e)),(f,d)
Łączymy dwa o najniższej częstości
((f,d),(b,((c,a),e)))

i tak na przykład element f to lewy lewy, czyli 00
element a to prawy, prawy, lewy, prawy, czyli 1101


gumisafc
postów: 16
2016-06-20 19:40:27

No wreszcie wyszło, dziękuje bardzo.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj