Nemes Tihamér OKSzTV'97

Az A és B halmazok egész számokat tartalmaznak. Mindkét halmaznak van olyan eleme, amelyik a másiknak nem eleme. Használni fogjuk a következő utasításokat:
 

nemüres(H)	igaz, ha a H halmaznak legalább egy eleme van
eleme(e,H)	igaz, ha az e elem benne van a H halmazban
üreshalmaz	üres halmazt ad eredményül
egyeleme(H)	a H halmaz egy tetszőleges elemét adja eredményül
hozzáad(e,H)	az e elemet berakja a H halmazba
kivesz(e,H)	az e elemet kiveszi a H halmazból

Valami:   H:=üershalmaz   Ciklus amíg nemüres(A) vagy nemüres(B)     Ha nemüres(A) akkor e:=egyeleme(A)                   különben e:=egyeleme(B)     Ha eleme(e,A) akkor kivesz(e,A)     Ha eleme(e,B) akkor kivesz(e,B)     hozzáad(e,H)   Ciklus vége Eljárás vége.

 
A. Mit csinál a fenti program? Mi lesz a futás végén a H halmazban, mi marad A-ban és B-ben?
B. Hogyan változik a három halmaz tartalma, ha a ciklusfeltételben szereplő vagy művelet helyére és műveletet írunk?

Az alábbi LOGO programokban egyszerre két teknőc rajzol. Azonos kezdőállapotból indulnak, kelet felé, a tollak a papíron vannak. Rajzold le az általuk készített ábrákat! Add meg az egyes szögek nagyságát fokban, és nevezd meg a jellegzetes geometriai alakzatokat is.
 

A.	Teknőc1: right 90 forward 10 left 90 forward 100  right 90 forward 20 left 120 forward 60 Teknőc2: left 90 forward 10 right 90 forward 100 left 90 forward 20 right 120 forward 60
B.	Teknőc1: right 135 forward négyzetgyök 200 left 135  forward 100 right 120 forward 20 left 150  forward 20+20*négyzetgyök 3 Teknőc2: left 135 forward négyzetgyök 200 right 135 forward 100 left 120 forward 20 right 150  forward 20+20*négyzetgyök 3

Egy programozási nyelvben az elágazás (IF utasítás) végét mindig a FI, a cikluis (DO utasítás) végét pedig mindig az OD alapszó jelzi. Készítettünk egy algoritmust, amely ellenőrzi az IF-FI, illetve a DO-OD párok helyes párosítását. A megoldásban az N elemű X vektor tartalmazza a program szavait.
 

Ellenőr:    A:=0 : B:=0    Ciklus I=1-től N-ig       Elágazás          X(I)="IF" esetén A:=A+1 : V(A):=B          X(I)="DO" esetén B:=B+1          X(I)="FI" estén A:=A-1 : Ha A<0 akkor HIBA1                                   Ha V(A+1)<B akkor HIBA2                                   Ha V(A+1)>B akkor HIBA3          X(I)="OD" esetén B:=B-1 : Ha B<0 akkor HIBA4       Elágazás vége    Ciklus vége    Ha A>0 akkor HIBA5    Ha B>0 akkor HIBA6 Eljárás vége.

Milyen hibajelenségek váltják ki a HIBA1..HIBA6 hibajelző utasításokat?

4. feladat: Hőmérsékletmérések (14 pont)

Kukutyinban N napon keresztül mértük a hőmérsékletet. Az egyes napi mérések értékét az A[1..N] tömb tartalmazza.
 

Valami:   L:=hamis   Ciklus I=1-től N-ig     Ha A[I]<0 akkor        Ha nem L akkor L:=igaz : P:=I : M:=A[I]        különben Ha A[I]>M akkor P:=I : M:=A[I]     Elágazások vége   Ciklus vége Eljárás vége.

A. Mit csinál a fenti program?
B. Mi a jelentése az L, P és M változóknak?

5. feladat: Festőalgoritmus (18 pont)

A képernyőn lévő zárt alakzatok befestésére készítettük az alábbi, nem mindig jól működő algaritmust: Az alakzatot olyan festett pontok határolják, amelynek 8 szomszédja között legfeljebb két határpont van.
 

Festés:   Ciklus sor=felső-től alsó-ig     fest:=hamis     Ciklus oszlop=bal-tól jobb-ig       Ha festett(oszlop, sor) akkor fest:=nem fest       Ha fest akkor pontrajzolás(osztlop, sor)     Ciklus vége   Ciklus vége Eljárás vége.

A. Mikor "gondolja úgy a fenti festőalgoritmus, hogy zárt alakzat belsejében van?
B. A képet egyes esetekben nem jól festi. Melyek ezek?

6. feladat: Pincérek és vendégek (24 pont)

Egy étteremben, ahol K pincér dolgozik, N vendég ebédelhet egyszerre. A vendéget a Rendelés, a pincért a Kiszolgálás eljárás szimulálja. egyszerre több vendég is rendelhet, és őket több pincér szolgálhatja ki. Amikor egy pincér befejezi egy vendég kiszolgálását, azonnal hozzáfoghat a következő kiszolgálásához.

A rendeléseket (az étel nevét és a vendég sorszámát) a REND(1..N) tömbben tároljuk. A Rendelés végrehajtása 2, a Kiszolgálás végrehajtása 5 percig tart.

Például, ha egy vendég a 3. percben kezdi el tanulmányozni az étlapot, rendelését legkorábbanaz 5. percben veszi fel egy pincér. Ha ekkor éppen van szabad pincér, a vendég pontosan a 10. percben kapja meg az ételt, ha nincs, akkor várnia kell. A pincér a kiszolgálás befejezésének percében (azaz a példa szerint a 10. percben) már elkezdheti a következő vendég kiszolgálását.
 

Rendelés (ÉTEL, VENDÉG):    REND(I):=(ÉTEL, VENDÉG)    I:=(I+1) mod N : DB:=DB+1 Eljárás vége.

Kiszolgálás (ÉTEL, VENDÉG):    (ÉTEL, VENDÉG):=REND(J)    J:=(J+1) mod N : DB:=DB-1 Eljárás vége.

 
A. Milyen programozási hiba van az algoritmusban? Javítsd ki! (Új utasítást nem írhatsz bele!)
B. Mi legyen az I, J és a DB változók kezdőértéke?
C. Nézzük azt az esetet, amikor a vendégek a 6., 7., 9., 15. és 20. percben kezdik el nézegetni az étlapot, és az étteremben két pincér dolgozik. Melyik vendég mikor kapja meg az ételt a fenti algoritmus szerint?
D. A C. pontbeli adatok mellett mikor van mindkét pincérnek egyszerre munkája?

Elérhető összpontszám: 100 pont