Kairėn–dešinėn
Taškai: 6
Bebrai sukūrė programą parko medžių kodams rasti. Ji aprašoma pagal šias taisykles:
|
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?
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.
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.