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:
|
|
|
|
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égeCiklus 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?
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 FIA 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 ODMit 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 ODB. {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)
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:
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: ARARAT Szabályok: (ARA,BA), (BB,BO) Lépések: ARARAT -> BARAT -> BBAT -> BOAT Kimenet: BOAT
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):=IAz 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!
|
|
|
|
c d e f b c d e a b c d |
b c d e c d e f d e f g |
c d e * * f g h * * i j |
* c e h * * f i * * * j |
|
|
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?