Nemes Tihamér OKSzTV'91

1. feladat: (12 pont)

Az alábbi két függvényeljárás (nyissz és nyassz) rudakat darabol. A rudak hosszát a rúd tömbben tároljuk, amelynek a rudak számánál eggyel több eleme van. A tömb utolsó eleme az úgynevezett strázsa, amelyben -1 van. A két függvényeljárás bemenő paramétereként azt kellene megadni, hogy mekkora rúddarabot akarunk levágni.
 

VAR rúd: ARRAY [1..Maxrúd] OF INTEGER; FUNCTION nyissz(h:INTEGER) : INTEGER;   VAR p : INTEGER; BEGIN   p:=1;   WHILE (rúd[p+1]<>-1) AND (rúd[p]<h) DO p:=p+1;   IF rúd[p]<h   THEN nyissz:=0   ELSE BEGIN nyissz:=p; rúd[p]:=rúd[p]-h END END {nyissz}; FUNCTION nyassz(h:INTEGER):INTEGER;   VAR p, q, m : INTEGER; BEGIN   p:=1; q:=0; m:=MAXINT;   WHILE (rúd[p]<>-1) DO BEGIN     IF (rúd[p]-h>=0) AND (rúd[p]-h<m)     THEN BEGIN m:=rúd[p]-h; q:=p END;     p:=p+1   END;   IF q<>0 THEN rúd[q]:=m;   nyassz:=q END {nyassz};

A.

Hogyan alakul a tömb tartalma, és milyen értéket adnak vissza az egyes függvényeljárások, ha kezdetben a tömbben [3, 5, 2, 4, 7, -1] van, és a 3, 4, 2, 2 paraméterekkel hívjuk meg mind a nyissz, mind a nyassz eljárást, külön-külön, a megadott sorrendben?

B.

A [2, 1, -1] tömbhöz adj meg olyan rúdigénylést, amelyre a nyissz függvényeljárás 0-t fog valamikor visszaadni, a nyassz pedig soha. (Ha nincs ilyen, válaszodat akkor is indokold meg!)

C.

A [3, 2, -1] tömbhöz  adj meg olyan rúdigénylést, amelyre a nyassz függvényeljárás fog valamikor 0-t visszaadni, a nyissz pedig soha. (Ha nincs ilyen, válaszodat akkor is indokold meg!)

2. feladat: (10 pont)
 

Furcsa számítógépünk a következő formában várja tőlünk a programot. Először meg kell adni az alapismereteket. Másodszor föl kell sorolni azokat a következtetési szabályokat, amelyek alkalmazásával a problémát megoldhatónak gondoljuk.
Alapismeretek például:
1. anyja (Szilágyi Erzsébet, Mátyás).
  Ez azt jelenti, hogy Szilágyi Erzsébet anyja Mátyásnak.
2. apja (Hunyadi János, Mátyás).
  Ez azt jelenti, hogy Hunyadi János apja Mátyásnak.
Szabályok például:
1. szülője(x,y) HA anyja(x,y) VAGY apja(x,y).
2. nagyszülője(x,y) HA szülője(x,z) ÉS szülője(z,y).
Ez magyarul a következőt jelenti: akkor nagyszülője x y-nak, ha van olyan z személy, akinek x a szülője és ő (azaz z) szülője y-nak.
A logikai kifejezéseket balról jobbra haladva értékeli ki a gép. A kiértékelést abbahagyja, ha a részeredmény alapján már eldönthető a teljes kifejezés értéke.
A:

Milyen rokonsági kapcsolatot határoznak meg a következő szabályok?
a. rokon1(x,y) HA szülője(z,x) ÉS szülője(z,y) ÉS x<>y.
b. rokon2(x,y) HA apja(x,z) ÉS szülője(z,y).
c. rokon3(x,y) HA szülője(x,y) VAGY (szülője(x,z) és rokon3(z,y))

B:

Írd meg a következő rokoni kapcsolatokat leíró szabályokat!
a. anyaiNagyszülője(x,y) HA ... {azaz x anyai nagyszülője y-nak}
b. szülőpár(x,y) HA ... {azaz akiknek közös gyermekük van}
c. leszármazottja(x,y) HA ... {azaz x leszármazottja y-nak}

3. feladat: (8 pont)

Egy palacsintasütő és egy palacsintaevő ember számára készítettünk egy-egy algoritmust. Úgy tervezzük, hogy a két két ember ezeket az algoritmusokat egyszerre -azaz egymással párhuzamosan- hajtja végre. Egy közös tárolót (tányért) használnak, amelyen egyszerre csak egy palacsinta fér el. Egymással nem beszélhetnek, csupán egy-egy, a vasútállomásokon alkalmazottakhoz hasonló szemaforral jelezhetnek egymásnak. Ehhez a következő utasításokat használhatják fel:
 

jelezz(SZ):	szabadra állítja az SZ szemafort
várj(SZ):	várakozik, amíg az SZ szemafor nem szabadot jelez, majd ismét tilosra állítja, és abbahagyja a várakozást

Sütő:   Ciklus     Süss egy palacsintát!     Várj(ÜRES A TÁNYÉR)     Tedd a palacsintát a tányérra!     Jelezz(EHETSZ)   Ciklus vége Eljárás vége

Evő:   Jelezz(ÜRES A TÁNYÉR)   Ciklus     *   Ciklus vége Eljárás vége

A * helyébe négy utasítást teszünk, különféle sorrendben.

Add meg, hogy mely megoldások hibásak és miért! Ha több helyes megoldás is van, vizsgáld meg, hogy melyik mennyire hatékony!
 

A:   Várj(EHETSZ)   Vedd fel a palacsintát!   Jelezz(ÜRES A TÁNYÉR)   Edd meg!	B:   Vedd fel a palacsintát!   Várj(EHETSZ)   Jelezz(ÜRES A TÁNYÉR)   Edd meg!
C:   Várj(EHETSZ)   Jelezz(ÜRES A TÁNYÉR)   Vedd fel a palacsintát!   Edd meg!	D:   Várj(EHETSZ)   Vedd fel a palacsintát!   Edd meg!   Jelezz(ÜRES A TÁNYÉR)

4. feladat: (15 pont)

A következ? két rendez? eljáráshoz írj olyan állításokat, amelyek a megjelölt helyeken érvényesek, és a rendezend? vektorra vonatkozó minden lényeges információt tartalmaznak!
 

Rendezés:   Ciklus I=1-t?l N-1-ig   {A. állítás}     M:=I     Ciklus J=I+1-t?l N-ig     {B. állítás}       Ha A(M)>A(J) akkor M:=J     Ciklus vége     Csere(A(I), A(M))   Ciklus vége Eljárás vége

Rendezés:   Ciklus I=2-t?l N-ig   {C. állítás}     J:=I-1     Ciklus amíg J>0 és A(J)>A(J+1)     {D. állítás}       Csere(A(J), A(J+1)) : J:=J-1     Ciklus vége   Ciklus vége Eljárás vége.

5. feladat: (12 pont)

Adott az alábbi Pascal-nyelvű függvényeljárás:
 

FUNCTION hash(v: INTEGER): INTEGER;   VAR h: INTEGER; BEGIN   h:=0;   WHILE v<>0 DO BEGIN h:=h+v MOD 10; v:=v DIV 10 END;   hash:=h MOD Max END {hash};

A hash függvényt a következő eljárás használja:
 

PROCEDURE insert(v: INTEGER);   VAR place, n : INTEGER; BEGIN   palce:=hash(v); n:=0;   WHILE (n<Max) AND (memo[place]>=0) DO BEGIN     place:=(place+1) MOD Max;     n:=n+1   END;   IF memo[place]<0 THEN memo[place]:=v END;

A VAR memo: ARRAY[0..Max-1] OF INTEGER (globális) tömb minden elemének kezdetben -1 az értéke.
Mi lesz a memo tömb tartalma az alábbi insert-sorozatok adott sorrendű végrehajtása után, a Max állandó adott értéke mellett?
 

A. CONST Max=7; insert(2); insert(26); insert(117); insert(8); insert(18)

 

B. CONST Max=11; insert(2); insert(26); insert(117); insert(8); insert(18); insert(14); insert(13)

 

6. feladat: (12 pont)

Egy adatátviteli rendszerben két számítógép között soros vonalon, négybites csomagokban továbbítják az információt. Mivel az átviteli csatorna nem tökéletes, kb. minden 50. átküldött bit megsérül. Annak azonban elenyésző a valószínűsége, hogy egymáshoz ennél közelebb lévő bitek sérüljenek meg. Ezért minden négybites csomagot 7 biten kódolva küldenek át. Így ha a 7 bitből csak egy sérül meg, akkor az eredetileg átküldött adat visszaállítható. Ha több bit sérül meg egyszerre, akkor az alábbi algoritmus nem működik helyesen. (A XOR bitenkénti KIZÁRÓ VAGY művelet.)
A következő programrészlet a vevő oldalon a dekódolás folyamatát látja el. Bemenete a csat hételemű tömb, amely a csatornán érkezett és ugyanabba a a csomagba tartozó biteket tartalmazza. Kimenetként az üzen négyelemű tömbben helyreállítja az eredeti üzenet 4 bitjét.
 

i:=0 IF (csat[1] XOR csat[3] XOR csat[5] XOR csat[7])=1 THEN i:=i+1; IF (csat[2] XOR csat[3] XOR csat[6] XOR csat[7])=1 THEN i:=i+2; IF (csat[4] XOR csat[5] XOR csat[6] XOR csat[7])=1 THEN i:=i+4; IF i>0 THEN csat[i]:=NOT(csat[i]); üzen[1]:=csat[3]; üzen[2]:=csat[5]; üzen[3]:=csat[6]; üzen[4]:=csat[7];

A következő programrészlet az adóoldalon a kódolás feladatát látja el. Értelemszerűen az előző eljárás fordítottját végzi. Néhány szám azonban hiányzik belőle. Ezeket *-gal helyettesítettük.
 

csat[3]:=üzen[1]; csat[5]:=üzen[2]; csat[6]:=üzen[3]; csat[7]:=üzen[4]; csat[1]:=csat[*] XOR csat[*] XOR csat[*]; csat[2]:=csat[*] XOR csat[*] XOR csat[*]; csat[4]:=csat[*] XOR csat[*] XOR csat[*];

Milyen értéket vehet fel, és mit fejez ki i hibátlan átvitel, illetve egyszeres hiba esetén? Add meg a *-gal helyettesített számokat a programban való előfordulásuk sorrendjében!

7. feladat: (12 pont)

Pap Jancsi fogad Tasziló barátjával, hogy a padláson heverő lyukszalagok egyikén sem fordul elő a "LILLA" szó. De hogy biztos legyen a dolgában, programot ír a lyukszalagok átalakítására.
Az alábbi BASIC nyelvű programban az OLVAS(K$) parancs az 1-es számú lyukszalag következő karakterét olvassa be K$-ba, az ÍR(L$) parancs pedig a 2-es számú lyukszalagra írja ki az L$ tartalmát. A szalagok végét a "$" jel jelzi. (Mivel Pap Jancsi még nem nagyon tud programozni, programja hibajelzéssel fog leállni a szalag végén.)
Pap Jancsi minden szalagot átmásol a programmal,  majd a már átalakított szalagokat újra meg újra átfuttatja, amíg csak változást tapasztal. Végül minden szalag eredetije helyett annak utolsó változatát rakja vissza a padlásra.
 

10 OLVAS(K$) 15 IF K$<>"L" THEN ÍR(K$): GOTO 10 ELSE OLVAS(K$) 20 IF K$<>"I" THEN ÍR("L"): GOTO 15 ELSE OLVAS(K$) 30 IF K$<>"L" THEN ÍR("LI"): GOTO 15 ELSE OLVAS(K$) 40 IF K$<>"L" THEN ÍR("LIL"): GOTO 15 ELSE OLVAS(K$) 50 IF K$<>"A" THEN ÍR("LILL"): GOTO 15 ELSE GOTO 10 60 END

Tasziló, aki megneszelte a turpisságot, már előre dörzsöli a kezét. Jogosan, mert a program valóban rossz.
A:
Tasziló, hogy nyilvánvalóvá tegye a diadalát, saját készítésű lyukszalagot dug el Pap Jancsi padlásán. Mi legyen a szalagon, hogy a program biztosan felsüljön? (Azaz bennhagyjon legalább egy LILLÁt.)
B:
Pap Jancsi közben maga is rájön a hibára, és kijavítja a programot. Két sorban végez apró módosítást, a többi soron nem változtat, és új sort sem szúr be. Add meg ezt a két sort kijavítva!

8. feladat: (13 pont)

A Folttisztító Turbo-Pascal eljárás a grafikus képernyőn lévő és a háttértől elütő színű alakzat pontjait festi át háttérszínűre, bizonyos rendszer szerint. A felhasznált grafikus utasítások és függvények:
 

GetPixel(x,y)	az (x,y) koordinátájú pont színét adja vissza
GetBkColor	a háttér színét adja vissza
PutPixel(x,y,szín)	az (x,y) pontot szín színűre festi

(Megjegyzés: az origó a bal felső sarokban van, x vízszintes, y függőleges elmozdulást jelent.)
 

PROCEDURE FoltTisztito(x,y: INTEGER);   VAR x1, y1, d, n : INTEGER; BEGIN   x1:=x; y1:=y; d:=1; n:=0;   REPEAT     CASE d OF       1: BEGIN x1:=x+1; y1:=y   END;       2: BEGIN X1:=x;   y1:=y+1 END;       3: BEGIN x1:=x-1; y1:=y   END;       4: BEGIN x1:=x;   y1:=y-1 END;     END {CASE};     IF (GetPixel(x1,y1)<>GetBkColor) THEN BEGIN       PutPixel(x,y,GetBkColor); n:=0; x:=x1; y:=y1; d:=(d+2) MOD 4+1     END     ELSE BEGIN d:=d MOD 4+1; n:=n+1 END   UNTIL n=4 END {FoltTisztito};

A.

Mi a d változó szerepe, és mit jelentenek egyes értékei?

B.

A képernyőn a következő, a háttétől elütő színű alakzat helyezkedik el. (Egy-egy mező egy-egy képernyőpontot jelent.) Sorszámozd be a program által "kitisztított" pontokat a tisztítás sorrendjében, az a, b, c és d betűkkel megjelölt, négy különböző kiindulási mező esetén! (Mind a négy esetre rajzolj egy-egy ábrát!)

	a
		b
			c
				d