BEBRO konkurso užduotys 2017

 

Močiutės uogienė

Taškai: 12

Emilija, Matas ir Kamilė padeda savo močiutei ruošti uogienę. Kad būtų paruoštas stiklainis uogienės, reikia padaryti tris dalykus:

Išplauti stiklainį – tai trunka 3 minutes.

Stiklainį pripilti uogienės – tai trunka 2 minutes.

Uždengti stiklainį – tai trunka 1 minutę.

Tik į švarų stiklainį galima pilti uogienę, be to, tik pilną uogienės stiklainį galima uždengti.

Vadinasi, šis pavyzdys yra negalimas:

Sudarykite 10 minučių darbo planą, pagal kurį galima paruošti didžiausią uogienės stiklainių skaičių.

Nutempkite pele darbus vaizduojančius paveikslėlius ant žydrų stačiakampių.

Paaiškinimas

Šiame uždavinyje nagrinėjama darbo plano tinkle konstrukcija ir atskirų komandų vykdymas vienu metu. Teisingai skirstant darbą reikia preliminariai įvertinti, kiek daugiausia jo galima padaryti, ir stengtis pasiekti šią ribą. Šiuo tikslu naudojamas godusis algoritmas, pritaikytas teisingai formalizuotai užduočiai.

Optimizavimas matematikoje ir informatikoje – tai geriausio elemento išrinkimas iš turimų pasirinkčių. Paprastai optimizavimo problema yra maksimizuoti (rasti didžiausią galimą reikšmę, esant tam tikroms sąlygoms) arba minimizuoti (atitinkamai rasti mažiausią reikšmę) tam tikras funkcijas sistemiškai pasirenkant įvesties reikšmes ir skaičiuojant funkcijos reikšmes.

Optimizavimo algoritmas vadinamas godžiuoju, kai kiekviename jo žingsnyje iš visų galimų pasirinkčių pasirenkamas tuo metu (tame žingsnyje) geriausias variantas ir visai neatsižvelgiama į bendrą rezultatą. Sprendžiant daugelį problemų, godžiojo algoritmo strategija ne visada pateikia optimalų sprendimą, bet, nepaisant to, godžiuoju algoritmu įmanoma rasti optimalų lokalųjį sprendimą, iš kurio galima apytiksliai numatyti optimalų globalųjį sprendimą.

https://en.wikipedia.org/wiki/Project_network

https://en.wikipedia.org/wiki/Greedy_algorithm

Raktiniai žodžiai: optimizavimas, godusis algoritmas.

Atsakymas

Teisingas atsakymas yra

Vienas uogienės stiklainis paruošiamas per 3 + 2 + 1 = 6 minutes. Kiekvienas vaikas dirba po 10 minučių, vadinasi, iš viso dirbama 30 minučių. Taigi daugiausia galima paruošti 30 : 6 = 5 stiklainius.

Pagal darbo planą reikia išplauti, pripilti uogienės ir uždengti 5 stiklainius. Svarbu atkreipti dėmesį į tai, kad negalima pirma pripilti uogienės, o paskui išplauti stiklainių, be to, negalima uždengti nepilnų stiklainių.

5 uogienės stiklainiams paruošti taikykime godųjį algoritmą:

  • Plauti stiklainius, kol nebeliks neplautų stiklainių.
  • Pripilti stiklainius uogienės, kol nebeliks tuščių stiklainių.
  • Uždengti stiklainius, kol nebeliks atidengtų stiklainių.

Šiuo algoritmu gaunamas viršuje pavaizduotas atsakymas.

Svarbu, kad uždavinyje neparašyta, kiek tiksliai stiklainių reikia paruošti, todėl, pavyzdžiui, jei vaikai dirbtų atskirai, paruoštų 3 stiklainius (neteisingas sprendimas):

Gauti klaidingą atsakymą galima ir tuo atveju, jei Kamilė negalėtų uždengti antro ir trečio stiklainio, nes tuo metu stiklainiai dar būtų nepilni. Tada tik trys stiklainiai būtų uždengti:

Interaktyvi užduotis

 

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