Analiza problemei a9 (demo CSE 2018)

Timpul de executie de 2 min, complexitate și la momentul inițial

Pentru a codifica o secvență constând din literele A, B, C, D și E, am decis să utilizeze un cod binar non-uniform pentru a decodifica în mod unic secvența binară care apare în partea de primire a canalului de comunicație. Noi folosim acest cod: A-1, B-000, B-001, G-011. Se specifică modul în care cuvântul de cod care urmează să fie codificat litere D. Lungimea cuvântului de cod pentru a fi cel mai mic dintre toate. Codul ar trebui să satisfacă proprietatea de decodare lipsită de ambiguitate.

Dacă decodare lipsită de ambiguitate a codului de un singur caracter nu ar trebui să fie duplicarea (repetarea) a unui alt cod de caracter. pentru că Lungimea de cod ar trebui să fie mai mic, apoi începe cu lungimea de cod = 1.

Codurile posibile sunt: ​​0, 1.

„0“ nu este potrivit, deoarece face parte din literele de cod: B, C, D

„1“ nu este potrivit, deoarece. un astfel de cod este codat litera A

Ia un cod de lungime = 2.

Codurile posibile sunt: ​​00,01,10,11

„00“ - nu este potrivit, deoarece face parte din literele de cod: B, C

„01“ - nu este potrivit, deoarece face parte din literele de cod T

„10“ și „11“ - nu sunt potrivite, deoarece începe cu un „1“, iar acest cod este codat litera A

Să considerăm o lungime cod = 3.

Codurile posibile: 000,001,010,011,100,101,110,111.

aruncați imediat codurile care încep cu „1“, în mod inutil. acest cod este codat litera A.

„000“ - nu este potrivit, deoarece un astfel de cod este codat litera B

„001“ - nu este potrivit, deoarece un astfel de cod este codat în litera

„010“ - este cazul, deoarece cod, astfel, nimic codificat