BEBRO konkurso užduotys 2017

 

Rutuliukai

Taškai: 9

Sunumeruoti rutuliukai rieda nuožulniąja plokštuma. Kai rutuliukai sukrenta į plyšį, pasikeičia jų eiliškumas. Jei rutuliukas pasiekia plyšį, į jį įrieda tik tada, jei tame plyšyje užtenka vietos. Kitu atveju rutuliukas rieda toliau. Kiekviename plyšyje yra kaiščių, kurie gali būti ištraukiami. Tada spyruoklė išmeta rutuliukus ir uždaro plyšį.

Štai kaip viskas atrodo:

Nuožulniąja plokštuma rieda 10 iš eilės sunumeruotų rutuliukų. Trys plyšiai – A, B ir C – turi atitinkamai vietos trims, dviem ir vienam rutuliukui. Kaiščiai ištraukiami tokia eile: A, B, C. Kiekvienas kaištis ištraukiamas tik tada, kai visi rutuliukai nustoja riedėti.

Kokia galutine eile išsidėstys rutuliukai?

A

B

C

D

Paaiškinimas

Plyšiai atitinka dėklų (angl. stack) duomenų struktūras. Tai duomenų tvarkymo būdas, kuris remiasi principu „paskutinis į maišą, pirmas iš maišo“. Pavyzdžiui, pirmas į plyšį įriedėjęs rutuliukas iš plyšio išrieda paskutinis. Nors idėja ir labai paprasta, tačiau dažnai būna labai naudinga programuojant. Pavyzdžiui, norima ištirti, kaip naudojamas dėklas, kai tikrinamas skliaustų subalansavimas. Skliaustai reiškinyje ((1+2)*3) yra subalansuoti, bet reiškinyje ((4+5)*(6–7) taip nėra. Visi atidaromieji skliaustai sumetami į vieną dėklą, ir, kai tik randamas atitinkamas uždaromasis skliaustas, atidaromasis skliaustas išmetamas iš dėklo viršaus. Užuot ėmus labai sudėtingus algoritmus, pakanka principo „paskutinis į maišą, pirmas iš maišo“.

Plačiau skaitykite čia

http://ims.mii.lt/EK%C5%BD/enciklo.html?word=d%EBklas

 

Raktiniai žodžiai: dėklas, duomenų struktūros.

Atsakymas

Teisingas atsakymas yra

A plyšyje vietos yra trims rutuliukams, todėl toliau riedės ketvirtas ir kiti rutuliukai. B plyšyje telpa du rutuliukai, todėl toliau riedės šeštas ir kiti rutuliukai. C plyšyje liks tik vienas – šeštas – rutuliukas, todėl horizontaliai iš kairės į dešinę išsidėstys septintas, aštuntas, devintas ir dešimtas rutuliukai. Ištraukus A plyšio kaištį, prie dešimto rutuliuko nuriedės trečias, antras ir pirmas rutuliukai. Ištraukus B plyšio kaištį, nuriedės penktas ir ketvirtas rutuliukai. Pagaliau ištraukus C plyšio kaištį, prie visų nuriedės šeštasis rutuliukas.

 

 
Informacija atnaujinta 2017-11-13 16:52:39