Bebrų viešbutis

Taškai: 12

Darbštūs bebrai pastatė viešbutį, jame įrengė daugybę kambarių.
Iš kiekvieno kambario galima patekti į kitus kambarius einant į kairę, į dešinę arba atgal. Suprantama, bebrai kambarius sunumeravo – iš kairės į dešinę, bet ne iš eilės, todėl gretimų kambarių numeriai labai skiriasi.

Raskite kambarį, kurio numeris 1337!
Spustelėkite rodykles po durimis su numeriu, kad galėtumėte eiti į kitą kambarį kairėn, dešinėn arba atgal.

Paaiškinimas

Bebrai gerai sugalvojo, kaip išdėstyti ir sunumeruoti kambarius, kad ieškant reikiamo kambario, kiekviename žingsnyje būtų aišku, į kurią pusę reikia sukti. Kiekvienąkart nusprendus pasukti į tam tikrą pusę, atmetama pusė galimų sprendimų. Jei kambariai būtų išdėstyti linijiniu būdu, reikiamo kambario paieška užtruktų daug ilgiau, nes reikėtų užsukti į kiekvieną kambarį.
Dažniausiai kompiuteriuose tokiu pat būdu laikomi duomenys. Informatikoje tai vadinama dvejetainiu paieškos medžiu. Kai sudaroma tokia duomenų laikymo struktūra, tarp milijono telefono numerių galima rasti reikiamą numerį daugiausiai naudojantis 20 žingsnių. Be abejo, kad būtų įmanoma tokia paieška, medžio duomenys turi būti tinkamai sutvarkyti.

Atsakymas

Numeruodami kambarius bebrai remiasi štai tokia taisykle: ieškodami vidinio kambario kambaryje su mažiausiu numeriu turėsime pasukti į kairę pusę, ieškodami vidinio kambario kambaryje su didžiausiu numeriu turėsime pasukti į dešinę pusę. Išsiaiškinę šią taisyklę, nesunkiai rasime ieškomą kambarį. Iš kambario, kurio numeris 5499, galima patekti į kambarį 1337 atliekant veiksmų seką, pavaizduotą paveiksle:

Interaktyvi užduotis

 

 
Informacija atnaujinta 2015-12-03 07:50:57