Nemes Tihamér OKSzTV'97

1. feladat: Rekurzió (20 pont)

A TORPE(1..5) tömbben a "HAPCI" szöveg található.

 

Valami(I):   Ciklus J=1-től 5-ig     T[I]:=J     Ha I=5 akkor Print     különben Valami(I+1)   Ciklus vége Eljárás vége.

Print:   Ciklus K=1-től 5-ig     Kiír(TORPE[T[K]])   Ciklus cége   Sorvég-írás Eljárás vége.

A. Mit ír ki a program a Valami(1) eljáráshívás hatására? (A kiírás sorrendjét nem kell megadni!)
B. Mit tartalmaz a T tömb?
C. A Valami eljárás hányszor hívja meg a Print eljárást?
D. Mit ír ki a program a Valami(1) eljáráshívás hatására, ha a Valami eljárásban a ciklus magját kicseréljük:
 

Ha (J nemeleme H-nak), akkor H:=HU{J} : T[I]:=J                              Ha I=5 akkor Print különben Valami(I+1)                              H:=H-{J} Elágazás vége

Egy adatbázist hálózaton keresztül több program is használ. Ez azonban veszélyeket rejt magában. Ez azonban veszélyeket rejt magában, például az éppen olvasott adatokat felülírhatja egy másik program. Az ilyen veszélyek elkerülésére ún. primitív utasításokkal szabályozzuk az adatbázis írását és olvasását. A küld, Van és Töröl primitív utasítások jellegzetessége, hogy közülük egy időben csak egyet hajt végre az adatbázist felügyelő program. A várakozó primitív utasítások végrehajtására érkezésük sorrendjében kerül sor.

A Küld(szöveg) utasítás hatására a felügyelő program feljegyzi az adott szöveget. A Van(szöveg1, szöveg2, ...) függvény értéke igaz, ha a megadott szövegek közül legalább egyet tárol a felügyelő program. Tárolt szöveget a Töröl(szöveg) utasítással törölhetünk.

Adatbázist író és olvasó programokból tetszőlegesen sok futhat egyszerre.

A. Milyen feltételek mellett írhatják-olvashatják az adatbázist ezek a programrészletek?
B. Az író program(ok) futását az olvasó programok, ha több van belőlük, tetszőlegesen hosszú időre felfüggeszthetik. Hogyan?
C. Mit és hogyan kell megváltoztatni a fenti programrészletekben ahhoz, hogy a B. pontban említett jelenség ne következhessen be?
D. Ha a fenti író programok közül egynél több fut egyidejűleg, előfordulhat, hogy az adatbázist elrontják. Milyen esetben?

Négyjegyű telefonszámokat tárolunk az N elemű TEL vektorban, teljesen rendezetlenül. Az alábbi függvény egy telefonszámot ad eredményül:
 

Telefonszám(A,F):    DB1:=0    DB2:=0    Ciklus I=1-től N-ig       Ha TEL(I)>=A és TEL(I)<=(A+F) div 2 akkor DB1:=DB1+1       Ha TEL(I)<=F és TEL(I)>(A+F) div 2 akkor DB2:=DB2+1    Ciklus vége    Ha DB1=0 akkor Telefonszám:=A    különben Ha DB2=0 akkor Telefonszám:=F             különben Ha DB1<=DB2 akkor Telefonszám:=Telefonszám(A, (A+F) div 2)                      különben Telefonszám:=Telefonszám((A+F) div 2+1,F) Függvény vége.

A. Mi lesz a Telefonszám(1000, 9999) hívás eredménye, ha a TEL vektorban 100 darab 2-vel kezdődő telefonszám van?
B. Mi lesz a Telefonszám(1000,9999) hívás eredménye, ha a TEL vektor az összes 000-ra végződő telefonszámot tartalmazza és más számot nem?
C. Milyen tulajdonságú értéket ad eredményül a Telefonszám függvény?
D. Legfeljebb hányszor hívhatja meg saját magát a Telefonszám függvény a Telefonszám(1000,9999) hívás hatására?

Az alábbi algoritmusok az A, B, C -rendre N, M illetve P elemű- halmazok elemeiből állítják elő a D halmazt. A halmazokat tároló tömbökben az elemek növekvő sorrendben vannak, és A(N)=B(M)=C(P)
 

Első:   I:=1 : J:=1 : K:=1 : L:=0   Ciklus amíg I<=N és J<=M és K<=P     Elágazás        A(I)<B(J) esetén I:=I+1        B(J)<C(K) esetén J:=J+1        C(K)<A(I) esetén K:=K+1        egyéb esetben L:=L+1 : D(L):=A(I)                      I:=I+1 : J:=J+1 : K:=K+1     Elágazás vége   Ciklus vége Eljárás vége.

Második:   I:=1 : J:=1 : K:=1 : L:=0   Ciklus amíg I<=N és J<=M és K<=P     Elágazás       A(I)<min(B(J), C(K)) esetén L:=L+1 : D(L):=A(I) : I:=I+1       B(J)<min(C(K), A(I)) esetén L:=L+1: D(L):=B(J) : J:=J+1       C(K)<min(A(I), B(J)) esetén L:=L+1 : D(L):=C(K) : K:=K+1       egyéb esetben    (*)          Elágazás             A(I)<B(J) esetén I:=I+1 : K:=K+1             B(J)<C(K) esetén I:=I+1 : J:=J+1             C(K)<A(I) esetén J:=J+1 : K:=K+1             egyéb esetben L:=L+1 : D(L):=A(I)   (**)                           I:=I+1 : J:=J+1 : K:=K+1       Elágazás vége     Elágazás vége   Ciklus vége Eljárás vége.

A. Milyen elemek kerülnek a D halmazba az egyes eljárások végrehajtásakor?
B. Mi az első eljárásban a ciklus minimális, illetve maximális lépésszáma rögzített N, M és P mellett?
C. A második eljárásban milyen feltétel teljesülése esetén hajtható végre a külső elágazás (*)-gal, illetve a belső elágazás (**)-gal jelölt egyéb esetben ága?

Egy NxM-es térkép pontjainak magasságát 0 és 255 közötti fényességi kóddal ábrázoljuk az A mátrixban (a magasabban fekvő pontok fényesebbek). Az alábbi algoritmus a B, a C, illetve a D mátrixba e kép valamilyen transzformáltját rakja. Mely pontok lesznek az átlagosnál fényesebbek, melyek átlagosak és melyek sötétebbek a B, a C, illetve a D mátrixban tárolt képeken? (A mátrixok (1,1) koordinátájú pontja felel meg a kép bal felső sarkának.)
 

Képfeldolgozás:   Ciklus I=2-től N-1-ig     Ciklus J=2-től M-1-ig       B(I,J):=128+(A(I,J)-A(I,J-1)) div 2       C(I,J):=128+(2*A(I,J)-A(I,J-1)-A(I-1,J)) div 4       D(I,J):=128+(4*A(I,J)-A(I,J+1)-A(I+1,J)-A(I,J-1)-A(I-1,J)) div 8     Ciklus vége   Ciklus vége Eljárás vége.

 
Megjegyzés: a kiküldött feladatsorban az értékelési útmutató is szerepelt, így valószínűleg nem kerül beszémításra ez a példa.

Egymással összekapcsolt halmazokon értelmezünk műveleteket az alábbiak szerint:



Két halmaz elemei között a kapcsolatot egy vonallal jelöljük. A példában a bal oldali halmaz (Osztály) egy-egy eleméhez a jobb oldalinak (Diák) több eleme is tartozhat, a jobb oldali minden eleme a bal oldalinak pontosan egy eleméhez tartozik.

A halmazelemek jellemzőit a "/" után adjuk meg az ábrán. Jelölésük az algoritmusokban: Halmaz.jellemző (például Diák.Átlag az összes diák átlagát jelenti). Definiálhatók változók is, amelyek nem halmazhoz kapcsolódnak.

Új változót (és halmazjellemzőt) értékadással hozhatunk létre, formája:
Változó=FÜGGVÉNY Halmaznév(aritmetikai kifejezés) [logikai kifejezés]
A változó helyett halmaznév.jellemző is megadható. A logikai kifejezés (ha van) kiválogatja a halmazból a logikai kifejezést kielégítő elemeket, illetve az aritmetikai kifejezés (ha van) ebből kiszámít valamilyen értéket, és a függvényt (ha van) ezekre alkalmazzuk. A kifejezésekben hivatkozni lehet az adott halmaz saját jellemzőire, a változókra, továbbá olyan halmazok jellemzőire, amelyek adott halmaztól balra és vele összeköttetésben vannak.

Az alkalmazható függvények:

ÖSSZEG, ÁTLAG, ELEMSZÁM, MAXIMUM, VAN, NINCS, MINDEN

Példa:

Válaszolj az alábbi ábrához tartozó kérdésekre!

A. Mit adnak meg a következő képletek?
 

Mozi.X=ÖSSZEG Vetítés (Nézőszám) [Rendező.Név="Rendes Ödön"] Y=MAXIMUM Mozi (X) Mozi.Z=Mozi (X=Y)

 
B. Mit adnak meg a következő képletek?
 

Műsor.X:=ÖSSZEG Vetítés (Nézőszám) Mozi.Y=ÁTLAG Műsor (X) Film.Z=ELEMSZÁM Műsor [X>Mozi.Y]

 
C. Írj fel olyan képletet, amely filmenként megadja, hogy vetítették-e Budapesten, és egy másikat, amely megadja azokat a színészeket, akiknek minden filmjét vetítették Budapesten!

D. Írj fel olyan képletet, amely filmenként megadja, hogy van-e bennük japán szereplő, és egy másikat, amely megadja azokat a mozikat, ahol nem látható japán színész!

Elérhető összpontszám: 100 pont