2014 2015 2016 2017 2018

Apsirengimo tvarka

Taškai: 9

Bebriukas Haris šiandien atsikėlė vėliau, nei planavo, ir dabar skuba į mokyklą. Mokykloje vyks renginys, lankysis žinomas architektas, todėl Hariui svarbu gerai atrodyti.
Norėdamas apsirengti, Haris turi atlikti 10 veiksmų. Kai kuriuos veiksmus Haris gali atlikti tuo pačiu metu, kad sutaupytų laiko ir spėtų į renginį. Tačiau kai kuriuos veiksmus jis gali atlikti tik baigęs ankstesnius. Pavyzdžiui, apsiauti batus galima tik tada, kai jau užsimautos kelnės ir kojinės.

Haris gali apsirengti įvairiai derindamas veiksmus. Tačiau viena iš pateiktų sekų nepadės Hariui apsirengti. Kuri?

A. 1, 9, 4, 2, 7, 10, 6, 8, 3, 5 C. 1, 9, 4, 7, 6, 5, 2, 10, 8, 3
B. 1, 9, 4, 7, 10, 6, 2, 5, 8, 3 D. 1, 9, 4, 7, 2, 10, 6, 3, 5, 8
Paaiškinimas

Labai dažnai užduotys turi išankstinių sąlygų. Vienas iš gerai žinomų pavyzdžių – apsirengimas. Reikia pirma apsivilkti apatinius, o tik tada mautis kelnes ir vilktis marškinėlius. Švarkas apsivelkamas dar vėliau. Kita vertus, nesvarbu, kada užsimausite kojines – prieš kelnes ar po jų. Kai tik tam tikros užduotys turi tarpusavio priklausomybių, jos sudaro vadinamąją dalinę tvarką. Ši tvarka dažnai pateikiama orientuotu grafu be ciklų, kur kiekviena užduotis yra viršūnė, o kiekviena išankstinė sąlyga – lankas. Jei grafas turėtų ciklų, atlikti veiksmų nepavyktų. Norint rasti tvarką, kuri tenkintų išankstinius reikalavimus, galima naudoti topologinio rikiavimo algoritmą. Jis fiksuoja visas viršūnes, kurių išankstinės sąlygos yra tenkinamos, išrenka vieną iš jų ir sudeda visas viršūnes, kurių visos išankstinės sąlygos šiuo metu patenkintos. Tai pavyzdys godžiojo algoritmo, kurio kiekviename žingsnyje pasirenkamas geriausias variantas.

Reikšminiai žodžiai: tvarka, eiliškumas, dalinė tvarka, grafas, orientuotas grafas be ciklų, topologinis rikiavimas

Atsakymas

C yra neteisinga seka. 10 veiksmas turi būti atliktas prieš pradedant 6 veiksmą. Visi kiti variantai yra teisingi sprendimai.