Az I. 185. feladat (2008. április)

I. 185. A lovakat abrakolni egymás mellé, egy hosszú rúdhoz kötik ki. Az etetőbe mindenféle takarmány kerül, mert a ló ínyenc állat, és ezért változatos takarmányt igényel. Ahhoz, hogy válogatni tudjanak, a kötőféket olyan lazán hagyják, hogy egy-egy ló a saját helyével szomszédos helyen álló lóval helyet tud cserélni, de messzebb már nem tud elsétálni.

Írjunk programot, amely megadja, hogy a lovak sorrendje etetés közben hányféle lehet és adjuk meg az összes lehetséges sorrendet. A program a lovak számát és nevét fájlból olvassa be, és az eredményt fájlba írja ki. A bemeneti, illetve kimeneti fájlok neve az első, illetve második parancssori argumentum legyen.

A bemenet első sorában a lovak száma (1N100), az ezt követő N sorban a rúdhoz kötés sorrendjében a lovak neve található.

A kimeneti szöveges állomány első sorában a lovak sorrendjének lehetséges száma és az azt követő ugyanennyi sorban az egyes ló-sorrendek.

Beküldendő a program forráskódja (i185.pas, i185.cpp, ...), valamint a program rövid dokumentációja (i185.txt, i185.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2008. május 15-én LEJÁRT.

A legtöbb versenyző észrevette, hogy a lehetséges sorrendek száma a Fibonacci számsorozat alapján határozható meg. A feladat megoldása visszavezethető egy speciális permutáció összes lehetséges sorrendjének előállítására. A speciális megkötés azt jelenti, hogy az eredeti sorozat egy eleme se cserélhet helyet 1-nél nagyobb távolságú másik elemmel. Ezt a szabályt figyelembe véve a legtöbb versenyző rekurzív cseremódszerrel állította elő a sorokat. Másik "klasszikus" módszer a feladat megoldására, a visszalépéses kereséssel történő előállítás. ( lovak.dpr)

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Földes Imre, Horváth 135 Loránd, Szoldatics András, Véges Márton.
6 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.

A KöMaL 2008. áprilisi informatika feladatai