Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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 (1\len\le500) négyzet alakú terület -- a szilárd anyag függőleges metszete -- minden cellája p (0,00\lep\le1,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, 0\lena\le generálások száma). A pna 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 (1\leqn\leq500) 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