Nemes Tihamér OKSzTV 2002

1. feladat: Válogatós (24 pont)

Lányok (N) és fiúk (M) ülnek egy sorban, vegyesen (N+M>0). Szeretnénk úgy ültetni őket, hogy az első N széken üljenek a lányok, a következő M széken pedig a fiúk.

A feladat megoldására a következő algoritmust találtuk ki:

1. Az első széken levőt felállítjuk (kezdetben ez lesz a szabad szék).
2. Az utolsó széktől visszafelé, de legfeljebb a szabad székig haladva keresünk egy lányt.
3. Ha találunk, akkor megjegyezzük, hogy legközelebb már csak innentől kezdve kell lányt keresni, és a lányt átültetjük a szabad székre.
4. Ezután az első széktől, de legfeljebb a szabad székig haladva keresünk egy fiút.
5. Ha találunk, akkor megjegyezzük, hogy legközelebb már csak innentől kezdve kell fiút keresni, és a fiút átültetjük a szabad székre.
6. Ha egyik keresés során sem értük el a szabad széket, akkor a 2. ponttól kezdve foly-tatjuk a keresést.
7. A szabadon maradt székre ültetjük azt, akit az első lépésben felállítottunk.

Példa: (Dóra,Endre,Ágnes,István) => (-,Endre,Ágnes,István) => (Ágnes,Endre,-, István) => (Ágnes,-,Endre,István) => (Ágnes,Dóra,Endre,István)

A. Mi lesz az eredmény, ha kezdetben a székeken ülők sorrendje (azaz a kezdő ülésrend): (Erika, János, Nóra)? A fenti példához hasonlóan lépésenként írd le!
B. Mi lesz az eredmény, ha a kezdő ülésrend: (Anna, Emese, Béla, Enikő, András, Jakab, Eszter, Móni, László, Piri, Péter)? A fenti példához hasonlóan lépésenként írd le!
C. Van olyan kezdő ülésrend, hogy csak egyetlen gyereknek kell mozognia. Melyik gyereknek, milyen kezdő ülésrend esetén?
D. Van olyan kezdő ülésrend, hogy minden gyereknek mozognia kell. Melyik ez a kezdő ülésrend?

Milyen hibák vannak az alábbi szakaszrajzoló eljárásban, amely az (x1,y1) és az (x2,y2) pontok között próbál meg szakaszt rajzolni? (A koordináták egész számok. Feltehetjük, hogy a végpontok biztosan a képernyőn vannak.) Hogyan jellemezhetők azok a szakaszok, amelyeket ez a szakaszrajzoló hibásan rajzol fel?
 

Szakasz(x1,y1,x2,y2):   dy:=(y2-y1)/(x2-x1); py:=y1; px:=x1   Ciklus amíg px<x2     rajzol(px,py)  {Kirajzolja az adott pontot}     py:=py+dy; px:=px+1   Ciklus vége Eljárás vége.

Sorozatokon az alábbi függvényeket értelmezzük:
 

üres(sorozat)	igaz, ha a sorozat üres, hamis, ha nem
első(sorozat)	a sorozat első eleme
utolsó(sorozat)	a sorozat utolsó eleme
elsőnélküli(sorozat)	a sorozat első elem nélküli (rész)sorozata
utolsónélküli(sorozat)	a sorozat utolsó elem nélküli (rész)sorozata
elsőnek(elem,sorozat)	elsőnek(elem,sorozat)
utolsónak(elem,sorozat)	az új elemmel a végén bővített sorozat


 

Egyik(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Egyik:=S   különben Egyik:=utolsónak(első(S),elsőnek(utolsó(S),                   Egyik(elsőnélküli(utolsónélküli(S))))) Függvény vége.

Másik(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Másik:=S   különben Másik:=utolsónak(első(S),                   elsőnek(első(elsőnélküli(S)),                   Másik(elsőnélküli(elsőnélküli(S))))) Függvény vége.

A. Mi az eredménye az Egyik("ABCDEF") függvényhívásnak? Fogalmazd meg általánosan is!
B. Mi az eredménye a Másik("ABCDEF") függvényhívásnak? Fogalmazd meg általánosan is!
C. Mi az eredménye az Egyik("ABCDE") függvényhívásnak?
D. Mi az eredménye a Másik("ABCDE") függvényhívásnak?

A következő algoritmus az A vektorban található nemnegatív egész számok alapján állítja elő a C vektort.
 

Mitcsinál(A,C):   Ciklus i=1-től N-ig     B(i):=1; C(i):=-1     Ciklus j=1-től N-ig       Ha A(i)>A(j) akkor B(i):=B(i)+1     Ciklus vége   Ciklus vége      {*}   Ciklus i=1-től N-ig     C(B(i)):=A(i)   Ciklus vége      {**}   Ciklus i=2-től N-ig     Ha C(i)<C(i-1) akkor C(i):=C(i-1)   Ciklus vége      {**} Eljárás vége.

A. Mit tartalmaz a B vektor a {*} jellel jelölt ciklus lefutása után?
B. Mit tartalmaz a C vektor a {**} jellel jelölt ciklus lefutása után?
C. Mit tartalmaz a C vektor a {***} jellel jelölt ciklus lefutása után?
D. Mit csinál az algoritmus?

Egy tömörítő eljárás a tömörítendő jelsorozat azonos elemekből álló részsorozatait három karakterrel kódolja: a *-jellel, a sorozat hosszából mint ascii-kódból előállított karakterrel és magával az ismétlődő karakterrel. Az eljárásnak az X szöveges állomány a bemenete és a Z szöveges állomány a kimenete.
 

Eljárás Tömörítés:   Nyit(X); Nyit(Z); Olvas(X,k)   Ciklus amíg nem filevége(X)     Csoportolvasás(X,db,kar,k); Ír(Z,*+Karakter(db)+kar)   Ciklus vége   Zár(X); Zár(Z); Eljárás vége.

Eljárás Csoportolvasás(X,db,kar,k):   kar:=k; db:=1; Olvas(X,k)   Ciklus amíg k=kar     db:=db+1; Olvas(X,k)   Ciklus vége Eljárás vége.

A. Milyen hibák vannak az eljárásban?
B. Hogyan lehet ezeket kijavítani? (Ne új eljárást írj!)
C. Milyen esetekben lesz hosszabb a tömörített állomány, mint a tömörítetlen?
D. Mit kell módosítani az eljárásban, hogy a tömörített állomány semmilyen esetben ne lehessen hosszabb az eredetinél?

Elérhető összpontszám: 100 pont