Házi feladat

3100 tábori foglalkozások

Általános leírás

Törekedj arra, hogy szép, áttekinthető kódot írj! Úgy oldd meg a feladatokat, hogy függvényeket használsz a megoldáshoz! A felhasznált függvényekben ne történjen konzolra való kiírás!

Mindegyik feladatban nagyon fontos, hogy bár hat inputfájlt kapsz, úgy írd meg a programod, hogy bármilyen, a feladatkiírásnak megfelelő bemeneti fájlegyüttessel működjön!

3.100-T Tábori foglalkozások

Egy nyári táborban hatféle foglalkozás közül választhatnak a diákok: fizika, matematika, csillagászat, robotika, web és 3D. Minden diák pontosan két vagy három különböző foglalkozást jelöl meg. A foglalkozásokat két vagy három külön helyiségben, több idősávban szeretnék megtartani. A szervezők ezért szeretnék látni, mely foglalkozások résztvevői között nagy az átfedés, mely névsorok tartalmaznak más névsorokat, és mely foglalkozáspároknak nincs közös jelentkezőjük.

A feladatban a jelentkezéseket kell összehasonlítanod; konkrét órarendet és terembeosztást nem kell készítened. Közös jelentkezőkkel rendelkező foglalkozások egyidejű megtartása ütközést okozna a diákoknak.

Bemeneti fájlok

A hat UTF-8 kódolású fájl egy-egy foglalkozás jelentkezőinek névsorát tartalmazza:

Mindegyik fájl első sora fejléc, a további sorok egy-egy jelentkezés időpontját és a diák teljes nevét tartalmazzák, pontosvesszővel elválasztva. A mezők nincsenek idézőjelezve. A nevek nem tartalmaznak pontosvesszőt vagy sortörést.

Jelentkezes;Nev
2027-01-12 09:14:26;Zafírparti Aurél
2027-02-03 16:08:51;Aranyligeti Izolda

A fenti két sor csak formátumminta. A dátumok formátuma éééé-HH-nn ÓÓ:pp:mm. Az időpontok 2027. január 1. 00:00:00 és 2027. június 30. 23:59:59 közé esnek. Az időpontokat DateTime típusú értékként tárold és hasonlítsd össze!

Egy diák egyszer küldi be a választásait. Az összes általa választott foglalkozás fájljában ugyanazzal a teljes névvel és ugyanazzal a jelentkezési időponttal szerepel. Két különböző diáknak nincs azonos jelentkezési időpontja: az időpont tehát egyértelműen azonosítja a diákot. Az egyezést az időpont alapján vizsgáld, ne a név alapján! Különböző diákok neve elvileg megegyezhet, ekkor is külön személynek számítanak.

A fájlok már a jelentkezési időpont szerint, szigorúan növekvő sorrendben rendezettek, nem pedig ábécérendben! Egy fájlban ugyanaz a diák legfeljebb egyszer szerepel. Minden diák pontosan két vagy három fájlban található meg. A mellékelt adatok összesen 40 különböző diák választásait tartalmazzák, de a programod más létszámmal is működjön! Egy foglalkozás fájlja akár csak a fejlécet is tartalmazhatja.

Elvárt működés és futási idő

Két foglalkozás jelentkezőlistáját mindig a rendezettségüket kihasználva, két mutatóval dolgozd fel! Az egyik mutató az első lista, a másik a második lista aktuális elemét jelöli. A mutatók csak előre haladhatnak; a listák elejéről ne indulj újra.

Egy kétlistás művelet futási ideje legfeljebb O(n + m) legyen, ahol n és m a két bemeneti lista hossza. A kiíráshoz szükséges bejárás megengedett. A lineáris követelmény a művelet egészére vonatkozik: ne rendezd újra a listákat, ne keress minden diákra külön a másik teljes listában, és ne végezz külön bináris keresést minden elemhez! Ne váltsd ki a kétmutatós feldolgozást kész halmazműveletekkel vagy hash-alapú adatszerkezettel!

Készíts újra felhasználható függvényeket a műveletekhez! Egy listát visszaadó függvény teljes rekordokat adjon vissza: az időpontot és a nevet együtt. A bemeneti listákat ne módosítsd! A függvényeken belül ne történjen konzolra való kiírás.

Minden részfeladat előtt írd ki a sorszámát! Minden eredménylistánál írd ki a létszámot, majd soronként a jelentkezési időpontot és a teljes nevet, a jelentkezés időrendjében, pontosvesszővel elválasztva! Az eredményeket sem kell név szerint rendezni. Üres eredménynél írd ki, hogy nincs ilyen jelentkező!

Beolvasás

  1. Olvasd be a hat névsort! Írd ki foglalkozásonként a jelentkezők számát! Ugyanaz a diák több foglalkozás létszámába is beleszámít, ezért ezek összege nem a táborozók száma.

Metszet – mindkét foglalkozást választók

A metszetbe azok a diákok tartoznak, akik mindkét vizsgált foglalkozást megjelölték. Minden közös diák pontosan egyszer szerepeljen! Készíts függvényt két rendezett lista metszetének meghatározására, majd használd az alábbi feladatokhoz!

  1. Kik választották a matematikát és a robotikát is?
  2. Kik választották a fizikát és a csillagászatot is?
  3. Kik választották a csillagászatot és a webet is?

Különbség – az első foglalkozást igen, a másodikat nem választók

Az A és B lista különbségébe azok tartoznak, akik A-ban szerepelnek, B-ben viszont nem. A sorrend számít: A különbség B általában nem ugyanaz, mint B különbség A. Készíts függvényt két rendezett lista különbségének meghatározására!

  1. Kik választották a fizikát, de a csillagászatot nem?
  2. Kik választották a csillagászatot, de a fizikát nem?
  3. Kik választották a robotikát, de a matematikát nem?

Unió – legalább az egyik foglalkozást választók

Az unióba azok tartoznak, akik a két foglalkozás közül legalább az egyiket megjelölték. Aki mindkettőt választotta, az is csak egyszer szerepeljen! Készíts függvényt két rendezett lista uniójának meghatározására!

  1. Kik választottak fizikát vagy csillagászatot, esetleg mindkettőt?
  2. Kik választottak matematikát vagy robotikát, esetleg mindkettőt?
  3. Kik választottak csillagászatot vagy webet, esetleg mindkettőt?

Szimmetrikus különbség – pontosan az egyik foglalkozást választók

Ide azok tartoznak, akik a vizsgált két foglalkozás közül pontosan az egyiket jelölték meg. A mindkettőt választók kimaradnak. A diák egy harmadik foglalkozást ettől még választhatott. Készíts függvényt e lista meghatározására! Megoldhatod közvetlenül két mutatóval, vagy a korábbi függvények felhasználásával, ha a teljes művelet így is lineáris marad.

  1. Kik választották a matematika és a robotika közül pontosan az egyiket?
  2. Kik választották a fizika és a csillagászat közül pontosan az egyiket?
  3. Kik választották a csillagászat és a web közül pontosan az egyiket?

Tartalmazás – az első csoport minden tagja szerepel-e a másodikban?

Az A jelentkezőlistája részhalmaza B jelentkezőlistájának, ha minden A-t választó diák B-t is választott. Az egyenlő listák is részhalmazai egymásnak. Üres lista bármely lista részhalmaza. Készíts logikai értéket visszaadó függvényt két rendezett lista részhalmazviszonyának eldöntésére! A következő kérdésekre „igen” vagy „nem” választ írj ki!

  1. Igaz-e, hogy minden csillagászatra jelentkező diák fizikára is jelentkezett?
  2. Igaz-e, hogy minden fizikára jelentkező diák csillagászatra is jelentkezett?
  3. Igaz-e, hogy minden webre jelentkező diák 3D-re is jelentkezett?

Diszjunktság – nincs-e közös jelentkező?

Két jelentkezőlista diszjunkt, ha nincs olyan diák, aki mindkettőben szerepel. Ez azt jelenti, hogy e két foglalkozás között a diákok választásai alapján nincs résztvevői ütközés. Üres lista bármely listával diszjunkt. Készíts logikai értéket visszaadó függvényt, amely ezt a két rendezett listáról eldönti! A következő kérdésekre „igen” vagy „nem” választ írj ki!

  1. Diszjunkt-e a csillagászat és a web jelentkezőlistája?
  2. Diszjunkt-e a fizika és a 3D jelentkezőlistája?
  3. Diszjunkt-e a matematika és a robotika jelentkezőlistája?

Mire figyelj a kétmutatós feldolgozásnál?

Az időpontok összehasonlítása háromféle eredményt adhat: az első kisebb, a második kisebb, vagy a kettő azonos. Azonos időpont esetén ugyanarról a diákról van szó. Ha az egyik mutató a lista végére ért, gondold végig, mi legyen a másik lista megmaradt elemeivel! Ez műveletenként eltérhet. A függvényeid üres listákkal is helyesen működjenek!