Nemes Tihamér OKSzTV'98

Első forduló

III. kategória, 11-13. osztályosok


1. feladat: Síkbeli kód (14 pont)
 
Egy téglalap pontjait fix hosszúságú, négyes számrendszerbeli számokkal kódoljuk.
Első lépésben a teljes téglalapot – oldalainak felezésével – négy egyforma részre (síknegyedre) osztjuk. Minden síknegyedhez a bal oldali ábra szerinti kódot rendeljük. A síknegyedek további felosztását és kódolását hasonlóképpen folytatjuk, amíg el nem érünk egy előre megadott mélységet. Egy pont kódja a pontot magába foglaló síknegyedek kódjának sorozata. Egy határpontot a (leg)kisebb kódú síknegyedbe tartozónak tekintünk.
A jobb oldali ábrán az (x, y) = (610, 720) koordinátájú pont 3 mélységű kódjának (301) meghatározása látható.
A. Határozd meg a [1-1000]×[1-1000]-es tartományba eső alábbi pontok 3 mélységű kódját:
1: (100,200)
2: (611,345)
3: (875,475)
4: (250,750)
B. Az alább felsorolt kódú pontok közül melyekről dönthető el egyértelműen, hogy a 600<= x< 900, 100<= y<800 tartományba esnek?
1:001
2:003
3:011
4:021
5:023
6:102
7:112
8:123
9:130
10:131
11:200
12:203
13:211
14:221
15:232
16:233
17:302
18:303
19:312
20:320


2. feladat: Halmazok uniója (15 pont)
 

Az alábbi algoritmus három, tömbként ábrázolt halmaz (A,B,C) unióját állítja elő egy negyedikben (D). Az egyes halmazok elemszáma rendre AN, BN, CN, illetve DN.
 
Unió:
  D:=A: DN:=AN
  Ciklus I=1-től BN-ig
    J:=1
    Ciklus amíg J<AN és A(J)?B(I)
      J:=J+1
    Ciklus vége
    Ha J>=AN akkor DN:=DN+1: D(DN):=B(I)
  Ciklus vége

  Ciklus I=1-től CN-ig
    J:=1
    Ciklus amíg J<AN és A(J)?C(I)
      J:=J+1
    Ciklus vége
    Ha J>=AN akkor DN:=DN+1: D(DN):=C(I)
  Ciklus vége
Eljárás vége.

A. Milyen bemenő adatokra ad rossz eredményt az algoritmus?
B. Magyarázd el, hogyan lehet kijavítani az algoritmust?



3. feladat: Bizonytalan (10 pont)
A BIZONYTALAN programnyelv kétféle vezérlési szerkezetet ismer: az elágazást és a ciklust.

Az elágazás egy igaz feltételű utasítást választ ki és hajt végre (több igaz feltétel közül a választás véletlenszerű).

IF feltétel1® utasítás1 | feltétel2® utasítás2 | ... | feltételn® utasításn FI
A ciklusban a ciklusmagot addig kell ismételni, amíg legalább egy feltétel teljesül. A ciklusmag egyszeri végrehajtása az egyik igaz feltételű utasítás végrehajtását jelenti (több igaz feltétel közül a választás véletlenszerű).
DO feltétel1® utasítás1 | feltétel2® utasítás2 | ... | feltételn® utasításn OD
Mit csinálnak az alábbi programrészletek?
 
A. {X, Y és Z 1-nél nagyobb természetes számok.}
A:=X: B:=Y: C:=Z
DO A>B -> A:=A-B | B>C -> B:=B-C | C>A -> C:=C-A OD
B. {Az A mátrix egyik oszlopában sem fordul elő ugyanaz az elem kétszer.
X és Y tetszőleges, előre meghatározott értékek.}
I:=1: J:=1
DO A[1,I]<> X -> I:=I+1 | A[2,J]<> Y -> J:=J+1 OD
VALASZ:=(I=J)
 

4. feladat: Cserebere (18 pont)
 
Egy automata a bemenetére érkező jelsorozatból bizonyos szabályok szerint képzett más jelsorozatot állít elő. Minden egyes szabályt egy-egy jelsorozat-pár ír le. A pár első tagja a helyettesítendő, a második tagja a helyettesítő jelsorozat. Egy lépésben az automata megvizsgálja, hogy van-e olyan szabály, amelynek első tagja illeszthető az átalakítandó jelsorozatra, s közülük az elsőt alkalmazza; ha a helyettesítendő jelsorozat több helyen is illeszkedik, a cserét balról az első helyen hajtja végre. Ezt a lépést addig ismétli, amíg van alkalmazható szabály (a hasonlítást újra az átalakítandó sorozat első elemétől kezdi).

Példa:

 
Bemenet: ARARAT
Szabályok: (ARA,BA), (BB,BO)
Lépések: ARARAT -> BARAT -> BBAT -> BOAT
Kimenet: BOAT
Add meg az alábbi feladatok mindegyikéhez a lehető legkevesebb szabályból álló megoldást! (A betűk mellett az = és a + is része a jelsorozatoknak. A darabszám azt jelenti, hogy az adott jelek számát előre nem ismerjük, a megoldásnak az összes ilyen szerkezetű jelsorozatra működnie kell.)
 
Bemenet Kimenet
A. AAABB= 
(n db A, k db B)
=CCCCC
(n+k db C)
B. CABCCBAAB=+
(n db A, n db B és n db C)
AAA=BBB+CCC 
(a betűk száma változatlan)
C. AAAABBBBBABA
(n db A és B tetszőlegesen összekeverve)
ABABABABABAB
(a betűk száma változatlan)

5. feladat: Speciális mátrixok (16 pont)

Egy speciális kitöltésű N*N-es mátrixot tömörítve például egy vektorral és egy függvénnyel ábrázolhatunk. A mátrixban az azonos betűk azonos értékű elemeket jelölnek, * jelöli azokat az elemeket, amelyek értéke közömbös, mert a felhasználásukra sohasem kerül sor. A mátrix bal felső elemének indexe (1,1). A vektorban az azonos betűvel jelölt azonos értékű elemek közül csak egyet tárolunk, a *-gal jelölt közömbös értékű elemeket pedig nem tároljuk. A vektor elemeit 1-től indexeljük. A függvény a mátrix egy indexpárját a vektor egy indexére képezi le.
Példa:
A mátrix:  A vektor:  A függvény: Index(I,J):=I

Az alábbi négy feladat megoldására készíts egy-egy aritmetikai kifejezésből álló olyan függvényt, amely kiszámítja a mátrix I. sorának J. oszlopában levő elem vektorbeli indexét!

A. feladat
B. feladat
C. feladat
D. feladat
d e f g
c d e f
b c d e
a b c d
a b c d
b c d e
c d e f
d e f g
a b * *
c d e *
* f g h
* * i j
a b d g
* c e h
* * f i
* * * j
(a b c d e f g)
(a b c d e f g h i j)


6. feladat: Ablakok (27 pont)

Az a vektorban n db téglalap alakú ablak képernyő-koordinátáit tároljuk. a-ban takarási sorrendben vannak az ablakok: a[1]-ben a legalsó, a[n]-ben a legfelső. Egy téglalapot négyelemű vektorral adunk meg az ábrán látható módon. Az x téglalap “üres”, azaz nincs kirajzolandó pontja, ha x[0]>x[2] vagy x[1]>x[3].

A következő programrésznek az a feladata, hogy a képernyőn az x téglalappal megadott területet, amely egy vagy több ablaknak lehet része, frissítse. (Egy pontot (pixelt) csak egyszer gyújt ki. Így villogásmentes és gyors lesz a rajzolás.) Frissít(x,m) kirajzolja az a[m] ablaknak az x téglalappal közös pontjait.
 
R(x,m):
  Ha m>0 akkor
    k:=1: Frissít(x,m)
    Ciklus i=0-tól 3-ig
      h:=x: k:=-k
      Ha k=1 akkor ertek:=max(h[(i+2) mod 4],a[m][i]+k)
      különben ertek:=min(h[(i+2) mod 4],a[m][i]+k)
      h[(i+2) mod 4]:=ertek
      R(h,m-1): k:=-k
      Ha k=1 akkor ertek:=max(x[i],a[m][i])
      különben ertek:=min(x[i],a[m][i])
      x[i]:=ertek
      k:=k*(1-(i mod 2)*2)
    Ciklus vége
  Elágazás vége
Eljárás vége.

A k,i,h,ertek az R lokális változói.

A. Az m. ablak vizsgálata közben, a ciklusmagba belépve, hogyan változik a k értéke? Az a[m] ablakhoz képest milyen területek frissítésére kerül sor k értékétől függően?
B. Az ábra segítségével rajzold le, hogyan változik az x paraméter által megadott terület az m. ablak vizsgálata közben, ha az a[m] teljes egészében része az x-nek! (Az ábrán az m. ablak az 5-össel jelölt mező, az x kezdetben pedig mind a kilenc mező.)
C. Mi történik, ha valamelyik lépésben az m. ablaknak és a frissítendő x területnek nincs közös része?
D. Mi lesz x-ben a ciklusból kilépve?
E. Hogyan lehetne az m>0 feltételen változtatva gyorsítani az algoritmuson?

Elérhető összpontszám: 100 pont