Nemes Tihamér OKSzTV'98

1. feladat: Karikák (15 pont)

Az alábbi Logo programok köröket rajzolnak különböző elrendezésben.

A következőkben felsoroljuk a használható utasításokat.
 

kör 10	10 egység sugarú kört rajzol, az aktuális pontot véve középpontnak. A rajzolás elején a teknőc északi irányba néz, a toll a levegőben van, a kör eljárás a körvonal rajzolása előtt leteszi a tollat, a végén pedig újra felemeli. Rajzolás után a teknőc visszaáll eredeti pozíciójába és irányába.
előre t	hatására a teknőc az aktuális irányba előre lép t egységgel
jobbra sz	hatására pedig jobbra fordul sz fokkal
ismétlés db [utasítások]	hatására a zárójelbe tett utasításokat :db-szer megismétli

 

elágazás	ha feltétel [az akkor ág utasításai]
eljárás	tanuld eljárásnév :paraméter   utasítások vége

Melyik program mit rajzol?
 

A.	tanuld nta :db   ha :db > 0     [ismétlés 2      [ismétlés :db [kör 10 előre 20]      jobbra 90]      nta :db - 1     ] vége
B.	tanuld ntb :db   ha :db > 0     [ismétlés :db [kör 10 előre 20]      jobbra 120 ntb :db - 1     ] vége
C.	tanuld ntc :db   ha :db > 0      [ismétlés 3      [ismétlés :db - 1 [kör 10 előre 20]       kör 10 jobbra 60 előre 20]      ntc :db-1     ] vége

Az A és B halmazok egész számokat tartalmaznak. Használni fogjuk a következő utasításokat:
 

nemüres(H)	igaz, ha a halmazban van elem
üreshalmaz	üres halmazt ad eredményül
eleme(e,H)	igaz, ha az e elem benne van a H halmazban
egyeleme(H)	a H halmaz egy tetszőleges eleme
berak(e,H)	az e elemet berakja a H halmazba
kivesz(e,H)	kiveszi az e elemet a H halmazból

Az alábbi algoritmusokban a legalább N+1 elemű, 1-től indexelt X vektor egy tizedes tört törtrészének számjegyeit tartalmazza. Például 0.75 esetén X(1)=7, X(2)=5.
 

Első(I):   Ha I=N+1 akkor Ha X(I)>5 akkor X(I-1):=X(I-1)+1   Ha I<N+1 akkor Első(I+1)   Ha X(I)>9 akkor X(I):=0   X(I-1):=X(I-1)+1 Eljárás vége.

Második(I):   Ha I=N+1 akkor X(I-1):=X(I-1)+1   Ha I<N+1 akkor Második(I+1)   Ha X(I)>9 akkor X(I):=0   X(I-1):=X(I-1)+1 Eljárás vége.

Harmadik(I):   Ha I=N+1 akkor X(I-1):=10-X(I-1)   Ha I<N+1 akkor Harmadik(I+1): X(I-1):=9-X(I-1) Eljárás vége.

A. Mit csinál a fenti három algoritmus, ha az I=1 értékkel hívjuk meg, s N értéke 10?
B. Tetszőleges N esetén bizonyos esetekben hibásan működnek. Milyen X vektorok esetén?

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:

Adott egy N*M-es A mátrix:

A mátrix milyen elhelyezkedésű elemének indexeit adják meg kimenő paraméterként az alábbi algoritmusok?
Rajzold le a keresési irányt!
Mikor működnek hibásan?
 

AKeres(I,J):   I:=1: J:=1   Ciklus amíg A[I,J]<>0     Ha J<M akkor J:=J+1 különben I:=I+1: J:=1   Ciklus vége Eljárás vége.

BKeres(I,J):   I:=1: J:=M   Ciklus amíg A[I,J]<>0     Ha I<N akkor I:=I+1 különben J:=J-1: I:=1   Ciklus vége Eljárás vége.

CKeres(I,J):   I:=N: J:=M   Ciklus amíg A[I,J]<>0     Ha J>1 akkor J:=J-1 különben I:=I-1: J:=M   Ciklus vége Eljárás vége.

A Sötét Erdő rablói minden útelágazásnál és minden ösvény végén pénzt rejtettek el. Az erdőbe pontosan egy út vezet, az út minden elágazásnál két irányban folytatódik. Az alábbi programrészletben az A 2N-1-1 elemű tömb, az S 2N-1 elemű tömb és az N érték a függvények bemenő paraméterei.
 

f1(A,S,N):   p:=1: z:=S[p]   Ciklus i=1-től N-1-ig     Ha A[p] akkor p:=2*p különben p:=2*p+1     z:=z+S[p]   Ciklus vége   f1:=z Függvény vége.

f2(S,N):   p:=1: q:=S[p]   Ciklus i=2-től 2^N-1-ig     Ha S[i]>q akkor p=i: q:=S[i]   Ciklus vége   z:=0   Ciklus amíg p>1     z:=z+1: p:=p div 2   Ciklus vége   f2:=z Függvény vége.

Elérhető összpontszám: 100 pont