Nemes Tihamér OKSzTV'96

1. feladat: Szövegelés (7 pont)

Az alábbi algoritmusrészlet a szöveg típusú S változó értékét alakítja át; S szavakat és a szavakat elválasztó egy-egy szóközt tartalmaz.
 

S:=S+" " Ciklus amíg első(S)<>" "    S:=elsőutániak(S)+első(S) Ciklus vége S:=elsőutániak(S)

 
A. Mi lesz S értéke az algoritmusrészlet végrehajtása után? (Gondolj a kivételes esetekre is!)

B. Mire szolgál a ciklus előtti, illetve utáni értékadás?

Az alábbi program A és B értékét határozza meg az N elemű X vektor értékei alapján. M értéke kezdetben 1.
 

Mitcsinál (X, M, N, A, B) :   Ha N-M<=1 akkor Ha X(M)<=X(N) akkor A:=N: B:=M                                 különben A:=M: B:=N             különben K:=(M+N) div 2                      Mitcsinal (X, M, K, A1, B1)                      Mitcsinal (X, K+1, N, A2, B2)                      Ha X(A1)>X(A2) akkor A:=A1                                     különben A:=A2                      Ha X(B1)<X(B2) akkor B:=B1                                     különben B:=B2   Elágazások vége Eljárás vége.

A. Mi lesz A és B értéke?

B. Hányszor kell összehasonlítani az X tömb elemeit a megoldás során, ha N 2 hatványa?

C. Milyen esetben lesz azonos a futás végén A és B értéke?

3. feladat: Mit számol? (10 pont)

Az X és Y tömbökben egy sokszög egymást követő csúcsainak koordinátái vannak. Az alábbi algoritmusrészlet A és B értékét határozza meg.
 

A:=0: B:=0: i:=N Ciklus j:=1-től N-ig   L:=X[i]-X[j]: K:=Y[i]-Y[j]   A:=A+L*(Y[i]+Y[j]): B:=B+négyzetgyök (L*L+K*K)   i:=j Ciklus vége A:=abszolútérték(A/2)

A. Mi lesz A és B értéke?

B. Mire szolgál az abszolútérték-képzés?

4. feladat: Csak párhuzamosan! (16 pont)

Egy számítógépben "nagyon sok" processzor van, így a kifejezések kiszámítását egyszerre több processzor végezheti.

Példa:

 
Az (a+b)*(c/d)/(e+f) kifejezés optimálisan három lépésben számolható ki két processzorral.

1. lépés: (a+b) és (c/d) egyidejű kiszámítása két processzorral -legyen a két részeredmény u és v,

2. lépés: u*v és (e+f) egyidejű kiszámítása két processzorral -legyen a két részeredmény x és y

3. lépés: x/y kiszámítása egy processzorral.


Egy kifejezés párhuzamos kiszámítását akkor tekintjük optimálisnak, ha a lehető legkevesebb lépésben végezhető el úgy, hogy a práhuzamosan felhasznált processzorok száma minimális.

Állapítsd meg, hogy optimális esetben a következő kifejezések hány lépésben számolhatók ki, s kiszámításukhoz hány processzorra van szükség! (A zárójelezés nem bontható fel a kiszámítás gyorsítása érdekében!)
 

A. a+b*c+d*e

B. a*b+c*(d*e+f/g+h*i)

C. a*(b+c)-d*(e/f-g*h)+i*j

5. feladat: Pascal-program struktúrája (20 pont)

Egy Pascal program struktúráját PROLOG-szerű tényállításokkal adjuk meg:
 

tartalmazza (KülsőEljárás, BelsőEljárást)

megelőzi (EgyikEljárás, MásikEljárást)

E tényállítások a közvetlen tartalmazást, illetve közvetlen megelőzést írják le.

Példa:
 

Itt van egy Pascal program váza:

Program ...;    Procedure első;       Procedure második;       end {második};    end {első};    Procedure harmadik;    end {harmadik}; end {program}.

Struktúráját az alábbi tényállítások írják le:

tartalmazza ("első", "második"). megelőzi ("első", "harmadik").

A. Add meg a következő szabályoknak megfelelő Pascal-program vázát!
 

tartalmazza("A","B"). tartalmazza("B","C"). megelőzi("B","D"). megelőzi("A","E"). tartalmazza("A","D").

B. A Pascal-nyelvben, mint közismert, az eljárások a sorrendi és a láthatósági szabályok betartásával hívhatják egymást. Írj
 

hívhatja (X, Y) ha ...

néven olyan PROLOG-szerű eljárást, amely ellenőrzi, hogy X a sorrendi és láthatósági szabályok szerint hívhatja-e Y-t! A ha alapszó utáni formulákban a nem, a vagy, valamint az és logikai műveleteket, továbbá a tényállításokat is használhatod az általad esetleg definiálandó eljárások mellett.

6. feladat: Multihalmazok (24 pont)

Két állattenyésztő nyilvántartást vezet állatairól. Ez a nyilvántartás olyan [ és ] között álló, kétszeres mélységű sorozat, amely ábécé szerint rendezve tartalmazza az állatfajták nevét és darabszámát.

Példa:

A: [ [kacsa, 5], [liba, 13], [nyúl, 66], [tyúk, 4] ]

B: [ [kacsa, 1], [kecske, 33], [nyúl, 99] ]


A nyilvántartás kezelésére szolgáló függvények a következők:

A. Mit adnak eredményül a következő rekurzív függvények?
 

Egyik(A, B):   Ha üres(A) és üres(B)     akkor 0     különben       ha üres(A)         akkor második(első(B))+Egyik(A,elsőutániak(B))         különben második(első(A))+Egyik(elsőutániak(A),B) Függvény vége.

Másik (A, B):   Ha üres(A) és üres(B)   akkor []   különben     ha üres(A)     akkor B     különben       ha üres(B)       akkor A       különben          ha első(első(A))>első(első(B))         akkor elejére(első(B), Másik(A, elsőutániak()B))         különben            ha első(első(A))<első(első(B))           akkor elejére (első(A), Másik(elsőutániak(A),B))           különben elejére(pár(első(első(A)),                            második(első(A))+második(első(B))),                            Másik(elsőutániak(A), elsőutániak(B))) Függvény vége.

B. Készíts olyan függvényt, amely megadja, hogy a két gazdának összesen hány fajta állata van! (A fenti példában öt fajta állat szerepel.)

C. Készíts olyan függvényt, amely megadja, hogy melyik állatfajtából mennyit tudnak eladni akkor, ha egy-egy állatfajtából mindkettőjüknek ugyanannyit kell értékesíteniük! (A fenti példa szerint mindössze kacsát és nyulat adhatnak el, mégpedig: [[kacsa,1], [nyúl, 66] ].)

7. feladat: Pénzgyűjtögetők (13 pont)

Arany oszkár 5, Ezüst Benő 10 forintosokat gyűjt. Egy perselybe 5, 10 és 20 forintosokat lehet bedobni. Ha egymás után két 5 forintost dobnak be, akkor Arany Oszkár azonnal kicseréli őket egy 10 forintosra, ha pedig két 10 forintost dobnak be, akkor Ezüst Benő cseréli ki őket egy 20 forintosra.

Arany Oszkárt és Ezüst Benőt egy-egy olyan (végtelen ciklusban futó) eljárással helyettesítjük, amelyek egymást hívogatják. Az A eljárás végrehajtása félbeszakad, amikor a B-t meghívja, majd amikor a B hívja meg az A-t, akkor a B végrehajtása szakad félbe, és az A végrehajtása folytatódik onnan, ahol az előbb megszakadt, amíg újra meg nem hívja B-t. Ilyenkor az A megint félbeszakad, és a B végrehajtása folytatódik az előző megszakítási ponttól. És így tovább. (A két eljárás végrehajtási módja tehát nem azonos a szokásos hívás-visszatérés mechanizmussal - az így működő eljárásokat hívják korutinoknak). PÉNZ az alábbi két eljárás közös változója.
 

Arany Oszkár:   Ciklus     Be: Pénz     Ha PÉNZ=5 akkor       Be: PÉNZ       Ha PÉNZ=5 akkor         Ki:10 (**)       különben         P:=PÉNZ         PÉNZ:=5: Ezüst Benő         PÉNZ:=P: Ezüst Benő       Elágazás vége     különben       Ezüst Benő     Elágazás vége   Ciklus vége Eljárás vége.

Ezüst Benő:   Ciklus     Ha PÉNZ=10 akkor       Arany Oszkár (***)       Ha PÉNZ=10 akkor         Ki: 20 (*)       különben         Ki: 10, PÉNZ       Elágazás vége     különben       Ki: PÉNZ     Elágazás vége     Arany Oszkár   Ciklus vége Eljárás vége.

A. Milyen esetben hajtjuk vége a *-gal jelölt kiírást?

B. Ha Arany Oszkár kicserél két 5 forintost egy 10 forintosra, a fenti eljárás azonnal kiírja (**-gal jelölt sor). Alakítsd át úgy ezt a sort, hogy ha ezután 10 forintos következne, akkor Ezüst Benő beválthassaa két 10 forintost egy 20 forintosra!

C. Miért lenne helytelen az eljáráspár működése, ha a ***-gal jelölt helyen Arany Oszkár hívása helyett Be: PÉNZ állna?

Elérhető összpontszám: 100 pont