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

A KöMaL 2013. áprilisi informatika feladatai

Kérjük, ha még nem tetted meg, olvasd el a versenykiírást.


Feladat típusok elrejtése/megmutatása:


I-jelű feladatok

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


I. 319. Néhány évtizeddel ezelőtt több, különböző alapon működő hálózat létezett. Ma már a TCP/IP alapú hálózatok az egyeduralkodók. A hatékonyabb menedzselés érdekében az eszközöket alhálózatokba szervezik. Ez történhet pusztán logikai alapon is, de az alhálózatok általában fizikai szinten is elkülönülnek. Az eszközök a saját hálózatukba tartozó eszközökkel közvetlenül kommunikálnak, a többi eszközt az alapértelmezett átjárón keresztül érik el.

Ha egy eszközt TCP/IP alapú hálózatban szeretnénk használni, akkor feltétlen meg kell adnunk IP-címét (az eszköz azonosítóját), netmaskját, az alapértelmezett hálózati átjáró IP-címét (utóbbi kettő az adott alhálózatra jellemző) és a domainnevekkel történő eléréséhez a DNS szerver címét is. Ezek a címek négy 1 bájtnyi, általában decimálisan leírt, egymástól ponttal elválasztott számból állnak.

Egy alhálózat méretét (a hozzá tartozó IP-címek számát) a netmask segítségével lehet meghatározni. (A netmask bináris alakja első néhány jegyének helyén 1 áll, az azt követő jegyek mindegyike 0.) A netmask kettes számrendszerbeli alakjában meghatározzuk a 0 értékű bitek számát (k). Az ennek megfelelő méretű bináris számok száma (2k) adja meg az oda tartozó címek számát. Mivel a legelső cím a hálózat címe, a legutolsó pedig egy úgynevezett szórási cím, az alhálózatban összesen 2k-2 eszköz látható el IP-címmel.

Az alhálózat címe és a szórási cím egy eszköz IP-címe és a hozzá tartozó netmask ismeretében meghatározható. Ha képezzük a címek kettes számrendszerbeli alakját, a logikai és műveletet számjegyenként alkalmazva rájuk megkapjuk a hálózat címét. A szórási cím megadásához az IP-cím kettes számrendszerbeli alakjához a netmask egyes komplemensét kell hozzávennünk a logikai vagy művelettel.

Az ipadat.txt állományban egy nagyobb cég belső hálózatán található eszközei közül tüntettük fel néhánynak az adatait. Minden egyes sorban két adat van, egymástól pontosan egy szóközzel elválasztva, az IP-cím és a netmask.

Az ipadat.txt állomány első néhány sora:

Írjunk programot, amely megoldja az alábbi feladatokat. Az egyes feladatok megoldása előtt jelenítsünk meg a képernyőn a feladat sorszámát tartalmazó szöveget (például: 6. feladat), a beolvasás előtt pedig a beolvasás tartalmára vonatkozó üzenetet (például: Add meg a dolgozók számát!) Az ékezet nélküli kiírás is megengedett.

1. Olvassuk be és tároljuk el a honlapunkról letölthető ipadat.txt állomány adatait a későbbi feladatok megoldásához szükséges formában.

2. Jelenítsük meg a képernyőn, hogy hány IP-címet tartalmaz az állomány.

3. Készítsünk függvényt binbe néven, amely egy IP-címhez annak bináris alakját rendeli az azt alkotó számok 8 bites kettes számrendszerbeli alakjának egymás után írásával szövegként. Például: 10.32.0.17-hez a 00001010 00100000 00000000 00010001 értéket rendeli. (A szóközök csak a jobb olvashatóság miatt szerepelnek a nyomtatásban.)

4. Készítsünk függvényt binbol néven, amely egy szövegként tárolt 32 jegyű kettes számrendszerbeli számhoz a neki megfelelő IP-cím decimális alakját rendeli.

A további feladatok megoldásához használjuk az itt elkészített függvényeket közvetlenül vagy más függvényeken, eljárásokon keresztül.

5. Olvassuk be egy netmask értékét decimális formában, majd jelenítsük meg a képernyőn, hogy hány eszközt láthatunk el egy ilyen hálózatban IP-címmel. (Például a 255.255.240.0 netmaskhoz 4094 tartozik.)

6. Egy intézményben az alhálózatokat úgy alakították ki, hogy méretük a lehető legkisebb, de az IP-címmel ellátható eszközök száma az ott dolgozók számának legalább háromszorosa legyen. Olvassuk be egy osztály dolgozóinak számát, majd határozzuk meg a hálózatban használt netmask decimális alakját.

7. A bevezetőben szereplő cégnél az egyes alhálózatok utolsó felhasználható IP-címét az átjáróhoz rendelik. Jelenítsük meg a képernyőn azon sorok sorszámát egymástól szóközzel elválasztva, amelyek ilyen átjárók alhálózat oldali IP-címét tartalmazzák.

8. Készítsük el a csoport.txt állományt, amelyben az ipadat.txt fájlban található IP-címek alhálózatonkénti csoportosításban szerepeljenek. Egy-egy csoport első sora az alhálózat címe legyen. Alatta a hozzá tartozó címek soronként jelenjenek meg. Minden IP-cím sora tabulátorjellel kezdődjön.

A fenti példabemenethez tartozó kimenet:

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

Letölthető fájl: ipadat.txt

(10 pont)

megoldás, statisztika


I. 320. Barátaimmal azt a feladatot kaptuk, hogy készítsük el iskolánk rendezvényeinek jól áttekinthető weblapját a port.hu tévéműsorának mintájára. A lapon az aktuális rendezvényeken túl meg kell jeleníteni a múltbeli és a már ismert jövőbeli eseményeket is. Azt mondták, hogy a következő tartalmak előállítására van szükség:

\bullet Egy rendezvényt (műsort, előadást stb.) választva meg kell jeleníteni a címet, az időpontot (egy színdarab esetén lehet több is), a helyét, a közreműködők (előadó, szereplő stb.) nevét.

\bullet Egy helyet (például termet) választva meg kell adni az ottani rendezvények nevét, időpontját.

\bullet Egy dátum választásakor fel kell sorolni az adott napi rendezvények címét, időpontját, helyét.

\bullet Egy közreműködőt választva meg kell jeleníteni, hogy mely rendezvényeken, miként működött közre.

Az első megbeszélés során felosztottuk a munkát. Nekünk a megoldáshoz szükséges adatbázist kell megterveznünk, a teszteléshez néhány adattal feltöltenünk, valamint a fenti tartalmak előállításához szükséges lekérdezéseket SQL nyelven megalkotnunk. A feladat megoldásához a MySQL adatbázis-kezelőt kell használnunk. (A MySQL elérhető a multiplatform XAMPP csomagban is, ennek használatát javasoljuk. Itt az adatbázis-szerver a legegyszerűbben a phpmyadmin segítségével kezelhető.)

Beküldendő a megoldás rövid leírása (i320.pdf), amely tartalmazza az adatbázis modelljét (a táblák kapcsolatát) kifejező képet és a MySQL verziószámát, az adatbázis mentése (export / dump) (i320.sql), valamit a fenti lapok tartalmának előállításához szükséges SQL kérdéseket tartalmazó fájl (i320.txt).

(10 pont)

megoldás, statisztika


I. 321. A fotószolgáltatók és a digitális nyomdák különböző látványos kiadványok előállítását vállalják digitális fényképek alapján, például személyre szóló naptárak, könyvjelzők, panorámafotók készítését. Egyik érdekes termékük a fotómozaik-poszter, amelyben fotók százai állnak össze egyetlen képpé. Nagyfelbontású képen a fotómozaikot alkotó kisméretű fotók is jól láthatóak, felismerhetőek.

Készítsük el a Középiskolai Matematikai és Fizikai Lapok e havi borítójának képét fotómozaikként a lap archívumában található képek, rajzok, ábrák segítségével.

A megoldáshoz több (internetről ingyenesen letölthető) programot ajánlunk:

- AndreaMosaic v3.30 fotómozaik készítő program;

- IrfanView képnéző program, amely a képformátum - akár csoportos - módosítására is alkalmas;

- HTTrack Website Copier, amellyel weboldalakat tölthetünk le.

Honlapunkon elérhető az aktuális cimlapnagy.jpg állomány, amit fotómozaikként készítsünk el. A kép hosszanti oldala 70 és 100 cm között legyen. Az idei borítók fekete-fehér színűek, így a fekete-fehér, vonalas ábrák alkalmasak a megjelenítéshez.

Jó minőségű, nem túl sok ismétlődést tartalmazó mozaikkép előállításához legalább 200 darab kis kép szükséges, amelyeket a http://www.komal.hu/verseny/korabbi.h.shtml oldalról elérhető archívumból töltsünk le és alakítsunk át a nyersanyagtól elvárt formátumba.

Beküldendő a képállomány (i321.jpg) és egy rövid dokumentáció (i321.txt, i321.pdf, ...), amely tartalmazza vázlatosan a megoldás leírását és a használt szoftverek nevét. A képállomány maximális mérete 10 MB lehet.

cimlapnagy.jpg

(10 pont)

megoldás, statisztika


S-jelű feladatok

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


S. 80. Gombóc Artúr sokat jár barátaihoz egy N lakosú városban. Az utcák egyirányúak a városban. Gombóc Artúr nem szeret sokat gyalogolni, így azon töprengett, hogy hány olyan utca van és melyek azok, amiken végigmehet úgy, hogy saját lakásától az egyik barátjához (N-1 barátja van, hiszen mindenki a barátja) sétál el az egyik legrövidebb úton. Miután ezen gondolkozott egy keveset, úgy döntött, ideje valami nehezebb munkába fogni, és a következő kérdést tette fel: ,,Hányféleképpen juthatok el a lakásomból az egyes barátaimhoz valamelyik legrövidebb úton?''

A program olvassa be a standard input első sorából N-et és M-et (N, M\le
1\;000\;000): a lakások és az utcák számát, majd a következő M sorból a ki, vi, si szóközzel elválasztott egészeket: azaz a ki lakás kezdőpontú, vi lakás végpontú, si hosszú utcát. Gombóc Artúr lakása az 1. Írjuk a standard output első sorába az a egészet, ahol a db utca a válasz az első kérdésre, majd a következő sorba az a db utcát rendezve (a bemeneti állományban elfoglalt sorszámukkal azonosítva), növekvő sorrendben, szóközzel elválasztva. Az utolsó sorba pedig a második kérdésre válaszként minden barátjára ki kell írni, hogy hányféleképpen lehet oda valamely legrövidebb úton eljutni, illetve ennek a számnak az 1000007-es maradékát.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. Kapható részpontszám a 9 pontból, ha a program csak kisebb tesztesetekre tud lefutni időben. A programra nem jár pont, ha az első részfeladatra a bemeneteknek legalább 20%-ánál nem ad helyes kimenetet.

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

(10 pont)

megoldás, statisztika


Figyelem!

Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.