Nemes Tihamér OKSzTV'91

Tekintsük az alábbi algoritmust, amelynek a bemenete egy szó, kimenete pedig a "JÓ!" vagy a "ROSSZ!" felkiáltás.

A VEREMBE és VEREMBŐL eljárások egy veremtár kezelésére szolgálnak. Az ÜRES eljárással megtudható, hogy a verem üres-e. A verem kezdetben üres.

Az OLVAS eljárás a bemenet következő betűjét olvassa be, a VANMÉG eljárás pedig megvizsgálja, hogy van-e a szónak további betűje.
 

Ha VANMÉG akkor OLVAS(betű): VEREMBE(betű) Ciklus amíg (VANMÉG és nem ÜRES)   OLVAS (betű)   VEREMBŐL(felső)   Ha (betű<>felső) akkor VEREMBE(felső): VEREMBE(betű) Ciklus vége Ha (VANMÉG vagy nem ÜRES) akkor "ROSSZ!" egyébként "JÓ!"

Mely szavakra ad "JÓ!" és melyekre "ROSSZ!" választ az algoritmus az alábbiak közül?

A. bab B. kiiktat C. odaado D. errearra E. kikerrearrakik

2. feladat: (8 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).
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}

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: (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 a 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 is ú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 diadalát, saját készítésű lyukszalagot dug el Pap Jancsi padlásán. Mi legyen ezen a szalagon, hogy a program biztosan felsüljön? (Azaz bennhagyjon legalább egy LILLA-t.)
B:
Papp 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!

5. feladat: (11 pont)

A kompatibilis programozóhoz címzett mulatóban egy játékgép áll. A gép tetején egy piros, egy zöld és egy kék lámpa van, amelyek közül mindig csak egy ég; kezdetben a piros. A gépbe "1" és "0" feliratú zsetonokat lehet bedobálni. A gépen van még egy nyomógomb, amely csak akkor nyomható meg, amikor a piros lámpa ég; ilyenkor a gép annyi forintot fizet, amennyi az a 2-es számrendszerbeli szám, amelyet az addig bedobott zsetonokon lévő számjegyek a bedobás sorrendében balról jobbra sorbaállítva kiadnak (például 1,1,0 bedobása 6 Ft-ot ér). A zsetonokat a kasszánál darabonként 10 forintért árulják. A gépbe azonban csak 9 zseton fér. Ha 9 zseton bedobása után a zöld vagy a kék lámpa ég, a pénzünk odaveszett. Só Sajó szerint az, hogy legközelebb melyik lámpa gyullad ki, csak attól függ, hogy éppen melyik lámpa ég, és hogy milyen zsetont dobtunk be. Tapasztalatait a következő táblázatban összegezte:
 

Melyik lámpa ég:		PIROS	ZÖLD	KÉK
Milyen zsetont dobtunk be:	0	piros	kék	zöld	Melyik lámpa gyullad ki:
	1	zöld	piros	kék

Serte Petra szerint a gép csak 9-cel osztható összegeket fizet ki. De Petra nem igazán ismeri a gépet, és lehet, hogy téved.

A. Kapunk-e a géptől pénzt a következő zsetonsorozatok bedobása bedobásával?

a. 1, 1, 0
b. 0, 1, 1, 1
c. 1, 0, 1, 0, 0
d. 1, 0, 1, 0, 1


B. Igaza van-e Petrának? Ha nincs, akkor mi jellemzi a játékgép által kifizetett összegeket?

C. Maximum mennyit fizet a gép egyszerre, egy játékban?

D. Legalább hány zsetont kell bedobnod ahhoz, hogy a játék nyereséges legyen? (Hiszen a zsetonok is pénzbe kerülnek.)

6. feladat: (5 pont)

Itt van egy programrészlet:
 

Függvényeljárás REJTVÉNY(A,B)   Ha A>B akkor REJTVÉNY:=-REJTVÉNY(B,A)          egyébként ha A=0 akkor REJTVÉNY:=B                           egyébként REJTVÉNY(A-1,B-1) Függvényeljárás vége.

Mit adnak eredményül a következő függvény-eljárás-hívások?

 
A. REJTVÉNY(3,12)?

B. REJTVÉNY(4,6)+REJTVÉNY(6,4)?

C. REJTVÉNY(X,Y), ahol X és Y tetszőleges nemnegatív számok?

7. feladat: (7 pont)

Egy vasúti menetrendhez a következő térkép tartozik:


Az alábbi algoritmus megvizsgálja, hogyan lehet eljutni Budapestről Nagykanizsára. Add meg, hogy milyen sorrendben írja ki az alábbi algoritmus az egyes városokat!

A sor nevű adatszerkezetnek csak a végére lehet új elemet tenni (Sorba(I)), elvenni belőle pedig csak az elejéről lehet (I:=Sorból).

A Voltunk(I) eljárással feljegyezzük, hogy az I-edik városban már voltunk a bejárás során.
 

Bejárás:   Sorba(4): Voltunk(4)   Ciklus amíg a sor nem üres és nem voltunk Nagykanizsán     I:=Sorból     Ciklus J=1-től 9-ig       Ha a J- városban még nem voltunk és van közvetlen út az I.-ből a J.-be       akkor Sorba(J):Voltunk(J)             J-edik városnév kiírása     Ciklus vége   Ciklus vége Eljárás vége.

Elérhető összpontszám: 56 pont