Az I. 127. feladat (2006. március)

I. 127. Egy iskolában az egyik titkárnő feladata a tanulók részére elkészíteni a havi ebédjegyeket. Minden hónapban kap egy mintát, amit fénymásolással sokszorosít, és a másolatokat kivágja.

A titkárnő a már meglévő ebédjegyeket és a mintát egymás mellé helyezi a gépbe, hogy egyszerre többet tudjon másolni. Néhányszor lemásolja őket, majd az így készült lapokból kivágja az ebédjegyeket. A kivágott jegyeket a korábbiak mellé illeszti, és megismétli a folyamatot. (A fénymásolóra helyezhető ebédjegyek számát tekintsük korlátlannak.) Mind a másolás, mind a jegyek kivágása bizonyos időbe telik, ami nem függ a másolt vagy szétvágott jegyek számától.

Készítsünk programot, ami segít a titkárnőnek a kellő számú ebédjegy minél gyorsabb elkészítésében. A program kérdezze meg a szükséges ebédjegyek számát (a mintadarabbal együtt), a fénymásoláshoz és a vágáshoz szükséges időket. Ezekből számolja ki az ebédjegyek elkészítésének minimális idejét, és adja meg a lépéseket. A lépéseket egymás mellé írt F (fénymásolás) és K (kivágás) betűkkel kódolja.

A szükséges ebédjegyek száma legfeljebb 1000. A titkárnő nagyon takarékos, mindig pontosan a kért számú ebédjegyet készíti el, és soha sem másol a szükségesnél többet.

Példa (dőlt betűvel jelöltük a számítógép által kiírt üzeneteket):

Ebédjegyek száma:  64
Fénymásolás ideje: 1
Kivágás ideje:     8
Idő:      30
Folyamat: FFFFFFFKFFFFFFFK

Beküldendő a program forráskódja (i127.pas, i127.cpp, ...).

(10 pont)

A beküldési határidő 2006. április 18-án LEJÁRT.

Megoldás. Induljunk ki abból, hogy a titkárnő mindig a szükséges számú ebédjegyet készíti el, soha se többet, illetve hogy egyszerre az összes eddig elkészült ebédjegyet fénymásolja. Vizsgáljuk meg, mi történik néhány fénymásolás alkalmával: n db kezdeti ebédjegyből k fénymásolás után (k+1)n ebédjegy lesz. Mivel kezdetben 1 db minta-ebédjegye volt a titkárnőnek, így N, az ebédjegyek száma, a fénymásolások valamilyen szorzatával lesz egyenlő: N=1^.(k₁+1)^.(k₂+1)^....^.(k_i+1). Másképpen, két kivágás közötti fénymásolások száma +1 az N osztója kell, hogy legyen, illetve ezek szorzatának nyilván N-et kell adnia.

Ezek közül a szorzatok közül az (egyik) minimális idejűt kell meghatározni. Számítsuk ki egy ilyen fénymásolás-sorozat idejét. Jelöljük a fénymásolás idejét T_f-el, a kivágás idejét T_k-val, továbbá a kivágások közötti fénymásolások számát k_i-vel, a kivágások számát pedig n-Nel. A fénymásolás ideje így: T=T_k^.n+T_f^.(k₁+k₂+...+k_n).

Egy lehetséges algoritmus ennek a sorozatnak a meghatározására, hogy végignézzük N összes lehetséges szorzótényezős felbontását, és kiválasztjuk a legkisebb idejűt. Az összes lehetséges felbontást egy backtrack szerű algoritmussal nézhetjük végig, mindig ügyelve arra, hogy a szorzan N maradjon.

Erre látható egy Pascal nyelven írt megoldás. Az esetek végignézését egy rekurzív függvény végzi. Ez megkeresi a paraméterként megadott szám összes osztóját, az aktuálisat eltárolja egy tömbben, majd elosztja a paramétert az aktuális osztóval. Ha a hányados nagyobb 1-nél, akkor a függvény rekurzívan meghívja magát a hányados paraméterrel. Ha 1, akkor visszatér a függvény. Minden lépésben kiszámolja a tömbben lévő számok által reprezentált másolás-folyamat idejét, a legkisebb ilyet pedig eltárolja.

Letölthető Pascal program: i127.pas

Engedy István

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Balambér Dávid, Czigler András, Györök Péter, Kiss Dániel Miklós, Ozsvárt László, Vincze János.
9 pontot kapott:	Kovács 129 Péter, Szoldatics András, Véges Márton.
4 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2006. márciusi informatika feladatai