2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Kairėn–dešinėn

Taškai: 6

Bebrai sukūrė programą parko medžių kodams rasti. Ji aprašoma pagal šias taisykles:

  • Kiekvienas parko medis pažymėtas raide.
  • Kiekviena raidė randama posūkiais kairėn arba dešinėn, kol nusigaunama iki to medžio.
  • Kiekvienos raidės kodas prasideda nuo įėjimo į parką.

Pavyzdžiai:

  • Raidės A kodas yra KK, nes nuo įėjimo iki medžio A turime pasukti kairėn du kartus.
  • Žodžio BAR kodas yra KDKKKD.

Kiek raidžių bebrų programoje atitinka žodį BEAR?

Paaiškinimas

Jeigu kompiuteris, naudodamas mūsų kairėn–dešinėn kodą, pakeičia raidę K skaičiumi 0, o raidę D skaičiumi 1, kairėn–dešinėn kodas tampa dvejetainiu kodu. Tada parko planas tampa kompiuterio duomenų struktūra, vadinama dvejetainiu medžiu. Tai reiškia, kad ilgas ir sudėtingas maršrutas kompiuterio atmintyje užima labai mažai vietos.

Įdomus dalykas, kad šiame kode nereikia jokių kablelių, tarpų ar kitų skiriamųjų ženklų. Galite pabandyti dekoduoti atsakymą ir pamatysite, kad nereikia jokių tarpų norint nurodyti, kur vienos raidės kodas baigiasi ir prasideda kitos raidės kodas. Toks kodas vadinamas prefiksiniu kodu. Tai reiškia, kad kodas yra netgi trumpesnis.

Raktiniai žodžiai: prefiksas, dvejetainis medis.

Atsakymas

Teisingas atsakymas yra 9.

Tolesnėje lentelėje surašyti visų raidžių kairėn–dešinėn kodai

B

E

A

R

KDK

KDD

KK

D

Iš čia lengvai gauname žodžio BEAR kodą: KDKKDDKKD.

Taip pat matome, kad bebrų programoje žodį BEAR atitinka 3 + 3 + 2 + 1 = 9 raidės.

Interaktyvi užduotis