Az I. 271. feladat (2011. szeptember) |
I. 271. Szilárd anyagokon folyadék átszivárgását vizsgáljuk (a jelenség neve: perkoláció). Készítsünk programot i271 néven a folyamat bemutatására. Modellünkben egy n×n-es (1n500) négyzet alakú terület -- a szilárd anyag függőleges metszete -- minden cellája p (0,00p1,00) valószínűséggel átengedi a folyadékot (például egy mikrorepedés alakul ki), és 1-p valószínűséggel pedig nem.
Az első ábrán látható anyag nem, de a másodikon látható már átengedi a folyadékokat felülről lefelé (a sötét mezők a folyadékot átengedő anyagrészek). A folyadék lehetséges mozgásiránya egy anyagcellából balra lefelé, lefelé vagy jobbra lefelé lehetséges:
Készítsünk statisztikát arról, hogy a p valószínűség függvényében hányszor volt folyadékátengedő az anyag. A négyzet n oldalhossza a megadott feltételek között tetszőleges, a statisztika készítése során rögzített. n értéke szerepeljen a dokumentációban is. Minden p értéknél legalább 100 anyaghalmazt generáljunk és számoljuk meg, hogy ebből hányszor volt átengedő az anyag (na, 0na generálások száma). A p, na számpárokat írjuk ki egy szöveges adatállományba, majd táblázatkezelő rendszerben PontXY típusú diagramon ábrázoljuk a méréseinket.
Beküldendő egy i271.zip tömörített állományban a program forráskódja (i271.pas, i271.cpp, ...), a diagramot tartalmazó táblázatkezelő állomány (i271.xls, i271.ods, ...), valamint a program rövid dokumentációja (i271.txt, i271.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ő 2011. október 10-én LEJÁRT.
Megoldásokról
A perkoláció olyan kémiai, fizikai, geológiai jelenség, amelynél az a kérdés, hogy a repedések, anyaghibák, stb. alkotnak-e összefüggő hálózatot. Szimulációs program készítése volt a feladat, amellyel tanulmányozni, lehet egy szilárd test áteresztő képességét. A szimulációban, illetve annak specifikációjában néhány fontos szabály rögzítve volt. A szilárd anyag metszetét egy n×n-es (1n500) négyzet alakú terület ábrázolta. A folyadék csak felülről lefelé, azaz három irányba terjedhetett.
A beérkezett megoldásokról:
A négyzet n oldalhossza a megadott feltételek között tetszőleges, a statisztika készítése során rögzített. A feladatmegoldók jelentős része az átjárhatóságot rekurzív útkereséssel jól oldotta meg. Látszólag ez jó módszer, de sajnos n értékének növekedésével a futási idő rohamosan nő. Gyakorlatilag mindenkinél n=50 esetén a futási idő 1 perc fölé nő. A specifikációban szándékos választása. A bemenetet többen feleslegesen ellenőrizték. Erre vonatkozó tanácsokról itt olvashattok: stdio.pdf
Egy megoldás:
Gema Barnabás 11. évfolyamos versenyző (Veszprém, Lovassy László Gimnázium) dokumentációja alapján A program először a táblázat felső sorában az átengedő cella attribútumát megváltoztatja. Ez az új attribútum azt jelenti, hogy az adott cellán folyadék folyhat át. Ezek után a következő sorokat vizsgáljuk. Minden átengedő cellánál megnézi, hogy felette található-e olyan cella, amiből a folyadék lefolyhat. Ha igen, akkor megváltoztatja a vizsgált cella attribútumát. Ez a vizsgálat lefut a táblázat minden során. Csak abban az esetben áll meg az algoritmus, ha egy sorban nincsen olyan cella, amely átengedné a folyadékot. Az utolsó sornál a program megvizsgálja, hogy van-e olyan cella, amibe eljutott a folyadék. Ha talál ilyet, akkor az átengedő anyagok számát megnöveli eggyel. i271.pas
A szimuláció elemzése:
A perkolációs hálózat összefüggőségének, a szilárd anyag áteresztőképességének vizsgálatát statisztikailag vizsgálja szimulációs programunk. A táblázat minden cellája p valószínűséggel átengedi a folyadékot. Rögzített n oldalhossz mellett statisztikailag vizsgáltuk az áteresztőképesség p-től való függését. A szilárd anyag vastagságának növelésével egyre élesebb az 50%-os valószínűségnél várható váltás.
10×10 tábla esetén
20×20 tábla
100×100 tábla
500×500 tábla
Statisztika:
14 dolgozat érkezett. 10 pontot kapott: Adrián Patrik, Gema Barnabás, Hoffmann Áron, Jákli Aida Karolina. 9 pontot kapott: Barkaszi Richárd Miklós, Fényes Balázs. 8 pontot kapott: 5 versenyző. 7 pontot kapott: 3 versenyző.
A KöMaL 2011. szeptemberi informatika feladatai