Nemes Tihamér OKSzTV'95

1. feladat: (12 pont)

Egy vasúti rendező-pályaudvar egyetlen kitérőt tartalmaz, az alábbi ábrának megfelelően.



Ha egy vonatszerelvény érkezik az 1,2,3...N sorszámú kocsikkal, akkor minden egyes lépésben három lehetőség közül választhatunk:
 

ÁT	A szerelvény elején levő kocsit a kijárat felé továbbítjuk.
BE	A szerelvény elején levő kocsit a kitérőbe visszük.
KI	A kitérő végén álló utolsó kocsit a kijárat felé küldjük.

Állapítsd meg, hogy ha a beérkező szerelvény az 1,2,3,4 kocsikból áll, akkor lehet-e a kimenő szerelvény a következő sorrendű! Az előállíthatóknál add meg előállításuk lépéseinek sorrendjét, a többinél pedig magyarázd meg, hogy miért nem lehetséges az előállításuk!
 

A. 4,3,2,1
B. 4,1,2,3
C. 1,4,3,2
D. 1,4,2,3

2. feladat: (12 pont)

Egy kártyajátékos N lapot kap, de közülük egyszerre csak K lapot tud a kezében tartani. A következő algoritmusokban A(i) jelöli a kártyajátékos kezében levő i. lapot (1iK), mindhárom azt a tevékenységet játssza le, amelyben a kártyajátékosnak a j. sorszámú lapra van szüksége (1jN) - ha a kezében van, akkor stratégiája szerint átrendezheti a kezében levő lapokat; ha nincs, akkor le kell tennie valamilyen stratégia alapján a kezében levő lapok közül egyet, majd a helyére felveheti a szükséges lapot. Add meg, hogy a (*)-gal jelölt részre beírt egyes algoritmusokban milyen stratégiát alkalmaz a játékos!
 

i:=1 Ciklus amíg iK és A(i)j   i:=i+1 Ciklus vége (*)

A.	Ha i>K akkor Tedd le A(K)-t: A(K):=j        különben Ciklus p=i-től 2-ig                   A(p):=A(p-1)                 Ciklus vége                 A(1):=j Elágazás vége
B.	Ha i>K akkor Tedd le A(K)-t: A(K):=j: B(K):=1        különben p:=i-1: B(i):=B(i)+1                 Ciklus amíg p>0 és B(p)>B(p+1)                   Csere(A(p),A(p+1))                   Csere(B(p),B(p+1))                   p:=p-1                 Ciklus vége Elágazás vége
C.	Ha i>K akkor Tedd le A(K)-t              Ciklus p=K-tól 2-ig                A(p):=A(p-1)              Ciklus vége              A(1):=j Elágazás vége

3. feladat: (10 pont)

Van egy SZÖVEG típusunk, megfelelő műveletekkel. Ezek a műveletek az alábbiak:
 

HOSSZ	a szöveg hosszát megadó függvény
KIIR	a képernyőre írja a megfelelő betűt, vagy szöveget
ELEJE	eljárás, amely paramétereként kapott szövegből levágja az utolsó karaktert
VEGE	eljárás, amely paramétereként kapott szövegből levágja az első karaktert
ELSO	a szöveg első karakterét adó függvény
UTOLSO	a szöveg utolsó karakterét adó függvény

A. Milyen sorrendben írja ki az alábbi két eljárás a paraméterként kapott szöveget?
B. Mi lesz az eredmény az ELJ2("ALMA") eljáráshívás után?
 
 

PROCEDURE Elj1(S:Szoveg);   BEGIN     IF Hossz(S)>0 THEN Kiir(Utolso(S)); Eleje(S); Elj2(S);     END IF;   END Elj1;

PROCEDURE Elj2(S:Szoveg);   BEGIN     IF Hossz(S)>0 THEN Kiir(Elso(S)); Vege(S); Elj1(S);     END IF;   END Elj2;

4. feladat: (14 pont)

Egy rövidített hívószámok használatára alkalmas telefon leírása a rövidítés programozására így szól:
1. Nyomd le a STORE gombot!
2. Távolsági hívás esetén tárcsázd a 06-ot, majd nyomd le a PAUSE gombot, s utána a körzet 1-, vagy 2-jegy? körzetszámát!
3. Tárcsázd a 6- vagy 7-jegy? telefonszámot!
4. Nyomd le az AUTO gombot!
5. Tárcsázd azt az egyetlen számot, amit a késôbbiekben rövidített számként szeretnél használni a teljes hívószám tárcsázása nélkül!


A telefonkészülék az alábbi algoritmus szerint működik (a STORE gomb megnyomása után kezdôdik az algoritmus és a TÁBLA tömb azon elemébe teszi be a rövidített telefonszámot, amit utoljára nyomunk le - ez lesz a rövidítésre használt szám):
 

Telefonprogram:   Be: T(1),T(2): Db:=2   Ha T(1)=0 és T(2)=6 akkor      Ciklus       Be: T(3)     amíg T(3)PAUSE      Ciklus vége   Elágazás vége   Be: X   Ciklus amíg XAUTO     Db:=Db+1: T(Db):=X: Be: X   Ciklus vége   Be: X   TÁBLA(X):=T Eljárás vége.

Sorolj fel olyan eseteket, amikor vagy az algoritmus működik hibásan - és ilyenkor add meg a hibajelenséget is, vagy a tárolt telefonszám nem felel meg a Magyarországon használt - s a leírásban megadott - telefonszámoknak!

Egy grafikus nyelven a képernyővel a következő transzformációkat végezhetjük:
 

FORGAT((x,y),(p,q))	Négyzet alakú rész forgatása 90 fokkal balra
XTÜKÖR((x,y),(p,q))	Téglalap alakú rész tükrözése a téglalap X-tengelyére
YTÜKÖR((x,y),(p,q))	Téglalap alakú rész tükrözése a téglalap Y-tengelyére

Milyen transzformációkkal állítható elő az alábbi állapotból a következő néhány állapot? (Csak 2-lépéses megoldásokat keress!)
 

A	B	C
D	E	F
G	H	I

Feladatok:
 

A. B E C G H F A D I

B. B A C E F I H D G

Példa:
 

Alap A B C D E F G H I

XTÜKÖR ((1,2),(2,3)) A E F D B C G H I

6. feladat: (21 pont)

A következő algoritmusrészlet szövegben keres szöveget, az egyszerű keresést néhány ötlettel gyorsítva.
 

siker:=hamis: i:=1 Ciklus amíg ihossz(A)-hossz(B)+1 és nem siker   j:=hossz(B)   Ciklus amíg 1j és B(j)=A(i+j-1)     j:=j-1   Ciklus vége   siker:=(j=0): Ha nem siker akkor i:=i+C(j) Ciklus vége

A. A keresés külső ciklusa mikor áll le?
B. A belső ciklus mikor fejeződik be?
C. Mi a szerepe a C vektornak?
D. Próbálj megfogalmazni minél pontosabb szabályt a C vektor meghatározására, azaz próbáld kitalálni, hogyan lehetne C elemeibe 1-nél nagyobb számokat tenni!

7. feladat: (15 pont)

A. Hogyan titkosítja a Szöveg szöveget a következô programrészlet? Mi a szerepe a Kulcs-nak?
(Az angol ABC betűi: ABCDEFGHIJKLMNOPQRSTUVWXYZ.)

Kódoltszöveg:='': I:=1 Ciklus amíg IHossz(Szöveg)   Ha Szöveg(I)'A' és Szöveg(I)'Z' akkor     Újbetű:=Karakter(((Karakterkód(Szöveg(I))+              Karakterkód(Kulcs((I-1 mod Hossz(Kulcs))+1))             -2*Karakterkód('A')+1) mod 26)+Karakterkód('A'))    különben     Újbetű:=Szöveg(I)   Elágazás vége   Kódoltszöveg:=Kódoltszöveg+Újbetű: I:=I+1 Ciklus vége


 

Hossz	a bemenetként kapott szöveg hosszát adja meg
Karakter	a megadott kódú karaktert adja
Karakterkód	a megadott karakter kódját adja meg
Szöveg(I), Kulcs(I)	a Szöveg, Kulcs I. betűjét adja meg

B. Mi volt az eredeti szöveg, ha a program eredményként ezt adta: 'SEG GSR SXVJM' és a Kulcs értéke 'NEMES' volt?

Van egy tömbünk, amelyben az elsô K elemből álló részt, és a maradék N-K elemből álló részt fel kell cserélnünk úgy, hogy a két részen belül a sorrend ne változzon.

A feladatot megoldó eljárás:
 

procedure Felcserél(E,K,V: integer);   var I,J: integer;   begin     I:=K-E;     if I>V-K then I:=V-K;     if I>0 then begin       for J:=0 to I-1 do Csere(Tömb[E+J],Tömb[V-I+J]);        if K-E>V-K then Felcserél(E,K,V-I)       else Felcserél(E+I,K,V);     end;   end;

Hívása: Felcserél(0,K,N);

A. Hányszor kerül a Csere eljárás meghívásra?
B. Az eljárásba azonban hiba csúszott, így nem azt teszi, amit szeretnénk. Mit tesz a kitűzött feladat megoldása helyett?
C. Találd meg a hibát a Felcserél eljárásban!

Elérhető összpontszám: 100 pont