Feladat A kurzusra járókról tudjuk, hogy kinek mikor van elfoglaltsága. Válaszoljunk az alábbi kérdésekre: 1. Mikorra szervezhető konzultáció, azaz mikor van mindannyiuknak szabadideje? 2. Mely napokon van adott intervallumban (pl. 8-16 óra között) legalább egy kurzustagnak szabadideje? Az adatokat egy karakteres fájlból olvassuk be, a 2. feladat többlet paraméterét pedig klaviatúráról. Mielőtt nekilátna a megoldásnak, nézze meg az én megoldásomat, futtassa a mellékelt, kész OraHalmazProgram.exe programot a OraHalmaz_Keret.zip kicsomagolása után!
Megoldás Az alábbiakból is kiderül, hogy a megoldás kézenfekvően vezet az órák (pontosabban a szabad órák) alkotta halmaz adatszerkezetre. Így készítjük el az órák halmaz típusát (óra-halmaz típust).
A feladat specifikációja Be: N N, ntk Naptárak, Naptárak=Naptár*, Naptár=Halmaz(Óra)Nap, Nap=(Hétfő,...,Vasárnap), Óra=0..23
1&2. feladathoz
tól,ig Óra
2. feladathoz
Ki:
mindenki Naptár valaki Naptár
1. feladathoz 2. feladathoz
Ef:
N=Hossz(ntk)
Uf:
n Nap: ( o mindenkin
i [1..N]: o ntki,n )
1. feladat
vagyis n Nap: mindenkin= n Nap: ( o valakin
i [1..N]: o ntki,n )
vagyis n Nap: valakin=
Az ÓraHalmaz típus megadása Elvárások az ÓraHalmaz típustól – exportmodul Exportmodul TÓraHalmaz: Típus TÓra TÓraHalmaz Konstans Soha:TÓraHalmaz [üres halmaz] Mindig:TÓraHalmaz [alaphalmaz] Eljárás ReadHalmaz(Konstans kérdés:Szöveg, Változó h:TÓraHalmaz) WriteHalmaz(Konstans elő:Szöveg, h:TÓraHalmaz, utó:Szöveg) Bele(Változó h:TÓraHalmaz, Konstans o:TÓra) Függvény BenneE(Konstans h:TÓraHalmaz, o:TÓra):Logikai Elemszám(Konstans h:TÓraHalmaz):Egész
1
2. feladat
Eljárás Egyesít(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz) Metsz(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz) Kivon(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz) Operátor AzonosE(Konstans h1,h2:TÓraHalmaz):Logikai Másként h1=h2 LegyenEgyenlő(Változó mi:TÓraHalmaz, Konstans mivel:TÓraHalmaz) Másként mi:=mivel Modul vége.
Megjegyzések: 1) 2) 3)
Elnézést a „nagyképű” „Pascalizmusért”: Read/Write a művelet nevében. Didaktikai oka van: kérdés kapcsolódik majd hozzá. Operátor: kétváltozós, infix (köztes, azaz az operandusok közé illeszkedő) jelölésű eljárás vagy függvény. Az operátornak neve is van (pl. AzonosE, LegyenEgyenlő), és egy használat szintaxisát leíró szabály (pl. Másként h1=h2, Másként mi:=mivel). A név szükségességére visszatérünk, a használat szintaxisa világos.
Az ÓraHalmaz megalkotása – modul
Egy lehetséges megvalósítás lényege: a Logikai elemű tömbbel ábrázolás: Modul TÓraHalmaz: Reprezentáció Típus TÓra=0..23 TÓraHalmaz=Tömb(TÓra:Logikai) [Igaz=ráér] Konstans Soha:TÓraHalmaz(Hamis,Hamis,… 24-szer) [üres halmaz] Mindig:TÓraHalmaz(Igaz,Igaz,… 24-szer) [alaphalmaz] Változó h:TÓrahalmaz [ilyen tartozik minden egyes TÓraHalmaz típusú adathoz] Implementáció Eljárás ReadHalmaz(Konstans kérdés:Szöveg, Változó h:TÓraHalmaz): [pl. addig olvasunk szabad órák intervallumait, amíg az nem üres …] … Eljárás WriteHalmaz(Konstans elő:Szöveg, h:TÓraHalmaz, utó:Szöveg): [pl. szóközzel elválasztva a szabad órákat …] … Eljárás Bele(Változó h:TÓraHalmaz, Konstans o:TÓra): [Uf: h(o)] … Függvény BenneE(Konstans h:TÓraHalmaz, o:TÓra):Logikai [Uf: BenneE(h,e)=h(o)] … Függvény Elemszám(Konstans h:TÓraHalmaz):Egész [Uf: Elemszám(h)=Megszámolás(h,.=Igaz)] … Eljárás Egyesít(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz): […] … Eljárás Metsz(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz): […] … Eljárás Kivon(Változó új:TÓraHalmaz, Konstans h1,h2:TÓraHalmaz): […] …
2
Operátor AzonosE(Konstans h1,h2:TÓraHalmaz):Logikai Másként h1=h2 … Operátor LegyenEgyenlő(Változó mi:TÓraHalmaz, Konstans mivel:TÓraHalmaz): Másként mi:=mivel … Inicializálás h:=Soha [ez hajtódik végre minden deklarációkor a helyfoglalás után] Modul vége.
Megjegyzések: 1)
Egy típus definiálásakor a modulbeli Változó rész írja le, hogy milyen szerkezet tartozik minden egyes ilyen típusú adathoz, annak deklarálásakor. Pl. most: Változó
mind a ma-hoz, mind a holnap-hoz 24-24 logikai értékhez szükséges mennyiségű bájt Hogy minek az operátornak az „olvasható” név? Lássuk csak: hogy nézne ki az operátordefiniálás az alábbi „logikus” esetben: ma,holnap:TÓraHalmaz
2)
Operátor =(Konstans h1,h2:TÓraHalmaz):Logikai = := h1(0..23)=h2(0..23) [implicit ciklus; visszavezetés Logikai értékadásra] Operátor vége.
Ugye, milyen furcsa lenne?!? E helyett így kell definiálni:
3)
Operátor AzonosE(Konstans h1,h2:TÓraHalmaz):Logikai Másként h1=h2 AzonosE := h1(0..23)=h2(0..23) Operátor vége. Az Inicializálás részben található utasításokat hajtja végre minden egyes ilyen típusú adat helyfoglalásakor. Az 1)-beli példában a ma és a holnap létrejöttekor mindkettő Soha kezdőértéket kap.
Kódolás Készítse el a típust megvalósító unitot! Kiindulhat az OraHalmaz_Unit_Keret.pas-ból, amelyben már kész a beolvasó és kiíró művelet. Ne felejtse átnevezni OraHalmaz_Unit-ra (a programban így kell hivatkozni rá)! Mielőtt belenéz a keret-unitba, próbáljon válaszolni a következő kérdésekre: 1. 2. 3. 4. 5. 6.
Milyen részei vannak egy Pascal unitnak? Hogyan néz ki egy –mondjuk S nevű, 1..5 indextípusú, Integerekből álló– Pascal tömbkonstans deklarációja? Írjon föl egy helyes szintaxisú példát! Egy T felsorolás típus esetén mit ad meg a Low(T), High(T) függvény? Például: Low(TNap)=?, High(TNap)=? Lehet-e egy tömb indextípusa egy felsorolás típus? Hány eleme van annak a tömbnek, amelyet a TNap típussal indexelünk? Hogy kódolunk (szabályszerűen) egy beolvasást?
Készítse el az „alapfeladatot” megoldó programot ! Kiindulhat az OraHalmazProba.pas-ból. Ebben is már kész az I/O, csak a két lényegi eljárás (OsszesMetszet, OsszesEgyesites) megvalósítása hiányzik.
3
Fájlszerkezetek 1. sor: N (emberek száma) (i-1)*7+j. sor:24 jel (i=1..N, j=1..7),
ahol jel=F/.
Foglalt (=dolgozik)/Szabad; j=1 Hétfő...j=7 Vasárnap
Értelmezze az alábbi két példafájlt:
1. példabemenet (naptarak1.dat)
2. példabemenet (naptarak2.dat)
Probléma Gondolja meg, mi az ára, hogy a fenti halmazábrázolást tetszőleges elemtípusra megfogalmazhassuk! Kérdések: 1. milyen műveleteket kellene az elemtípusnak exportálnia, s ilyeneket feltéve 2. hogyan írhatnánk újra a halmaz-unitunkat úgy, hogy lehetőleg semmit ne kelljen rajta változtatni pusztán a miatt, mert megváltoztatjuk az elemtípust? Ha ezekre a kérdésekre válaszol, akkor már tudja: hogyan készíthet egy típussal paraméterezett ún. típuskonstrukciót?
Házi feladatok Hf-1 Hogyan módosítaná a halmaz típust akkor, ha egy elem bent létén túl a multiplicitása is érdekes. Ez vetődhetne föl akkor, ha a kérdés az volna, hogy mikor tartsanak 1 órás szemináriumot? Nyilván akkor, amikor a legtöbben bent tartózkodnak, azaz a 2. kérdést bővítsük ezzel! Megoldáshoz
Ez a fajta halmaz az ún. multihalmaz. A halmaz ábrázolásához használt tömb ez esetben nem logikai típusú, hanem egész. A továbbiak a fentihez hasonlóan végzendők el.
4
Hf-2 24 órához elegendő lenne 24 bit is, amíg a SizeOf(TOraHalmaz)=24 bájt. (Ellenőrizze!) Valósítsa meg a típust olcsóbban, kisebb helyfoglalás mellett. Például: a) Longint SizeOf(Longint)=4, azaz 32 bit (kicsit több ugyan, de mégsem 24 bájt!) b) 3-karakter THaromKar=Array [1..3] of Char SizeOf(THaromKar)=3 (mily meglepő: 24 bit ) Megoldásokhoz
Bitműveletek: x shl b=x balra shift (=léptetés) y bittel; x shr b=x jobbra shift y bittel. A szokásos And/Or/Not műveletek bitműveletek is. A jelölések egyszerűsítéséhez: hexadecimális konstans-írás: $ff=255, $101=256+1=257 bináris konstans-írás: %1010=8+2=10, %11111111=255
Hf-3 Nevezze át a típus I/O-műveleteit: Read-re/Write-ra! Fordítsa le! Mit tapasztal? Hogyan tehetné ismét szintaktikusan helyessé?
5
