BEBRO konkurso užduotys 2018

 

Knygų rinkinio rikiavimas

Taškai: 9

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.
Pirmojo tipo žingsnis: kiekvienas bebras gali sukeisti dvi ant stalo gulinčias knygas (A pavyzdys).
Antrojo tipo žingsnis: bebrai gali susikeisti kaimyninėmis knygomis su šalia esančiu stalu (B pavyzdys).

Pirmu žingsniu kiekvienas bebras sukeičia knygas ant savo stalo.

Kiek mažiausiai žingsnių reikia, kad knygos būtų išrikiuotos 1, 2, 3, 4, 5, 6?

A. trys žingsniai

B. keturi žingsniai

C. penki žingsniai

D. šeši žingsniai

Paaiškinimas

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.

Raktiniai žodžiai: godus algoritmas, lygiagretus tinklas, rikiavimas.

Atsakymas

Teisingas atsakymas: B.

Š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ą.

 

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