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 |
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
C yra neteisinga seka. 10 veiksmas turi būti atliktas prieš pradedant 6 veiksmą. Visi kiti variantai yra teisingi sprendimai.