Programozás‎ > ‎Feladatok‎ > ‎Fazekas‎ > ‎

Megoldás

Algoritmusok

1. Verzió

Tegyük fel, hogy az első menetben az 1., 2., ..., i. tárgyat égetjük ki. A T égetési időre a következő becslést írhatjuk fel:
T ≥ (az első i tárgy égetési idejének maximuma) + (az (i + 1)., (i + 2)., ..., n. tárgyak optimális elrendezésének égetési ideje).

Meg kell keresnünk azt az i indexet, amire a fenti becslés a legkisebb T értéket adja. A best( i ) függvény fogja kiszámolni az i., (i + 1)., ..., n. tárgy optimális égetési idejét. Az e[] tömbben tároljuk az égetési időket. A best() függvény egy ciklusban végigpróbálja, hogy 1, 2, ..., k tárgy elhelyezése esetén milyen optimális égetési idő adódik. Vigyázni kell, hogy nagy indexek esetén kevesebb, mint k tárgy van összesen.

Best(i)
   Ha i > n akkor Best := 0
   különben
      min := -1; max := 0;
      v := i + k - 1; Ha v > n akkor v := n

      Ciklus j := i-től v-ig
         Ha e[j] > max akkor max := e[j]
         ido := max + Best(j + 1)
         Ha (ido < min) vagy (min = -1) akkor min := ido
      Ciklus vége

   best := min
   Elágazás vége
Eljárás vége

2. Verzió

A feljegyzéses módszer segítségével felgyorsíthatjuk előző megoldásunkat. A múlt órán megismert technikával dolgozunk, egy cache[]tömbben eltároljuk a már kiszámított best( i ) értékeket. Ez tényleg gyorsít az algoritmuson, hiszen a best() függvény sokszor meghívódik ugyanarra az i paraméterre.

Második lépésben most már azt is szeretnénk tudni, melyik felosztás adja az optimális égetési időt. Ha az i., (i + 1)., ..., n. tárgyak optimális égetésénél első körben az i., (i + 1)., ..., j. tárgyak kerülnek a kemencébe, akkor a choice[] tömb i. indexű eleme fogja a j értéket tárolni.

Az optimális megoldást az (1, choice[1]), (choice[1]+1, choice[choice[1]+1]), ... párok írják le.

Best(i)
   Ha cache[i] = 0 akkor
      Ha i > n akkor Best := 0
      különben
         min := -1; max := 0;
         v := i + k - 1; Ha v > n akkor v := n

         Ciklus j := i-től v-ig
            Ha e[j] > max akkor max := e[j]
            ido := max + Best(j + 1)
            Ha (ido < min) vagy (min = -1) akkor
               min := ido
               choice[i] := j
            Elágazás vége
         Ciklus vége

         cache[i] := min
      Elágazás vége
   Elágazás vége

   Best := cache[i]
Eljárás vége


Sajnos még nem tökéletes a módszerünk. Ha kiszámoljuk, mennyi memória szükséges a cache[] és choice[] tömbök tárolásához a lehetséges maximális n (10000) esetén, keserű csalódásban lesz részünk. Az égetési idő hosszú egész, a choice elemei egész típusúak kell legyenek, ezért a két tömb alapból lefoglal 60 Kbyte-ot, ami a Pascal lehetőségeinek határát súrolja. Szerencsére a choice[] értékek okosabb kódolásával (abszolút index helyett relatív index) a memóriaigény csökkenthető.

3. Verzió

Tovább tökéletesíthetjük algoritmusunkat, ha észrevesszük, hogy az előző eljárásban a best( ) függvény mindig nagyobb értékű paraméterekkel hívja meg magát rekurzívan. Tehát, ha tároljuk a már kiszámított értékeket, és a maximális indextől indulva csökkenő sorrenben számítjuk ki a best( i ) értékeket, akkor a rekurzió kiküszöbölhető, egyszerűen egy tömböt kell feltöltenünk.

A best eljárás új változata:

best(i)
   min := -1; max := 0
   v := i + k - 1;
   Ha v > n akkor v := n
   Ciklus j := i-től v-ig

      Ha e[j] > max akkor max := e[j]
      ido := max + cache[i+1]
      Ha (ido < min) vagy (min = -1) akkor
         min := ido
         choice[i] := j;
      Elágazás vége
   Ciklus vége
   cache[i] := min;
Eljárás vége

A főprogram:
cache[n + 1] := 0
Cikus j := N-től 1-ig
   best(j)
Ciklus vége

Ki: cache[1]

j := 1
Ki: j, choice[j]
Ciklus amíg choice[j] < n
   j := choice[j]+1
   Ki: j, choice[j]
Ciklus vége

Megoldások

Erben Péter (Delphi): ep_fazekas.dpr
Fehér Gábor (Delphi, rekurzióval): fg_fazekasr.dpr
Fehér Gábor (Delphi, rekurzió nélkül): fg_fazekasd.dpr
Mészáros Balázs (C): mb_fazekas.c