Nemes Tihamér OKSzTV'91

Első forduló

11-13. osztályosok

1991. január 14. 1400-1700


1. feladat: (12 pont)

Az alábbi két függvényeljárás (nyissz és nyassz) rudakat darabol. A rudak hosszát a rúd tömbben tároljuk, amelynek a rudak számánál eggyel több eleme van. A tömb utolsó eleme az úgynevezett strázsa, amelyben -1 van. A két függvényeljárás bemenő paramétereként azt kellene megadni, hogy mekkora rúddarabot akarunk levágni.
 
VAR rúd: ARRAY [1..Maxrúd] OF INTEGER;

FUNCTION nyissz(h:INTEGER) : INTEGER;
  VAR p : INTEGER;
BEGIN
  p:=1;
  WHILE (rúd[p+1]<>-1) AND (rúd[p]<h) DO p:=p+1;
  IF rúd[p]<h
  THEN nyissz:=0
  ELSE BEGIN nyissz:=p; rúd[p]:=rúd[p]-h END
END {nyissz};

FUNCTION nyassz(h:INTEGER):INTEGER;
  VAR p, q, m : INTEGER;
BEGIN
  p:=1; q:=0; m:=MAXINT;
  WHILE (rúd[p]<>-1) DO BEGIN
    IF (rúd[p]-h>=0) AND (rúd[p]-h<m)
    THEN BEGIN m:=rúd[p]-h; q:=p END;
    p:=p+1
  END;
  IF q<>0 THEN rúd[q]:=m;
  nyassz:=q
END {nyassz};

A.

Hogyan alakul a tömb tartalma, és milyen értéket adnak vissza az egyes függvényeljárások, ha kezdetben a tömbben [3, 5, 2, 4, 7, -1] van, és a 3, 4, 2, 2 paraméterekkel hívjuk meg mind a nyissz, mind a nyassz eljárást, külön-külön, a megadott sorrendben?
B.
A [2, 1, -1] tömbhöz adj meg olyan rúdigénylést, amelyre a nyissz függvényeljárás 0-t fog valamikor visszaadni, a nyassz pedig soha. (Ha nincs ilyen, válaszodat akkor is indokold meg!)
C.
A [3, 2, -1] tömbhöz  adj meg olyan rúdigénylést, amelyre a nyassz függvényeljárás fog valamikor 0-t visszaadni, a nyissz pedig soha. (Ha nincs ilyen, válaszodat akkor is indokold meg!)

2. feladat: (10 pont)
 

Furcsa számítógépünk a következő formában várja tőlünk a programot. Először meg kell adni az alapismereteket. Másodszor föl kell sorolni azokat a következtetési szabályokat, amelyek alkalmazásával a problémát megoldhatónak gondoljuk.
Alapismeretek például:
1. anyja (Szilágyi Erzsébet, Mátyás).
  Ez azt jelenti, hogy Szilágyi Erzsébet anyja Mátyásnak.
2. apja (Hunyadi János, Mátyás).
  Ez azt jelenti, hogy Hunyadi János apja Mátyásnak.
Szabályok például:
1. szülője(x,y) HA anyja(x,y) VAGY apja(x,y).
2. nagyszülője(x,y) HA szülője(x,z) ÉS szülője(z,y).
Ez magyarul a következőt jelenti: akkor nagyszülője x y-nak, ha van olyan z személy, akinek x a szülője és ő (azaz z) szülője y-nak.
A logikai kifejezéseket balról jobbra haladva értékeli ki a gép. A kiértékelést abbahagyja, ha a részeredmény alapján már eldönthető a teljes kifejezés értéke.
A:
Milyen rokonsági kapcsolatot határoznak meg a következő szabályok?
a. rokon1(x,y) HA szülője(z,x) ÉS szülője(z,y) ÉS x<>y.
b. rokon2(x,y) HA apja(x,z) ÉS szülője(z,y).
c. rokon3(x,y) HA szülője(x,y) VAGY (szülője(x,z) és rokon3(z,y))
B:
Írd meg a következő rokoni kapcsolatokat leíró szabályokat!
a. anyaiNagyszülője(x,y) HA ... {azaz x anyai nagyszülője y-nak}
b. szülőpár(x,y) HA ... {azaz akiknek közös gyermekük van}
c. leszármazottja(x,y) HA ... {azaz x leszármazottja y-nak}

3. feladat: (8 pont)


4. feladat: (15 pont)

A következ? két rendez? eljáráshoz írj olyan állításokat, amelyek a megjelölt helyeken érvényesek, és a rendezend? vektorra vonatkozó minden lényeges információt tartalmaznak!
 
Rendezés:
  Ciklus I=1-t?l N-1-ig
  {A. állítás}
    M:=I
    Ciklus J=I+1-t?l N-ig
    {B. állítás}
      Ha A(M)>A(J) akkor M:=J
    Ciklus vége
    Csere(A(I), A(M))
  Ciklus vége
Eljárás vége
Rendezés:
  Ciklus I=2-t?l N-ig
  {C. állítás}
    J:=I-1
    Ciklus amíg J>0 és A(J)>A(J+1)
    {D. állítás}
      Csere(A(J), A(J+1)) : J:=J-1
    Ciklus vége
  Ciklus vége
Eljárás vége.

5. feladat: (12 pont)

Adott az alábbi Pascal-nyelvű függvényeljárás:
 
FUNCTION hash(v: INTEGER): INTEGER;
  VAR h: INTEGER;
BEGIN
  h:=0;
  WHILE v<>0 DO BEGIN h:=h+v MOD 10; v:=v DIV 10 END;
  hash:=h MOD Max
END {hash};

A hash függvényt a következő eljárás használja:
 
PROCEDURE insert(v: INTEGER);
  VAR place, n : INTEGER;
BEGIN
  palce:=hash(v); n:=0;
  WHILE (n<Max) AND (memo[place]>=0) DO BEGIN
    place:=(place+1) MOD Max;
    n:=n+1
  END;
  IF memo[place]<0 THEN memo[place]:=v
END;

A VAR memo: ARRAY[0..Max-1] OF INTEGER (globális) tömb minden elemének kezdetben -1 az értéke.
Mi lesz a memo tömb tartalma az alábbi insert-sorozatok adott sorrendű végrehajtása után, a Max állandó adott értéke mellett?
 
A.
CONST Max=7;
insert(2); insert(26); insert(117); insert(8); insert(18)

 
B.
CONST Max=11;
insert(2); insert(26); insert(117); insert(8); insert(18); insert(14); insert(13)
 

6. feladat: (12 pont)

Egy adatátviteli rendszerben két számítógép között soros vonalon, négybites csomagokban továbbítják az információt. Mivel az átviteli csatorna nem tökéletes, kb. minden 50. átküldött bit megsérül. Annak azonban elenyésző a valószínűsége, hogy egymáshoz ennél közelebb lévő bitek sérüljenek meg. Ezért minden négybites csomagot 7 biten kódolva küldenek át. Így ha a 7 bitből csak egy sérül meg, akkor az eredetileg átküldött adat visszaállítható. Ha több bit sérül meg egyszerre, akkor az alábbi algoritmus nem működik helyesen. (A XOR bitenkénti KIZÁRÓ VAGY művelet.)
A következő programrészlet a vevő oldalon a dekódolás folyamatát látja el. Bemenete a csat hételemű tömb, amely a csatornán érkezett és ugyanabba a a csomagba tartozó biteket tartalmazza. Kimenetként az üzen négyelemű tömbben helyreállítja az eredeti üzenet 4 bitjét.
 
i:=0
IF (csat[1] XOR csat[3] XOR csat[5] XOR csat[7])=1 THEN i:=i+1;
IF (csat[2] XOR csat[3] XOR csat[6] XOR csat[7])=1 THEN i:=i+2;
IF (csat[4] XOR csat[5] XOR csat[6] XOR csat[7])=1 THEN i:=i+4;
IF i>0 THEN csat[i]:=NOT(csat[i]);
üzen[1]:=csat[3]; üzen[2]:=csat[5]; üzen[3]:=csat[6]; üzen[4]:=csat[7];

A következő programrészlet az adóoldalon a kódolás feladatát látja el. Értelemszerűen az előző eljárás fordítottját végzi. Néhány szám azonban hiányzik belőle. Ezeket *-gal helyettesítettük.
 
csat[3]:=üzen[1]; csat[5]:=üzen[2]; csat[6]:=üzen[3]; csat[7]:=üzen[4];
csat[1]:=csat[*] XOR csat[*] XOR csat[*];
csat[2]:=csat[*] XOR csat[*] XOR csat[*];
csat[4]:=csat[*] XOR csat[*] XOR csat[*];

Milyen értéket vehet fel, és mit fejez ki i hibátlan átvitel, illetve egyszeres hiba esetén? Add meg a *-gal helyettesített számokat a programban való előfordulásuk sorrendjében!


7. feladat: (12 pont)

Pap Jancsi fogad Tasziló barátjával, hogy a padláson heverő lyukszalagok egyikén sem fordul elő a "LILLA" szó. De hogy biztos legyen a dolgában, programot ír a lyukszalagok átalakítására.
Az alábbi BASIC nyelvű programban az OLVAS(K$) parancs az 1-es számú lyukszalag következő karakterét olvassa be K$-ba, az ÍR(L$) parancs pedig a 2-es számú lyukszalagra írja ki az L$ tartalmát. A szalagok végét a "$" jel jelzi. (Mivel Pap Jancsi még nem nagyon tud programozni, programja hibajelzéssel fog leállni a szalag végén.)
Pap Jancsi minden szalagot átmásol a programmal,  majd a már átalakított szalagokat újra meg újra átfuttatja, amíg csak változást tapasztal. Végül minden szalag eredetije helyett annak utolsó változatát rakja vissza a padlásra.
 
10 OLVAS(K$)
15 IF K$<>"L" THEN ÍR(K$): GOTO 10 ELSE OLVAS(K$)
20 IF K$<>"I" THEN ÍR("L"): GOTO 15 ELSE OLVAS(K$)
30 IF K$<>"L" THEN ÍR("LI"): GOTO 15 ELSE OLVAS(K$)
40 IF K$<>"L" THEN ÍR("LIL"): GOTO 15 ELSE OLVAS(K$)
50 IF K$<>"A" THEN ÍR("LILL"): GOTO 15 ELSE GOTO 10
60 END
Tasziló, aki megneszelte a turpisságot, már előre dörzsöli a kezét. Jogosan, mert a program valóban rossz.
A:
Tasziló, hogy nyilvánvalóvá tegye a diadalát, saját készítésű lyukszalagot dug el Pap Jancsi padlásán. Mi legyen a szalagon, hogy a program biztosan felsüljön? (Azaz bennhagyjon legalább egy LILLÁt.)
B:
Pap Jancsi közben maga is rájön a hibára, és kijavítja a programot. Két sorban végez apró módosítást, a többi soron nem változtat, és új sort sem szúr be. Add meg ezt a két sort kijavítva!

8. feladat: (13 pont)

A Folttisztító Turbo-Pascal eljárás a grafikus képernyőn lévő és a háttértől elütő színű alakzat pontjait festi át háttérszínűre, bizonyos rendszer szerint. A felhasznált grafikus utasítások és függvények:
 
GetPixel(x,y) az (x,y) koordinátájú pont színét adja vissza
GetBkColor a háttér színét adja vissza
PutPixel(x,y,szín) az (x,y) pontot szín színűre festi
(Megjegyzés: az origó a bal felső sarokban van, x vízszintes, y függőleges elmozdulást jelent.)
 
PROCEDURE FoltTisztito(x,y: INTEGER);
  VAR x1, y1, d, n : INTEGER;
BEGIN
  x1:=x; y1:=y; d:=1; n:=0;
  REPEAT
    CASE d OF
      1: BEGIN x1:=x+1; y1:=y   END;
      2: BEGIN X1:=x;   y1:=y+1 END;
      3: BEGIN x1:=x-1; y1:=y   END;
      4: BEGIN x1:=x;   y1:=y-1 END;
    END {CASE};
    IF (GetPixel(x1,y1)<>GetBkColor) THEN BEGIN
      PutPixel(x,y,GetBkColor); n:=0; x:=x1; y:=y1; d:=(d+2) MOD 4+1
    END
    ELSE BEGIN d:=d MOD 4+1; n:=n+1 END
  UNTIL n=4
END {FoltTisztito};

A.

Mi a d változó szerepe, és mit jelentenek egyes értékei?
B.
A képernyőn a következő, a háttétől elütő színű alakzat helyezkedik el. (Egy-egy mező egy-egy képernyőpontot jelent.) Sorszámozd be a program által "kitisztított" pontokat a tisztítás sorrendjében, az a, b, c és d betűkkel megjelölt, négy különböző kiindulási mező esetén! (Mind a négy esetre rajzolj egy-egy ábrát!)
a
     
   
b
     
     
c
   
     
d

Elérhető összpontszám: 84 pont