Nemes Tihamér OKSzTV'92

1. feladat: (10 pont)

D. E. Knuth: A számítógépprogramozás művészete című könyvében J. Stein alábbi algoritmusát közli:
"A program bemenő adatai az U és V természetes számok.

B1. Legyen k:=0, majd ismételten k:=k+1, U:=U/2, V:=V/2, egyszer vagy többször, esetleg egyszer sem, mindaddig, amíg már U és V nem mindketten párosak.

B2. Ha U páratlan, legyen T:= -V és menjünk B4-re. Egyébként legyen T:=U

B3. Legyen T.=T/2.

B4. Ha T páros, menjünk vissza B3-ra.

B5. Ha T>0, legyen U:=T, egyébként legyen V:= -T

B6. Legyen T:=U-V! Ha T<>0, menjünk vissza B3-ra. Egyébként az algoritmus véget ér, az output U*2^K."
 

A. Mi lesz a program eredménye a (15,20), (24,28), (54,60) számpárokra?

B. Milyen feladatot old meg a program?

2. feladat: (13 pont)

Az alábbi programrészlet az A$ változó alapján állít elő egy szöveget a B$-ban. A$ csak nyomtatható karaktereket tartalmazhat!

A programrészletben használt utasítások jelentése a következő:

 

1000 S=1 : B$=LEFT$(A$,1) 1010 IF B$=A$ THEN 1200 1020 FOR I=2 TO LEN(A$) 1030 IF RIGHT$(B$,1)=MID$(A$,I,1) THEN S=S+1 : GOTO 1090 1040 IF S>2 THEN B$=B$+CHR$(0)+CHR$(S) 1050 IF S=2 THEN B$=B$+RIGHT$(B$,1) 1060 B$=B$+MID$(A$,I,1) : S=1 1090 NEXT 1200 ..

A. Mi lesz B$-ban az 1200-as sorban, ha A$ tartalma kezdetben

A1. "Ipafai fapipa"
A2. "Ezüsttel befuttatott."
A3. "13333333-szor ismételd meg."
A4. "Gyakorisága 888888"
B. Fogalmazd meg tömören, mit csinál a fenti program!

C. Milyen esetekben nem lehet előállítani B$-ból A$ értékét?

D. Egészítsd ki a programot két új sorral (1100 és 1110) úgy, hogy B$-ból A$ mindig előállítható legyen!

3. feladat: (13 pont)

A következő programrészlet bemenete az A(N) vektor, értékei 0 és M-1 közötti egész számok.

A. Mit tartalmaz a megoldásban a B vektor a (*) ponton?

B. Mit tartalmaz a megoldásban a B vektor a (**) ponton?

C. Mit tartalmaz a megoldásban a B és a C vektor a (***) ponton?
 

Ciklus I=0-tól M-ig    B(I):=0 Ciklus vége Ciklus I=1-től N-ig    B(A(I)):=B(A(I))+1 Ciklus vége (*) Ciklus I=1-től M-1-ig    B(I):=B(I)+B(I-1) Ciklus vége (**) Ciklus I=1-től N-ig    C(B(A(I))):=A(I) : B(A(I)):=B(A(I))-1 Ciklus vége (***)

4. feladat: (18 pont)

Egy kétsávos egyirányú út forgalmát szimuláló programot készítettünk. A sávok forgalmát az A tömb írja le:



Az A(I,1)= -1 azt jelenti, hogy a felső sáv I. helyén nincs autó, illetve A(I,1)>=0 az itt tartózkodó autó sebességét adja meg (egy időegység alatt ennyit léphet előre). Az A(I,2) ugyanezt jelenti az alsó sávban.

Add meg, milyen forgalmi szituációkat szimulálnak az F1, F2 ... eljárások közül megírtak, illetve írd meg a szöveggel megadottakat! (A megoldásban S a maximális sebességet jelenti.)
 

Ciklus I=N-től 1-ig -1-esével    Ciklus J=1-től 2-ig       F1(I,A(I,J),J,K) : F1(I,A(I,J),3-J,L)       Ha K=A(I,J) és A(I,J)<S akkor          F2(I,J)       különben          ha K=A(I,J) akkor             F3(I,J)          különben             ha L<A(I,J)                akkor F4(I,J,K)             különben F5(I,J,L)    Ciklus vége Ciklus vége

---

F1(I,T,J,K): Lehet-e a J. sévban az I. helytől T lépést előrelépni? K legyen az a lépésszám, amennyit lehet (maximum T, minimum 0), I+K=N+1, ha az út végére ért az autó. Eljárás vége

F2(I,J): Előrelépés a sebességnek megfelelő távolságra majd gyorsítás 1 egységgel Eljárás vége

F3(I,J): Előrelépés a sebességnek megfelelő távolságra Eljárás vége

F4(I,J,K): A(I+K,J):=K-1 : A(I,J):= -1 Eljárás vége

F5(I,J,L): A(I+K,3-J):=A(I,J) : A(I,J):= -1 Eljárás vége.

5. feladat: (8 pont)

Mit, milyen helyzetben és méretben rajzolnak a következő, LOGO nyelvű programok?

A programban használt utasítások:

A.
LEFT 30
REPEAT 3 [ REPEAT 2 [ FORWARD x RIGHT 60 FORWARD x RIGHT 120 ] RIGHT 120 ]
B.
REPEAT 4 [ REPEAT 360 [ FORWARD 1 RIGHT 1 ] PENUP RIGHT 90 FORWARD 10 LEFT 90 PENDOWN ]

6. feladat: (15 pont)

Egy kurzormozgató program a kurzort a J, B, L, F billentyűkkel mozgatja. Mi a többi felhasznált billentyű hatása? A 'Rajzol' eljárás egy szakasz pontjait váltja ellenkezőjére a képen (sötétet világosra, illetve fordítva).
 

Kurzormozgatás: M:=1 : X:=100 : Y:=100 : RX:=X : RY:=Y : Rajzol(X,Y,X,Y) Ciklus    Be: B    Elágazás       B='F' esetén XX:=X : YY:=Y-1 : Változás       B='L' esetén XX:=X : YY:=Y+1 : Változás       B='J' esetén XX:=X+1 : YY:=Y : Változás       B='B' esetén XX:=X-1 : YY:=Y : Változás       B='1' esetén M:=1 : RX:=X : RY:=Y : Rajzol(X,Y,X,Y)       B='2' esetén M:=1 : RX:=X : RY:=Y : Rajzol(X,Y,X,Y)    Elágazás vége Ciklus vége Eljárás vége.

Változás: Ha M=1 akkor    Rajzol(RX,RY,X,Y) : Rajzol(RX,RY,XX,YY) különben    Rajzol(RX,RY,RX,Y) : Rajzol(RX,RY,RX,YY)    Rajzol(RX,RY,X,RY) : Rajzol(RX,RY,XX,RY)    Rajzol(RX,Y,X,Y) : Rajzol(RX,YY,XX,YY)    Rajzol(X,RY,X,Y) : Rajzol(XX,RY,XX,YY) Elágazás vége X:=XX : Y:=YY Eljárás vége.

7. feladat: (19 pont)

Egy színes monitor a képen megjelenő színeket az RGB színmodell segítségével állítja elő (R=red, G=green, B=blue). A megjelenő szín fehér, ha mindhárom szín benne van, fekete, ha egyik sem, alapszínű, ha a három szín közül csak az egyik szerepel a színben, s keverékszín, ha kettő. A színeket tehát egy háromelemű logikai vektorral ábrázoljuk, azon alapszíneknél igaz értékkel, amelyek az adott színben szerepelnek. Milyen műveleteket végeznek a következő eljárások?

A.
 

E1(S1, S2, S3):    Ciklus S=red-től blue-ig       S3(S):=S1(S) OR S2(S)    Ciklus vége Eljárás vége.

 
B.
 

E2(S1, S2):    Ciklus S=red-től blue-ig       S2(S):=NOT S1(S)    Ciklus vége Eljárás vége.

 
C.
 

E3(S1, SZ, I):    I:=1    Ciklus S=red-től blue-ig       Ciklus J=1-től 3-ig          SZ(J,S):=hamis       Ciklus vége       SZ(I,S):=S1(S)       Ha S1(S) akkor I:=I+1    Ciklus vége Eljárás vége.

 

8. feladat: (13 pont)

Mit adnak eredményül a következő függvényeljárások (L, L1, L2 karaktersorozatok, E egy karakter):

A.
 

Ismerjfel(L1, L2):    Ha üres(L1) akkor       eredmény:=L2    különben eredmény:=egymásután(els?(L1), Ismerjfel(elsőutániak(L1),L2)) Függvény vége.

B.
 

TaláljKi(E, L):    Ha üres(L) akkor       eredmény:=L    különben       Ha E=első(L) akkor          eredmény:=elsőutániak(L)       különben          eredmény:=egymásután(első(L), TaláljKi(E, elsőutániak(L))) Függvény vége.

C. Mi az eredménye az IsmerjFel("NEMES", egymásután("+","TIHAMÉR")) függvényeljáráshívásnak?

D. Mi az eredménye a TaláljKi("E", "NEMES") függvényeljáráshívásnak?

Elérhető összpontszám: 109 pont