Utolsó módosítás: 2008. december 3.
Az összes nyilvános példa bemenetet és kimenetet és a forráskódokat (a heti házi feladatokéval) egyben le lehet tölteni:
Egy feladat bizonyos részfeladatokból áll. Akárhány részfeladatot is lehet egyszerre végezni, de a részfeladatok között függőségek vannak, amik ezt korlátozzak. Egy feladatot csak akkor lehet elkezdeni, amikor már befejeztünk minden feladatot, amitől ez a feladat függ.
A részfeladatokat egy szövegfájl adja meg, aminek minden sorában először a feladat neve, aztán a feladat elvégzéséhez szükséges idő (napban) áll, majd azon feladatok neve, amitől ez a feladat függ.
Itt egy példa.
vakolat 1 ablakok mosdo 16 ablakok teto teveantenna udvar kabelek 23 ablakok teto teveantenna udvar mosdo teveantenna 13 teto ablakok 14 engedely 5 teto 3 udvar 3 ablakok teto
Amint látjuk, ebben a példában az építési engedélyt ugyan meg kell szerezni, de ettől nem függ semmilyen másik feladat, csinálhatjuk akár az egész ház felépítése után is. Másrészt a tévéantennát csak akkor szerelhetjük fel, ha a tető már fel van húzva. Az udvart csak akkor hozhatjuk rendbe, ha már a tető is kész, és az ablakok is, így lehet, hogy az udvaron és a tévéantennán egyszerre fogunk dolgozni.
Ez a mintapélda nagyon egyszerű lesz: csak sorbarendezzük a bemenet sorait valamilyen sorrendbe úgy, hogy semelyik feladat se álljon a követelményei előtt.
Egy lehetséges kimenet a következő.
engedely 5 teto 3 teveantenna 13 teto ablakok 14 udvar 3 ablakok teto mosdo 16 ablakok teto teveantenna udvar kabelek 23 ablakok teto teveantenna udvar mosdo vakolat 1 ablakok
Ott az engedély bárhova kerülhet a kimenetben, mivel sem tőle nem függ semmi, sem ő nem függ semmitől. Látjuk azonban, hogy a tetőhöz tartozó sor előbb van, mint az összes olyan feladat, amin csak a tető elkészítése után kezdhetünk dolgozni.
Nézzük a ruby nyelvű megoldásomat: s2f6.rb.
@duration = Hash.new();
@depends = Hash.new();
while line = STDIN.gets();
words = line.split();
task = words[0];
@duration[task] = words[1];
@depends[task] = words[2 .. -1];
end;
@used = Hash.new();
def solve(task);
#puts "[#{task}";
if !@used[task];
@depends[task].each() {|dep|
solve(dep);
};
puts(([task, @duration[task]] + @depends[task]).join(" "));
@used[task] = true;
end;
#puts "#{task}]";
end;
@duration.each_key() {|task|
solve(task);
};
Először beolvassuk a fájlt. Az adatokat példány változókba mentjük (ezek neve kukac jellel kezdődik). Mivel nem használunk objektum-orientált programozást (nem hozunk létre új osztályokat vagy bővítünk a könyvtári osztályokat metódusokkal, hanem végig a kezdetben meglévő main objektumban dolgozunk), ezeket az egész kódból elérhetjük, mint egy globális változót.
A gets függvény beolvas egy sort a standard bemenetről, és stringként adja vissza. Ha a fájl végére ér, akkor nil-t ad vissza, aminek az igazságértéke hamisnak számít, így a while ciklus feltétele hamis, és a ciklus véget ér. (A ruby több helyen is használ nil-t valamilyen hiányzó érték jelzésére, ezt azért teheti meg kényelmesen, mert a ruby dinamikusan típusos nyelv, vagyis nem kell fordításidőben eldönteni, hogy egy kifejezés vagy változó típusa mi lesz.)
Ez után a sztringek split metódusával szavakra törjük a sort
(ez egyben levágja a sztring végéről az újsor jelet vagy bármilyen más whitespace karaktereket is).
A split egy tömböt ad vissza.
Ennek a tömbnek elmentjük az első és a második elemét,
majd a második kivételével az összes elemből egy új tömböt képezünk.
Vegyük észre, hogy ugyanaz a [] metódus az első két esetben mást csinált,
mint a harmadik esetben,
ezt szintén a dinamikus típusok miatt teheti meg:
az első esetben az argumentuma szám típusú, a második esetben pedig range típusú.
A @duration[task] értéke egy sztring lesz,
nem alakítjuk át számmá,
de ez nem is baj, mivel a hosszal ebben a feladatban nem kell dolgoznunk.
Az adatokat két asszociatív tömbbe (hash-be) mentjük le,
kulcsnak használva a feladat nevét.
Az asszociatív tömb olyan adatstruktúra,
ami értékek párjait tárolja úgy,
hogy a pár első eleme (a kulcs) alapján a párt hatékonyan vissza lehet keresni akkor is,
ha sok pár van.
Kulcsnak majdnem mindig (itt is) sztringeket használunk.
(A ruby-ban a sztringek ugyan írhatóak,
de a kulcsként használt sztring tartalmát nem szabad módosítani.
A visszakeresésnél a tárolt kulcs és a keresett kulcs tartalma számít,
tehát egy másik, pontosan ugyanazon karaktersorozatot tároló sztring objektum segítségével
is visszakereshetjük a megfelelő párt.)
Egy asszociatív tömböt a
A beolvasás után definiálunk egy solve függvényt,
ami kiír egy feladatot, de előbb kiírja az összes olyan feladatot,
aminek ennél előbb kell szerepelnie.
A függvény rekurzívan hívja meg önmagát.
Arról azonban gondoskodnunk kell, hogy egy feladatot csak egyszer írjunk ki,
ezért azokat a feladatokat, amiket már kiírtunk, kulcsként eltároljuk egy harmadik,
Emlékezzünk rá, hogy amikor egy feladatnak megfelelő sort beolvastunk,
akkor elmentettünk a
Végül kiírjuk a feladathoz tartozó sort.
Egyszerűbb lett volna, ha a bemenetben kapott sort egyben lementjük
(egy asszociatív tömbbe a feladat nevével megjelölve),
mert hiszen változatlanul kell kiírni, de ez talán tanulságosabb lesz.
A kiíráshoz egy szavakból álló tömböt hozunk létre.
Ezt úgy kapjuk, hogy először létrehozunk egy két szóból álló tömböt,
amiben a feladat neve és a napok száma szerepel,
majd ezt és a közvetlen előkövetelmények tömbjét a
Végül a fő program befejezéseként meghívjuk a solve függvényt az összes feladatra.
Próbálja ki a programot úgy, hogy letöltjük a forrását
(s2f6.rb) és egy példabemenetet (pl. s2f6be0)
majd kiadjuk a ruby -w s2f6.rb < s2f6be0 parancsot.
Íme néhány példa bemenet és kimenet.
Jegyezzük meg, hogy a kimenet csak egy lehetséges megoldást ad meg,
a bemenetekhez több helyes kimenet is tartozik ebben a mintafeladatban.
Hash.new() hívással hozunk létre.
Ha most h egy asszociatív tömb,
akkor a következő műveleteket lehet vele elvégezni.
Belerakhatunk egy (k, v) kulcs-érték párt a h[k] = v hívással
(ha már van h-ban olyan pár, aminek a kulcsa k, akkor ez előbb törlődik);
törölhetjük a k kulcsú párt a h.delete(k) hívással;
visszakereshetjük a k kulcsú párban lévő értéket a h[k] hívással
(nil-t ad, ha nincs ilyen pár);
lekérdezhetjük, van-e k kulcsú pár a h.has_key?[k] hívással;
végrehajthatunk egy blokkot az összes kulccsal,
ami h-ban szerepel a h.each_key {|k| ... } hívással,
vagy az összek kulcs-érték páron a h.each_pair {|k, v| ... } hívással.
@used nevű asszociatív tömbbe.
Ha a task nevű feladatot még nem hajtottuk végre,
akkor ebben a hash-ben nem szerepel a task string kulcsként,
ezért a @used[task] hívás nil-t ad vissza,
így az if feltétele hamis lesz.
A @used hash-ben csak a kulcsok hordoznak értékes információt,
az értékekről csak annyit használunk, hogy egyik sem hamis.
@depends hash-be a feladat nevével, mint kulccsal,
egy tömböt. Ezt a tömböt úgy kaptuk, hogy egy új tömbbe másoltuk
annak a tömbnek az első két kivételével összes elemét,
amibe a bemenet sorának szavai voltak.
Ebben a @depends[task] tömbben tehát néhány sztring szerepel,
amik a feladat előkövetelményeit nevezik meg egyenként.
Lehet, hogy a tömb üres, vagyis egy eleme sincs,
ha a feladatnak nincs előkövetelménye.
Ezeken az elemeken megyünk tehát végig a tömbök each metódusával.
Minden előkövetelményre meghívjuk a solve függvényt rekurzívan,
ez nem csak ezt az előkövetelményt, hanem az esetleges közvetett előkövetelményeket is kiírja.
+ metódussal összefűzzük
egy újabb tömbbé.
Ezután a tömbök join metódusával ebből a sztringekből álló tömbből
egy sztringet kapunk úgy, hogy minden két eleme közé az a sztring kerül,
amit a join-nak paraméterként átadunk, tehát az egy szóközből álló sztring.
Végül a puts függvény kiírja a kapott sztringet, majd kiír egy újsor jelet is.