
Saliutas
Taškai: 9
Du draugai bebrai gyvena savo pilyse, kurias skiria didelis miškas. Jie kiekvieną vakarą siunčia vienas kitam žinutes, į dangų vieną po kitos leisdami fejerverko raketas. Kiekviena žinutė sudaryta iš žodžių eilės. Kiekvienas žodis yra koduojamas raketų seka. Bebrai vartoja tik penkis skirtingus žodžius (žr. lentelę). Pavyzdžiui, žinutei „Mediena Pilis Mediena“ išsiųsti būtų iššautas toks fejerverkas: Pastebima, kad fejerverko kodai yra dviprasmiški. |
|
Kiek skirtingų prasmių galėtų turėti šis fejerverkas?
Daugelis informatikoje įprastų kodų visiems žodžiams, iš kurių sudarytos žinutės, skiria vienodą bitų skaičių. Tai didelis privalumas, nes iškoduoti paprasta, nevienareikšmiškumo negali būti. Atlikdami šią bebrų užduotį, turime dvi fejerverkų raketų rūšis – bitus 0 ir 1. Kad atskirtų vieną nuo kito penkis žodžius, kai žodžių kodų ilgis toks pat, draugams bebrams visada reiktų trijų raketų ((23=8) > 5). Tikriausiai jie labai dažnai vartoja žodį „Mediena“, žodžius „Pilis“ ir „Upė“ – rečiau, o žodį „Uola“ – labai retai. Todėl bebrai sugalvojo ekonomišką kodą, kuriuo sutaupo daug raketų. Protinga?
Būtų dar protingiau, jeigu būtų sugalvoję priešdėlinį kodą – tokį, kad iš pirmosios raketos (priešdėlio) būtų galima nustatyti po jo einančių raketų (bitų) skaičių, priklausančių tam pačiam žodžiui. Tada išvengtų daugiaprasmių žinučių ir galėtų sutaupyti šiek tiek raketų. Pavyzdys: Mediena = 01, Pilis = 00, Upė = 100, Medis = 101, Uola = 110. Čia pirmasis ženklas yra prefiksas. Jei 0, tai dviejų ženklų kodas, jei 1 – trijų.
Teisingas atsakymas yra 4.
Žinutė gali reikšti:
- Pilis Uola Mediena Upė
- Pilis Pilis Pilis Upė
- Uola Medis Upė
- Uola Mediena Pilis Upė
Siekdami įsitikinti, kad nėra kitų reikšmių, sistemingai nagrinėkime, kaip parodyta paveikslėlyje.
- Pradedame nuo pirmosios raketos. Ji viena neturi jokios reikšmės. Po raketa užrašome 0.
- Pirmosios dvi raketos gali reikšti tik „Pilis“, po antrąja raketa užrašome 1, žymintį gautų reikšmių skaičių.
- Trečioji raketa esamoje raketų sekoje galėtų turėti naują reikšmę. Ar tikrai ji bus nauja? Jeigu čia baigtųsi visa raketų seka, tai ankstesnis sprendimas (Pilis) netektų galios, nes trečioji raketa būtų beprasmė. Todėl kol kas reikšmė „Uola“ lieka vienintelė ir po trečiąja raketa rašome 1. Ankstesnis sprendimas (Pilis) lieka „užšaldytas“. Ar jis turės tęsinį, pamatysime nagrinėdami tolesnes raketas.
- Ketvirtoji raketa gali raketų 1–2 seką (Pilis) pratęsti vėl tuo pačiu žodžiu „Pilis“, bet gali ir raketų 1–2–3 (Uola) seką pratęsti žodžiu „Mediena“. Abi šios sekos turėjo po vieną reikšmę. Todėl po ketvirtosios raketos turėsime 1+1=2 reikšmes.
- Tokį pat būdą taikome kiekvienai kitai raketai ir žiūrime atgal iki trijų raketų (tiek raketų ilgiausiame kode). Patikrinę paskutinę raketą gauname visų galimų reikšmių skaičių.
Informacija atnaujinta 2015-12-03 07:50:57