BEBRO konkurso užduotys 2018

 

Knygų rikiavimas

Taškai: 6

Trys bebrai turi po savo stalą. Ant kiekvieno stalo padėta po dvi knygas. Knygų tvarka sumaišyta, ir bebrai nori jas surikiuoti atlikdami apkeitimo žingsnius.

Yra du žingsnių tipai.
A tipo žingsnis: kiekvienas bebras gali sukeisti dvi ant stalo gulinčias knygas.
B tipo žingsnis: bebrai gali susikeisti kaimyninėmis knygomis su šalia esančiu stalu.

Padėkite bebrams surikiuoti knygas, panaudodami kuo mažiau žingsnių.

Paaiškinimas

Šis uždavinys yra lygiagretaus tinklo rikiavimo algoritmo versija. Pirmiausiajie pradeda sukeisdami knygas ant kiekvieno stalo, kaip nurodyta uždavinyje. Godus algoritmas nusprendžia, ar atlikti apkeitimą, ar ne. Antras žingsnis: vienintelis galimas veiksmas – visi bebrai stengiasi sukeisti knygas tarp stalų. Tuomet vienintelis kito žingsnio galimas veiksmas – sukeisti knygas ant kiekvieno stalo ir t. t. Godus algoritmas intuityvus ir optimalus. Vykdant algoritmą, galima lengvai rasti atsakymą. Toliau pateiktame paveikslėlyje parodyti minėtos strategijos veiksmai pagal rikiavimo tinklą.

Objektų išdėstymas eile pagal kurį nors jų parametrą, skaičiumi – pagal jų dydį, žodžiais – pagal raidžių rikiavimo eilę abėcėlėje ir pan. Rikiuoti galima dvejopai: didėjančiai arba mažėjančiai. Jeigu objektai skaidomi į kelias grupes, sakoma, kad jie rūšiuojami. Rūšiavimas gali būti panaudotas kaip pagalbinis rikiavimo veiksmas. Objektai surūšiuojami į grupes (rūšis), po to grupės sujungiamos, ir gaunama surikiuotų objektų eilė. Atkreipiame dėmesį, kad anglų kalboje neskiriamos rikiavimo ir rūšiavimo sąvokos. Į tai reikia reikia atsižvelgti, verčiant programas.

Atsakymas

3 žingsniai

Interaktyvi užduotis

 

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