Programozás‎ > ‎Feladatok‎ > ‎Kemence‎ > ‎

Megoldás

Algoritmus

Ez a feladat nagyon hasonlít Fazekas feladathoz. A következőkben megnézzük, hogy a Fazekas feladat megoldását hogyan lehet átalakítani a Kemence feladat megoldásához... A megoldásban csak a Best() függvénynek azt a ciklusát kell megváltoztatni, amelyik végigpróbálgatja, hogy hány tárgy kerüljön be a következő körben a kemencébe. Ez az előző feladatnál K darab volt, itt viszont számolni kell a bekerült tárgyak tömegét, és akkor kell megszakítani a ciklust, amikor a következő tárggyal már K fölé nőne az össztömeg.

Memória korlátok

Legfeljebb 10.000 darab tárgy lehet. Az égetési idő 1 byte, a súly 2 byte, a choice[] tömb tárgyanként 2 byte, mert legfeljebb 1000 tárgy kerülhet egyszerre a kemencébe. A cache[] tömb egy elemének pedig tudnia kell tárolni a lehető leghosszabb égetési időt, ami (K = 1, minden égetési idő = 100, minden tömeg = 1 esetén) legfeljebb 1,000,000 azaz 4 byte. Ez összesen legfeljebb (1+2+2+4)x10,000 = 90,000 byte, ez sajnos nem fér bele a Turbo és Borland Pascal 64 kilobájtjába.

A legegyszerűbb megoldás erre az lehet, hogy meghívunk egy eljárást, és annak egy helyi változója az egyik tömb, így az az adat a 64 kbyte-os stack-re kerül. (Ekkor viszont már a rekurzióra valószínűleg nem lesz elég hely.)

Megjegyzés

Egy bonyolultabb megoldás lehet a cache[] tömb kiküszöbölése a choice[] tömb segítségével. A choice[] tömb kitöltött része ugyanis tartalmazza azt az információt, hogy egy adott i indextőtl kezdve milyen csoportosításban kell betenni a tárgyakat az optimális időhöz, de ebből már megkapható az optimális idő, azaz cache[i]. Ezzel a futási időt legfeljebb N-szeresére növeljük, mert a choice[] tömb is legfeljebb N elemű. Ezt mi nem próbáltuk ki...

Megoldások

Fehér Gábor (Delphi): fg_kemence.dpr
Fehér Gábor (Pascal): fg_kem.pas
Mészáros Balázs (C): mb_kem.c