Az S. 63. feladat (2011. május)

S. 63. Makromolekulák (például proteinek) szerkezetét erősen leegyszerűsített formában vonzó- (V) és közömbös- (K) részek sorozatával írhatjuk le.

Például: KVVKVVVKVVKV

A vonzó-részek egymás mellé kerülése a térszerkezet kialakulásakor kedvező. A molekula szerkezetét karakterláncként írhatjuk le, amely modellünkben két dimenzióban feltekeredhet. A V-részek leginkább a molekulaszerkezet belsejében halmozódnak fel és a K-részek kívül.

Az ábrán jelöltük a molekulaszerkezet tekeredését és a VV elemek kapcsolatát. A természetben az a szerkezet kedvező stabilitású, amelynél több VV kapcsolat jön létre. A második szerkezetben 9, míg az elsőben csak 6 kapcsolat jött létre.

Készítsünk programot S63 néven, amely meghatározza egy adott makromolekula legstabilabb szerkezetét.

A program a makromolekula szerkezetét fájlból olvassa be. Az eredményt, a molekula síkbeli alakját, amely a maximális számú VV kapcsolatot tartalmazza (ha több ilyen van, akkor elegendő egyet), a kapcsolatok számát és a molekula kapcsolódási sorrendjét a képernyőn jelenítjük meg. A program egyetlen parancssori argumentuma a bemeneti fájl legyen.

A bemenet egyetlen sora V és K karaktereket tartalmaz (maximum 20-at).

Beküldendő a program forráskódja (s63.pas, s63.cpp, ...) az .exe és más fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s63.txt, s63.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás melyik fejlesztő környezetben fordítható egy tömörített s63.zip állományban.

(10 pont)

A beküldési határidő 2011. június 10-én LEJÁRT.

Megoldásokról

Négy megoldás érkezett, de a beküldöttek jól sikerültek.

Mintamegoldás

Borsos Zalán 12. osztályos tanuló (Marosvásárhely, Bolyai Farkas Elméleti Líceum) munkája alapján.

Az algoritmus a visszalépéses keresés segítségével a molekula összes lehetséges térszerkezetét generálja, majd ezek közül kiválasztja azt, amelyik a legtöbb kapcsolatot tartalmazza. A futási időt lényegesen javító észrevétel az, hogy a molekula első két alkotóelemének helyzetét tekinthetjük rögzítettnek, hiszen az így kapott szerkezetekből az összes többi forgatással megkapható, és a kapcsolatok száma nem változik. A komplexitás: exponenciális. A program kódja: s63.cpp

Tesztállományok: 1.txt, 2.txt, 3.txt, 4.txt és 5.txt.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Borsos 607 Zalán, Szabó 928 Attila.
9 pontot kapott:	Fekete 976 János, Nagy 111 Miklós.

A KöMaL 2011. májusi informatika feladatai