2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Dvejetainis viešbutis

Taškai: 6

Matas dirba viešbutyje. Jo šiandienos užduotis – ant kiekvieno namelio pakabinti naują kambario numerį. Pakabinęs 50-ąjį numerį, toliau jis kabina numerius pagal šias taisykles:

  • jei naujas namelio numeris mažesnis už namelio, prie kurio stovi, numerį, eina į kairę,
  • jei naujas namelio numeris didesnis už namelio, prie kurio stovi, numerį, eina į dešinę,
  • jei namelis, prie kurio stovi, neturi numerio, pakabina naują numerį.

Kai kurie nameliai jau sunumeruoti:

Matas turi pakabinti 29 numerį. Remdamiesi taisyklėmis, pažymėkite namelį, ant kurio Matas turi pakabinti šį numerį.

Paaiškinimas

Nameliai atitinka dvejetainio medžio viršūnes. Dvejetainis paieškos medis yra bendra duomenų struktūra informatikoje. Ji naudojama ieškomiems duomenims saugoti. Kiekviena viršūnė tenkina šias savybes:

  • n-tosios viršūnės reikšmė didesnė už visas reikšmes jos kairiajame pomedyje.
  • n-tosios viršūnės reikšmė mažesnė už visas reikšmes jos dešiniajame pomedyje.

Kairysis ir dešinysis pomedžiai yra dvejetainiai paieškos medžiai.

Todėl, kai ieškome viršūnės, žiūrime tik į kairę arba dešinę, bet ne į abi puses.

https://lt.wikipedia.org/wiki/Medis_(duomen%C5%B3_strukt%C5%ABra)#Dvejetainiai_med%C5%BEiai

Raktiniai žodžiai: dvejetainis paieškos medis, algoritmas.

Atsakymas

Teisingas atsakymas yra:

Pradedant nameliu, esančiu greta 50-ojo, 29 yra mažiau nei 50, todėl Matas eina į kairę. Kito namelio numeris 24. 29 yra daugiau už 24, todėl eina į dešinę. Kito namelio numeris 34, o 34 yra mažiau už 29, todėl eina į kairę. Šis namelis dar neturi numerio, ant jo ir pakabinamas naujas numeris.

Interaktyvi užduotis