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.
Fejerverkas galėtų reikšti taip pat ir „Medis Mediena“.

Žodis Raketų kodas
Pilis
Medis
Uola
Upė
Mediena

Kiek skirtingų prasmių galėtų turėti šis fejerverkas?

Paaiškinimas

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ų.

Atsakymas

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ų.
Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.