Nemes Tihamér OKSzTV'92

1. feladat: (16 pont)

A következő függvényeljárás az A tömb elemeiből számít ki egy értéket (a tömböt 1-től indexeljük):
 

F(P):    Ha A(P)>=0 akkor       F:=A(P)    különben       I:=F(2*P) : J:=F(2*P+1)       Ha I= -1 vagy J= -1 akkor          F:=-1       különben          Ha A(P)= -1 akkor             F:=I+J          különben             Ha A(P)= -2 akkor                F:=I-J             különben                Ha A(P)= -3 akkor                   F:=I*J                különben                   Ha A(P)= -4 akkor                      Ha J=0 akkor                         F:= -1                      különben                         F:=I/J                   különben F:= -1    Elágazások vége Eljárás vége.

A. Mi lesz az A tömbben levő számok pontos szerepe, jelentése?

B. Mi lesz F(1) értéke, ha az A tömb tartalma [-2, 7, 5]?

C. Mi lesz F(1) értéke, ha az A tömb tartalma [-1, -3, -4, 2, 2, 6, 2]?

D. Milyen esetekben ad F(1) függvényeljárás-hívás -1-et eredményül?

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: Csak párhuzamosan! (16 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: (20 pont)

Egy tömbben tároljuk egy terület NxM pontjának tengerszint feletti magasságát. A pontok egymástól S távolságra vannak egy négyzetrácson. Az SZ magasságú szintvonalat a következő ciklussal rajzolhatjuk meg:
 

Ciklus I=1-től N-1-ig    Ciklus J=1-től M-1-ig       Ha szintvonal(I,J,I+1,J) akkor                  Szakaszrajz(I*S,J*S-S/2,I*S,J*S)       Ha szintvonal(I,J,I,J+1) akkor                  Szakaszrajz(I*S-S/2,J*S,I*S,J*S)       Ha szintvonal(I+1,J,I+1,J+1) akkor                  Szakaszrajz(I*S+S/2,J*S,I*S,J*S)       Ha szintvonal(I,J+1,I+1,J+1) akkor                  Szakaszrajz(I*S,J*S+S/2,I*S,J*S)    Ciklus vége Ciklus vége

Szintvonal(I,J,K,L):    Szintvonal:=(T(I,J)<SZ és T(K,L)>=SZ) vagy (T(I,J)>=SZ és T(K,L)<SZ) Eljárás vége.

Ez a megoldás pontnégyesekre bontja a síkot. Ha a pontnégyes egy pontpárja között átmegy szintvonal, az azok közötti felezőpontot összeköti a pontnégyes által meghatározott négyzet középpontjával. Pl:

Alakítsd át az algoritmust, hogy a kijelölt szintvonal ne a felezőpontokon menjen át, hanem a megfelelő pontpárokban vett érték szerint arányosan határozd meg! A kiválasztott pontokat ne a négyzet középpontjával kösd össze, hanem egymással! Írd le azt is, hogy milyen esetek fordulhatnak el? (hány pontot lehet egy négyesen belül összekötni)! Pl:

6. feladat: (16 pont)

Egy agyafúrt bankrabló lefotózta a széf biztonsági programját. Balszerencséjére a programrész eleje és vége lemaradt!

A. Milyen értékeket vehet fel a B változó a 12310-es sorban?

B. Hogyan változtatja a ciklusmag az A és a B értékét?

C. Legfeljebb hány kódot kell kipróbálnia a betörőnek, hogy biztosan kinyithassa széfet és melyek lehetnek ezek?
 

... 12300 B=INT(ABS(X)) 12310 B=B-INT(B/3)*3+1 12320 INPUT "Mi a titkos kód", A 12325 IF A<100 OR A>999 THEN GOTO 07 12330 A=INT(A-33)*2 12340 FOR I=1 TO 2 12345 C=INT(A/10) 12350 B=B+A-C*10 12360 A=C 12370 NEXT 12380 IF B<>A OR B>3 THEN GOTO 12300 12390 PRINT "Máris nyitom!" ...

7. feladat: (13 pont)

Az alábbi rekurzív függvényeljárás bemenő paraméterei az X, M, A és B változók. X és M csak pozitív értékek lehetnek.

A. Milyen értéket számít ki a függvény?

B. Mi M szerepe?

C. Mi A és B szerepe?

D. Tetszőleges pozitív X és M esetén adj meg olyan A és B kezdőértékpárt, amely biztosan jó!
 

Function Rekurziv(X,M,A,B:Real):Real;   Var C:Real; Begin   C:=(A+B)/2;   If C-A<M Then Rekurziv:=C   Else If C*C>X Then Rekurziv:=Rekurziv(X,M,A,C)        Else Rekurziv:=Rekurziv(X,M,C,B) End{Rekurziv};

8. feladat: (13 pont)

A lista mint adatszerkezet rekurzív definíciója a következő:

1. . egyetlen elemet sem tartalmaz, azaz üres
2. . egy nemüres elemet és egy azt követő listát tartalmaz.
A lista adattípust a fenti rekurzív definíciót hűen követve így definiálhatjuk egy képzeletbeli programozási nyelven (ahol NIL üres listát, | választást jelöl, Elem pedig bármilyen, már ismert adattípus lehet):
TYPE Lista = NIL | (feje: Elem, farka: Lista)
Az alábbi függvényeljárás egy elemből és egy listából egy egy elemmel hosszabb listát hoz létre:
FUNCTION hozzLétre(e:Elem, l:Lista):Lista:
RETURN Lista:[e,l].
Ennyi bevezető után írd le saját szavaiddal az alábbi függvényeljárások hatását és működését:

A.
 

FUNCTION ismerjFel(l1, l2 : Lista): Lista: RETURN IF l1=NIL Then l2        ELSE hozzLétre(l1.feje, ismerjFel(l1.farka, l2)) ENDIF.

 
B.
 

FUNCTION találjKi(e:Elem, l:Lista): Lista: RETURN IF l=NIL THEN l        ELSE IF e=l.feje THEN l.farka             ELSE hozzLétre(l.feje, találjKi(e, l.farka)) ENDIF.

 
Tegyük fel, hogy már léteznek az alábbi (az egyszerűség kedévért csupa karakterekből álló) listák:
l1: (N(E(M(E(S)))))
l2: (T(I(H(A(M(É(R)))))))
Add meg az alábbi műveletek (függvényeljárás-hívások) eredményét:

C. ismerjFel(l1, hozzLétre('+', l2))=?

D. találjKi('E', l1)=?