Szlávi Péter: A LOGO függvénykezelése

Szlávi Péter: A LOGO függvénykezelése Alapok Általános feladat: fogalmazzuk meg a kitűzött függvényt - matematikai formalizmussal, rekurzívan, majd - kódoljuk LCN LOGO-ban! A. Egyszerű matematikai függvények: 1. N_alatt_a_K (b(n,k)) Definíció: b(n,k):=1, ha n=
Próbák: b 2 3 b 9 9

eredménye: 1 eredménye: 1

b 9 0 b 4 2

eredménye: 1 eredménye: 6

2. Legnagyobb közös osztó (lnko(x,y)) Definíció: lnko(x,y):=lnko(x-y,y), ha x>y lnko(x,y):=x, ha x=y lnko(x,y):=lnko(x,y-x), ha x
eredménye: 12 eredménye: 1

lnko 36 24 lnko 13 13

B. A hiányzó sorozatkezelő függvények pótlása: Jelölési konvenció: - l : egy sorozat, - e : a sorozat egy eleme. 1. Utolsó (first párja: last) Definíció: last(l):=Első(l), ha EgyElemű(l) last(l):=last(ElsőUtáni(l)), különben Megoldás: MAKE egyelemű FUNC WITH l empty? butfirst l MAKE last FUNC WITH l IF egyelemű l THEN first l ELSE last butfirst l

eredménye: 12 eredménye: 13

Próbák: [A szavakat, azaz a karakterek sorozatát sorozataként tekinteni az explode függvény segítségével lehet.] last explode "abc eredménye: ~c [a c betű!] last explode 123 eredménye: ~3 [a 3 jel!] last "[a b c] eredménye: c [a c szó] 2. Utolsó nélkül (butfirst párja: butlast) Definíció: butlast(e,l):=Üres, butlast(e,l):=Elejére(Első(l),ElsőUtáni(l)),

ha EgyElemű(l) különben

Megoldás: MAKE butlast FUNC WITH l IF empty? butfirst l THEN "[] ELSE fput first l butlast butfirst l Próbák: butlast "[] eredménye: "[] butlast "[abc def gh i] eredménye: "[abc def gh] 3. Sorozat végéhez fűzés (fput párja: lput) Definíció: lput(e,l):=[e], ha Üres(l) lput(e,l):=Elejére(Első(l),lput(e,ElsőUtáni(l)), különben Megoldás: MAKE lput FUNC WITH e l IF empty? l THEN makelist e ELSE fput first l lput e butfirst l Próbák: lput "a eredménye: "[a] lput "b "[] "[a] lput "c eredménye: "[a b c] lput "b "[a]

eredménye: "[a b]

4. Sorozat N. eleme hátulról (nfirst párja: nlast) Definíció: nlast(n,l):= ... hf. ... Megoldás: MAKE nlast FUNC WITH n l ....... hf. ....

Próbák: nlast 1 eredménye: "[a] "[[a]]

nlast 3 "[a b c]

eredménye: a

5. Sorozat hátulról N. elemét kihagyja (nremove párja: nlremove) Definíció: nlremove(n,l):= ... hf. ... Megoldás: MAKE nlremove FUNC WITH n l ....... hf. .... Próbák: nlremove 1 eredménye: "[] "[[a]] nlremove 3 eredménye: "[b c] "[a b c] 6. Sorozat hossza (length) Definíció: length(l):=0, length(l):=1+length(ElsőUtáni(l),

ha Üres(l) egyébként

Megoldás: MAKE length FUNC WITH l IF equal? l THEN 0 ELSE sum 1 length butfirst l Próbák: length "[[a b c]] eredménye: 1 length "[a b c] eredménye: 3

Programozási tételek Általános feladat: fogalmazzuk meg a kitűzött programozási tételt - matematikai formalizmussal, rekurzívan, majd - kódoljuk LCN LOGO-ban! 1. Összegzés tétel (szumma(l)) Definíció: szumma(l):=0, szumma(l):=Első(l)+szuma(ElsőUtáni(l)),

ha Üres(l) egyébként

Megoldás: MAKE szumma FUNC WITH l IF empty? l THEN 0 ELSE sum first l szumma butfirst l Próbák: szumma "[1 2 3 4 5 6 7 8 9] szumma "[] 2. Akkumulációs tétel (akkumuláció(fvk,neut,fvb,l)) Definíció: akkumuláció(fvk,neut,fvb,l):=neut, ha Üres(l) akkumuláció(fvk,neut,fvb,l):= fvk(fvb(Első(l),akkumuláció(fvk,neut,fvb,ElsőUtáni(l))),

különben

Megoldás: MAKE akkumuláció FUNC WITH fvk neut fvb l IF empty? l THEN neut ELSE fvk fvb first l akkumuláció fvk neut fvb butfirst l Próbák: Az egyszerű összegzés kipróbálásához szükséges egy "identikus függvény": paramétertovábbításhoz MAKE iden FUNC WITH l l Az összegzés: akkumuláció sum iden 0 "[1 2 3 4 5 6] A produktum:

akkumuláció product iden 1 "[1 2 3 4 5 6] A skalárszorzáshoz szükséges egy "komponenspár-szor-zó" függvény: MAKE szorzattag FUNC WITH l product first l nfirst 2 l A skalárszorzás: akkumuláció sum szorzattag 0 "[[2 2]] akkumuláció sum szorzattag 0 "[[1 1] [2 2] [3 3] [4 4] [5 5]] 3. Eldöntés tétel (eldönt(tul?,l):Logikai) Definíció: eldönt(tul?,l):=Hamis, ha Üres(l) eldönt(tul?,l):=Igaz, ha tul?(Első(l)) eldönt(tul?,l):=eldönt(tul?,ElsőUtáni(l)), különben Megoldás: MAKE eldönt? FUNC WITH tul? l IF empty? l THEN "FALSE ELSE IF tul? first l THEN "TRUE ELSE eldönt? tul? butfirst l Próbák: eldönt? empty? "[[1] [2]] Páros számot tartalmaz-e a sorozat? Ehhez a párosságvizsgálatot eldöntő függvény kell: MAKE páros? FUNC WITH x equal? rest x 2 0 Van-e páros? eldönt? páros? "[] eldönt? páros? "[1 3 5 7] eldönt? páros? "[1 2 3] 4. Keresés tétel (keres(tul?,l):[Logikai Sorszám]) Probléma, hogy miként lehet egy rekurzív filozófiájú megoldásban (amelynek alaptrükkje éppen az, hogy a további vizsgálatot egy rövidített sorozattal folytatja) megőrizni az érték egy komponenseként visszaadandó aktuális elem

sorszámát. A megoldás egy plusz paraméter, amely minden rekurzív hívásnál növekszik eggyel, vagyis a vizsgált elemsorszámmal azonos értékű. (Kezdetben 1ről indul.) Definíció: keres(l,sorsz):=[Hamis bármi], keres(l,sorsz):=[Igaz sorsz], keres(l,sorsz):=keres(ElsőUtáni(l),sorsz+1),

ha Üres(l) ha tul?(Első(l)) különben

Megoldás: A megoldást célszerű két lépésben végezni, mivel a keresés közben a megvizsgált elemek számát is nyilván kell tartani, s ezt a többletadminisztrációt nem indokolt a hívás egy pluszparaméteré-vel bonyolítani. Ezért az első függvény mindössze a szük-séges pa-raméterek átvételét, ill. ezek továbbítását végzi, természetesen a többlet-számláló paraméter kezdőértékének beál-lításával együtt. MAKE keres FUNC WITH tul? l keres_n tul? l 1 MAKE keres_n FUNC WITH tul? l n IF empty? l THEN makelist "FALSE n ELSE IF tul? first l THEN makelist "TRUE n ELSE keres_n tul? butfirst l sum n 1 Megjegyzés: érdemes elgondolkodni másik megoldáson is, ami a többletparaméter nélkül oldja meg ugyanezt! Próbák: keres empty? "[[1] [2] [] [4]] keres empty? "[[1] [2] [3] [4]] 5. Megszámolás tétel (megszámol(tul?,l): Egész) Definíció: megszámol(l):=0, ha Üres(l) megszámol(l):=1+megszámol(ElsőUtáni(l)), ha tul?(Első(l)) megszámol(l):=megszámol(ElsőUtáni(l)), különben Megoldás: MAKE megszámol FUNC WITH tul? l IF empty? l THEN 0 ELSE IF tul? first l THEN sum 1

megszámol butfirst l ELSE megszámol butfirst l Próbák: megszámol empty? "[[1] [2] [3]] megszámol empty? "[[] [2] [3]] 6. Maximumkiválasztás tétel (max(l): Sorszám) Definíció: max(l):=Első(l), max(l):=Első(l), max(l):=max(ElsőUtáni(l)),

ha EgyElemű?(l) ha Első(l)>max(ElsőUtáni(l)) különben

Megoldás: MAKE max FUNC WITH l IF egyelemű? l THEN first l ELSE IF greater? first l max butfirst l THEN first l ELSE max butfirst l Próbák: maximum "[1] maximum "[1 2 3] maximum "[3 2 1 5 4] 7. Maximumkiválasztás tétel általánosítása (ált_max(nagyobb?,l): Sorszám) Definíció: ált_max(l):=Első(l), ált_max(l):=Első(l),

ha EgyElemű(l)_ ha nagyobb?(Első(l), ált_max(ElsőUtáni(l))) ált_max(l):=ált_max(ElsőUtáni(l)), különben

Megoldás: MAKE ált_max FUNC WITH nagyobb? l IF egyelemű l THEN first l ELSE IF nagyobb? first l ált_max nagyobb? butfirst l THEN first l ELSE ált_max nagyobb ? butfirst l Próbák: A rendezési relációt pl. a síkon az euklideszi normával definiálhat-juk. Ehhez célszerű egy sikbeli pont normájának kiszámolását is önálló függvénnyel megvalósítani: MAKE norma FUNC WITH x sum product first x first x product last x

last x MAKE nagyobb2D? FUNC WITH x y IF greather? norma x norma y A síkbeli pontok sorozatának legnagyobbika: ált_max nagyobb2D? "[[1 2] [3 4] [5 6] [7 8]] 8. Kiválogatás tétel (kiválogat(tul?,l): Sorozat) Definíció: kiválogat(l):=Üres, ha Üres(l) kiválogat(l):=Elejére(Első(l),kiválogat(ElsőUtáni(l))), ha tul?(Első(l)) kiválogat(l):=kiválogat(ElsőUtáni(l)), különben Megoldás: MAKE kiválogat FUNC WITH tul? l IF empty? l THEN l ELSE IF tul? first l THEN fput first l kiválogat tul? butfirst l ELSE kiválogat tul? butfirst l Próbák: A kiválogatáshoz definiálandó a tul? függvény. Most az egyszerű-ség kedvéért e célra az empty? függvényt fogjuk fölhasználni. Źgy a vizsgált sorozat sorozatok sorozata lesz. kiválogat empty? eredménye: "[] "[[1] [2] [3 4] [5 6 7] [8]] kiválogat empty? eredménye: "[[ ] [ ]] "[[1] [ ] [2] [ ] [3 4] [[ ] [ ]] [5 6] [7 8]] 9. 'Rendezés maximumkiválasztással' tétel (max_rend(l): Sorozat) Definíció: max_rend(l):=Üres, ha Üres(l) max_rend(l):=Elejére(max(l) max_rend(maxnélkül(l))), különben ahol max(l):= ld. korábban maxnélkül(l):= hf. Megoldás: MAKE max_rend FUNC WITH l ...... hf. ..... Próbák: A rendezéshez definiálandók: max és maxnélkül

Fák Általános feladat: fogalmazzuk meg a kitűzött fákkal kapcsolatos függvényt - matematikai formalizmussal, rekurzívan, majd - kódoljuk LCN LOGO-ban! A. Keresésőfák: 1. Egy sorozatból hozzunk létre keresőfát! Definíció: kf(s):=s, kf(s):=[kf(ks) e kf(nk)],

ha Üres(s) egyébként ahol e:=Középső(s), ks:=Kisebbek(s) nk:=NemKisebbek(s)

Megoldás: MAKE kf FUNC WITH s IF empty? s THEN s ELSE makelist kf kisebbek s first s kf nemkisebbek s MAKE kisebbek FUNC WITH s IF empty? butfirst s THEN "[] ELSE IF greater? first s nfirst 2 s THEN fput nfirst 2 s kisebbek nremove 2 s ELSE kisebbek nremove 2 s Megjegyzések: - Hasonló a 'nemkisebbek' függvény is. - Nyilván ennél a megoldásnál lényegesen hatékonyabbat is el lehet készíteni "belső, közvetítő" függvény felhasználásával. Próbák: kf "[] kf "[1 2 3] kf "[2 1 3]

eredménye: "[] eredménye: "[[] 1 [[] 2 [[] 3 []]]] eredménye: "[[[] 1 []] 2 [[] 3 []]]

2. Egy keresőfából hozzunk létre rendezett sorozatot! Definíció: bkj(kf):=kf, ha Üres(kf) bkj(kf):=bkj(Első(kf)) [Középső(kf)] bkj(Utolsó(kf)), különben ahol Középső(kf):=Elem(kf,2), Utolsó(kf):=Elem(kf,3)

Megoldás: MAKE bkj FUNC WITH kf IF empty? kf THEN kf ELSE sentence bkj first kf makelist középső kf bkj last kf MAKE középső FUNC WITH kf nfirst 2 kf A last ld. korábban, vagy most rövidebben: nfirst 3 kf! Próbák: bkj bkj bkj bkj

"[] "[[] 1 []] "[[[] 1 []] 2 [[] 3 []]] kf "[1 2 3]

eredménye: eredménye: eredménye: eredménye:

"[] "[1] "[1 2 3] "[1 2 3]

3. Keresés keresőfában A feladat pontos megfogalmazására két lehetőség is logikusnak látszik. Az el-ső mindössze a keresett bentlétrére ad választ. A másodikban a logikai érté-ken túl, azt a részfát is visszaadja, amelyiknek gyökere a keresett. 1. Definíció: keres(kf,e):=Hamis, keres(kf,e):=Igaz, keres(kf,e):=keres(Első(kf),e), keres(kf,e):=keres(Utolsó(kf),e),

ha Üres(kf) ha e=Középső(kf) ha e
Megoldás: MAKE keres FUNC WITH kf e IF empty? kf THEN "FALSE ELSE IF equals? e középső kf THEN "TRUE ELSE IF less? e középső kf THEN keres first kf e ELSE keres last kf e Próbák: keres "[] 1 keres "[[] 1 []] 1 keres "[[[] 1 []] 2 [[] 3 []]] 1

eredménye: "FALSE eredménye: "TRUE eredménye: "TRUE

2. Definíció: keres(kf,e):=Üres, keres(kf,e):=kf, keres(kf,e):=keres(Első(kf),e), keres(kf,e):=keres(Utolsó(kf),e),

ha Üres(kf) ha e=Középső(kf) ha e
Megoldás: MAKE keres FUNC WITH kf e IF empty? kf THEN "[] ELSE IF equal? e középső kf THEN kf ELSE IF less? e középső kf THEN first kf ELSE utolsó kf Próbák: keres "[] 1 keres "[[[] 2 []] 1 []] 2 keres "[[[] 1 []] 2 [[] 3 []]] 1

eredménye: "[] eredménye: "[[] 2 []]] eredménye: "[[] 1 []]]

B. Fák diagnosztikája: 1. Hány szintes a fa? Definíció: szintszám(fa):=0, ha Üres(fa) szintszám(fa):=max(szintszám(Első(fa))+ szintszám(Utolsó(fa))+1, különben Megoldás: MAKE szintszám FUNC WITH fa IF empty? fa THEN 0 ELSE sum max szintszám first fa szintszám last fa 1 MAKE max FUNC WITH x y IF greater? x y THEN x ELSE y Próbák: szintszám "[] szintszám "[[[] 1 []] 2 []]

eredménye: 0 eredménye: 1

2. Hány elemű a fa? Definíció: pontszám(fa):=0, pontszám(fa):=pontszám(Első(fa)) + + 1 + + pontszám(Utolsó(fa)),

ha Üres(fa) különben

Megoldás: MAKE pontszám FUNC WITH fa IF empty? fa THEN 0 ELSE sum pontszám first fa sum 1 pontszám first fa Próbák: pontszám "[] pontszám "[[] 1 []] pontszám "[[] 1 [[[] 1 []]]]

eredménye: 0 eredménye: 1 eredménye: 2

3. Kiegyensúlyozott-e? Definíció: kiesfa(fa):=fa, kiesfa(fa):= hf.,

ha Üres(fa) ha ...(fa)

Megoldás: MAKE kiesfa FUNC WITH fa IF empty? fa THEN fa ........ hf. ....... Próbák: kiesfa "[]

eredménye: "[]

Gyakorló feladatok

Szöveges feladatok: 1. Első szó MAKE elsoszo FUNC WITH mondat first mondat 2. Első betű MAKE elsobetu FUNC WITH mondat first explode elsoszo mondat 3. Utolsó szó MAKE utolsoszo FUNC WITH mondat last mondat 4. Utolsó betű MAKE utolsobetu FUNC WITH mondat last explode utolsoszo mondat 5. Ciklikus léptetés szavanként balra MAKE balralep FUNC WITH mondat lput first mondat butfirst mondat 6. Ciklikus léptetés szavanként jobbra MAKE balralep FUNC WITH mondat fput last mondat butlast mondat 7. Mondat szavai sorrendjének megfordítása MAKE fordit FUNC WITH mondat IF empty? mondat THEN mondat ELSE lput first mondat fordit butfirst mondat 8. Mondat szavai, s betűi sorrendjének megfordítása MAKE befordit FUNC WITH mondat IF empty? mondat THEN mondat ELSE lput implode fordit explode first mondat befordit butfirst mondat

_) Az egyelemű függvény LOGO megvalósítását ld. korábban!