Megoldás: Építkezés
Adatstruktúta
A speciális munkák kezelése nem fog sok gondot okozni. A feladat szövege szerint ugyanis az ilyen munkák csak egymással egy napon nem végezhetőek el. Arról viszont nem ír, hogy egy olyan napon, amikor egy speciális munkát végezünk, ne dolgozhatnánk más közönséges munkákon is. Tehát a speciális munkákat is vehetjük közönséges munkáknak, amiknek egyszerűen csak más módon atdák meg az egymástól-függését. Mert ha pl. 9 6 3 8 a speciális munkák sora, akkor azt egyszerűen fel lehet bontani a 9 6, a 6 3 és 3 8 megelőzési párok sorozatára.
A megelőzési párokat egy 200-szor 200-as két dimenziós tömbben fogjuk tárolni. Legyen előz[a, b] = Igaz, ha az a sorszámú munkát el kell végezni a b munka előtt, és Hamis ha ezt nem muszáj! (Ez egyébjént egy irányított gráf, ahol akkor van a és b között irányított él, ha a megelőzi b-t.)
Betöltés
Eljárás Betolt()
a := 0; b := 0;
Beolvas(N, K, T);
Ciklus i := 1-től K-ig
Beolvas(b);
Ha a <> 0 Akkor
eloz[a, b] := Igaz;
Elágazás Vége
a := b;
Ciklus Vége
Ciklus i := 1-től T-ig
Beolvas(a, b);
eloz[a, b]:= Igaz;
Ciklus Vége
Eljárás Vége
Megoldás
A feladat valójában a munkák Topologikus Sorrendjének meghatározása, de a neve ellenére ez az algoritmus józan ésszel is könnyen érthető lesz... Egy egszerű lépést kell ugyanis ismételgetni: keressük meg az összes olyan munkát, amit nem előz meg egy munka sem, jelöljük be mindet az első napra, és töröljük őket az eloz[] tömbből. Így a törlés miatt már követező lépésben is lesz néhány munka, amit nem előz meg más, ezeket természetesen a második napra kell bejelölni.
(Az olyan munkákat, amiket nem előz meg egy másik sem, forrásoknak nevezzük; az olyanokat meg, amik nem előznek meg semmit, nyelőknek.)
A lépést egyébként addig kell ismételgetni, amíg találunk újabb forrásokat.
Leprogramozás
A megoldás tárolására felveszünk még egy 200-as nap[] és egy ugyanakkora munka[] tömböt. A munka[] tömbbe az elvégzés sorrendjében kerülnek a munkák, és a nap[i] tárolja, hogy a munka[i] munkát hányadik napra tette be algoritmus.
(M fogja számolni a napokat, kesz a betett munkákat.) Első kísérletünkben fel fogjuk használni a Forras(i) és a Torol(i) eljárásokat is. Az első megnézi, hogy léteznek-e az i. munkát megelőző más munkák, és Igaz-al tér vissza, ha nincsenek. A második pedig kitörli az összes i. munkára való hivatkozást az eloz[] tömbből.
Eljárás Megold()
M := 0; kesz:= 0;
voltuj := Igaz;
Ciklus Amíg (voltuj)
M := M + 1;
voltuj := Hamis;
Ciklus i := 1-től N-ig
Ha (Forras(i)) Akkor
kesz := kesz + 1;
munka[kesz] := i;
nap[kesz] := M;
voltuj := Igaz;
Torol(i);
Elágazás vége
Ciklus Vége
Ciklus Vége
M := M - 1;
Ha (kesz = N) Akkor
MegoldasKi(M);
Különben
Kiir(0)
Elágazás Vége
Eljárás Vége
M egyel mindig "túlszalad" a ciklusban.
Ha nem sikerült minden munkát elhelyezni, akkor 0-t írunk ki. (Ilyenkor egyébként egy irányított kör van a munkák gráfjában.)
Ezzel az algoritmussal viszont van egy kis gond még. Ugyanis amint talál egy forrás típusú munkát, rögtön kitörli azt. Így ugyan helyes sorrendben fogja kiadni a munkákat, de lehetséges, hogy egy napra több egymástól függő munkát is berak. Ezért a munkák törlését mindig akkor szabad csak elvégezni, amikor már összeszedtük az összes aznapi munkát. A következő kódrészlet a kesz munka-számláló alapján megkeresi az adott (M.) napra berakott munkákat, és törli őket:
Ha voltuj Akkor
i := kesz;
Ciklus Amíg (i > 0) és (nap[i] = nap[kesz])
Torol( munka[i] );
i:= i - 1;
Ciklus Vége
Elágazás Vége
A Forras(i) eljárás egy lehetséges megírása.
Eljárás Forras(i)
j := 1;
Ciklus Amíg ((j <= N) és (eloz[j, i] = Hamis)) j := j + 1;
Forras := j > N;
Eljárás Vége
Többször is kihasználtuk, hogy a fordító olyan kódot készít, ami balról jobbra végzi a kiértékelést. Tehát pl. az előbb ha j > N, akkor már nem vizsgálja meg a második feltételt is. (Ez a legtöbb nyelvben így van, Pascalban kérhető teljes kiértékelés is, de ez az alapértelmezett.)
A Torol(i) eljárás:
Eljárás Torol(i)
Ciklus j := 1-től N-ig
eloz[i, j] := Hamis;
eloz[j, i] := Hamis;
Ciklus Vége
Eljárás Vége
eloz[j, i]-t elvben nem kellene törölni, mert i egy forrás típusú munka... Már csak egy dolog hiányzik a megoldásunkból: figyelni kell arra is, hogy egy munkát ne vegyünk be többször a megoldásba. Mert ha pl. egy munka egy nap vizsgálatánál már forrás, akkor onnantól mindig forrás fog maradni. Felvehetünk pl. egy torolt[] tömböt, aminek kezdetben minden eleme Hamis, és az időközben törölt munkáknál beállítjuk Igazra. Ezek után még figyelni kell rá, hogy ne vegyünk be olyan munkákat, amikre torolt[munka] = Igaz.
A kiírás:
Eljárás MegoldasKi(M)
Kiir(M); UjSor;
j := 1;
Ciklus i := 1-től M-ig
Ciklus Amíg ((j <= N) és (nap[j] = i))
Kiir(munka[j], ' ');
j := j+1;
Ciklus Vége
UjSor;
Ciklus Vége
Eljárás Vége
Megoldások
