Algoritmizálás Horváth Gyula Szegedi Tudományegyetem Természettudományi és Informatikai Kar
[email protected]
2.
Rekurzió
2.1.
Feladat: Sorbaállítások száma
Hány féleképpen lehet sorbaállítani az osztály tanulóit? Bemenet: a tanulók n száma. Kimenet: ahány félekeppen az n tanuló sorbaállítható.
Megoldás Jelölje P(n) a megoldás értékét n tanuló esetén. A Tanulókat az 1, . . . , n számokkal azonosítjuk. P(1) = 1 Visszavezés kisebb méret˝u, ugyanilyen probléma megoldására. Tekitsük azokat a sorbaállításokat, amelyek esetén az n-edik tanuló a sorban az els˝o helyen áll, és jelöljük ezek számát S(1, n)-el. Általában, jelölje S(i, n) azon sorbaállítások számát, ahol az n sorszámú tanuló a sorban az i-edik helyen áll. Tehát P(n) = S(1, n) + S(2, n) + · · · + S(n, n) Nyilvánvaló, hogy S(1, n) megegyezik n − 1 tanuló összes lehetséges sorbaállításának számával, tehát S(1, n) = P(n − 1). Általában, azon sorbaállítások száma, ahol az n-edik tanuló a i-edik helyen áll, P(n − 1). Tehát, ha n > 1, akkor P(n) = n ∗ P(n − 1) P(n) = n ∗ (n − 1) ∗ · · · ∗ 2 ∗ 1 1 2 3
P:=1; f o r i :=2 t o n do P:=PΛn ;
2.2.
Feladat: Zsebpénz
n Euro zsebpénzt kaptunk. Minden nap veszünk pontosan egy dolgot a következ˝ok közül (zárójelben az ár szerepel) perec (1 Eu), fagylalt (2 Eu), csoki (2 Eu). Számítsuk ki, hogy hányféleképpen költhetjük el a zsebpénzünket!
Megoldás Jelölje K(n) az n Eu lehetséges elköltéseinek a számát. A következ˝o összefüggések állnak fenn: • K(1) = 1 (csak egy perecet vehetünk) • K(2) = 3 (vagy két perecet, vagy egy csokit, vagy egy fagyit vehetünk) • K(n) = K(n − 1) + 2K(n − 2) ha n ≥ 3, (els˝o alkalommal perecet, csokit vagy fagylaltot vehetünk). A következ˝o algoritmus adja meg a K(n) függvényt:
1
1 2 3 4 5 6 7 8 9
f u n c t i o n K( n : i n t e g e r ) : i n t 6 4 ; begin i f n=1 t h e n K: =1 e l s e i f n=2 t h e n K: =3 else K:=K( n−1)+2ΛK( n −2); end {K} ;
2.3.
A rekurzió gyökerei:Peano axiómák
1. 0 ∈ N (A 0 természetes szám ) 2. S(x) 6= 0 (A 0 nem rákövetkez˝oje egyetlen természetes számnak sem) 3. S(x) = S(y) ⇒ x = y 4. Ha M ⊆ N és 0 ∈ M és ∀x(x ∈ M ⇒ S(x) ∈ M) akkor M = N (Indukció axióma) 5. x + 0 = x 6. x + S(y) = S(x + y) Az S(0) = 1 jelölést használva, x + 1 = x + S(0) = S(x + 0) = S(x) Az 5. és 5. axiómák egy rekurzív algoritmust adnak az 1-es számrendszerbeli összeadásra. Az a + b összeg kiszámításának (rekurzív) algoritmusa: Vegyünk a darab kavicsot a bal kezünkbe, b darab kavicsot a jobb kezünkbe. Ha a jobb kezünk üres, akkor az eredmény a bal kezünkben van (5. axióma). Egyébként, ( b = S(b) = b + 1 valamely b-ra) tegyünk félre 1 kavicsot a jobb kezünkb˝ol adjuk össze (ezen algoritmussal) a két kezünkben lév˝o kavicsokat tegyük a bal kezünkbe az 1 félretett kavicsot A szorzás rekurzív megadása x·0 = 0
x · S(y) = x + x · y
2.4.
Feladat: Eldöntend˝o, kinek van több birkája
Két szomszédos gazda vitatkozik, hogy kinek van több birkája. Adjunk algoritmust a vita eldöntésére! A < (lineáris) rendezési reláció rekurzív megadása 0 < S(x) ¬(x < 0)
S(x) < S(x) ⇔ x < y
2
2.5.
Feladat: Partíciószám
Definíció. Az n természetes szám egy partíciója olyan π = ha1 , · · · , ak i sorozat, amelyre: • a1 ≥ a2 ≥ · · · ≥ ak > 0 • ∑ki=1 ai = n (ai a π partíció része.) Jelölje P(n) n összes partíciójának számát. Probléma: Partíciószám Bemenet: n Kimenet: n partícióinak száma, P(n) Megoldás Jelölje P2(n, k) n azon partícióinak számát, amelyben minden rész ≤ k. Összefüggések: 1. P2(1, k) = 1, P2(n, 1) = 1 2. P2(n, n) = 1 + P2(n, n − 1)
3. P2(n, k) = P2(n, n) ha n < k
1 2 3 4 5 6 7 8 9 10 11 12 13
4. P2(n, k) = P2(n, k − 1) + P2(n − k, k) ha k < n A megoldás: P(n) = P2(n, n) function P(n: integer ) : int64 ; f u n c t i o n P2 ( n , k : i n t e g e r ) : i n t 6 4 ; begin i f ( n =1) or ( k =1 ) t h e n P2 :=1 e l s e i f k>=n t h e n P2 :=1+ P2 ( n , n−1) else P2 := P2 ( n , k−1)+P2 ( n−k , k ) ; end { P2 } ; begin P:= P2 ( n , n ) ; end {P} ; Rekurziós fa fogalma. Olyan fa, amelynek minden pontja egy eljáráshívást jelent adott aktuális paraméterekre, úgy, hogy a pont fiai megfelelnek azoknak az eljáráshívásoknak, amelyek végrehajtódnak az aktuális paraméterek esetén.
Rekurzív algoritmus helyességének bizonyítása I. Terminálás bizonyítása Bebizonyítandó, hogy minden eljáráshívás végrehajtása véges lépésben befejez˝odik. (Az eljárás terminál.) Terminálás bizonyítása megállási feltétellel. Megállási feltétel Legyen P(x1 , . . . , xn ) n-paraméteres rekurzív eljárás. A M(x1 , . . . , xn ) kifejezés megállási feltétele a P rekurzív eljárásnak, ha 1. M(a1 , . . . , an ) ≥ 0 minden megengedett a1 , . . . , an aktuális paraméterre.
2. Ha M(a1 , . . . , an ) = 0 akkor nincs rekurzív hívás P(a1 , . . . , an ) végrehajtásakor. 3. Ha van rekurzív hívás P(a1 , . . . , an ) végrehajtásakor valamely b1 , . . . , bn paraméterekre, akkor M(b1 , . . . , bn ) < M(a1 , . . . , an )
Állítás: M(n, k) = (n − 1) × (k − 1) megállási feltétel P2-re. II. Helyesség bizonyítása 1. Alaplépés. Annak bizonyítása, hogy az eljárás helyes eredményt számít ki, ha az aktuális paraméterek esetén nincs rekurzív hívás. 2. Rekurzív lépés. Feltéve, hogy minden rekurzív hívás helyes eredményt ad, annak bizonyítása, hogy a rekurzív hívások által adott értékekb˝ol az eljárás helyes eredményt számít ki. 3
5,1
+
1
2,3
3,2
3,1
5,4
1,4
+
1
+1
+
5,3
5,2
5,5
+
2,1
1,2
1
1
1
1. ábra. A P2(5, 5) eljáráshívás rekurziós fája
2.6.
Feladat: Hanoi tornyai
A hanoi torony probléma: Három pálca egyikén n korong van a többi üres. A korongok nagyság szerinti sorrendben helyezkednek el, alul van a legnagyobb. Át akarjuk helyezni a korongokat egy másik pálcára a következ˝o szabályok alapján. Egyszerre csak egy korong mozgatható. A korong vagy üres pálcára vagy egy nála nagyobb korongra helyezhet˝o. Oldjuk meg a feladatot egy rekurzív algoritmussal! Határozzuk meg a korongmozgatások számát!
Megoldás Legyen a hanoi eljárás egy olyan algoritmus, amelynek három argumentuma van, az els˝o argumentum azt adja meg, hogy hány korongot helyezünk át, a második megadja, hogy melyik toronyról a harmadik, hogy melyik toronyra. Ekkor az eljárás az (n, 1, 2) argumentummal megoldja a feladatot. Amennyiben i − 1 korongot már át tudunk helyezni, i korongot a következ˝oképpen helyezhetünk át. Els˝oként i − 1 korongot áthelyezünk az oszlopról egy másik oszlopra. Utána az i-edik korongot rárakjuk a kimaradó üres oszlopra. Végül ezen korong tetejére felrakjuk az i − 1 korongot. Ezt a rekurziót írja le a következ˝o eljárás (a megengedett lépést a mozgat függvény írja le, az argumentumai, hogy honnan hova) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
p r o c e d u r e mozgat ( r o l , ra : I n t e g e r ) ; b e g i n { mozgat } w r i t e l n ( r o l , ’ −> ’ , ra ) ; end { mozgat } ; p r o c e d u r e h a n o i ( n , r o l , ra : i n t e g e r ) ; begin { hanoi } i f ( n =1) t h e n mozgat ( r o l , ra ) e l s e begin h a n o i ( n−1 , r o l , 6−r o l −ra ) ; mozgat ( r o l , ra ) ; h a n o i ( n−1 , 6−r o l −ra , ra ) ; end end { h a n o i } ; Lépések száma: Az i-edik korong átrakásához kétszer kell i − 1 korongot áthelyezni és egy további mozgatás szükséges. Tehát T (i)-vel jelölve az i korong átrakásához szükséges mozgatások számát a T (i) = 2T (i − 1) + 1 rekurzív összefüggés áll fenn. T (1) = 1, így T (2) = 3, T (3) = 7. Azt sejthetjük, hogy T (i) = 2i − 1, amely egyenl˝oség teljes indukcióval egyszer˝uen igazolható.
4
2.7.
Feladat: Pénzválás
Bemenet: P = {p1 , ..., pn } pozitív egészek halmaza, és E pozitív egész szám. Eldöntend˝o, hogy van-e olyan S ⊆ P, hogy ∑ p∈S = E. Megjegyzés: A pénzek tetsz˝oleges címletek lehetnek, nem csak a szokásos 1, 2, 5 10, 20, stb., és minden pénz csak egyszer használható a felváltásban.
Megoldás A megoldás szerkezetének elemzése. Tegyük fel, hogy E = pi1 + . . . + pik , i1 < . . . < ik egy megoldása a feladatnak. Ekkor E − pik = pi1 + . . . + pik−1
megoldása lesz annak a feladatnak, amelynek bemenete a felváltandó E − pik érték, és a felváltáshoz legfeljebb a els˝o ik − 1 (p1 , . . . , pik −1 ) pénzeket használhatjuk. Részproblémákra bontás. Bontsuk részproblémákra a kiindulási problémát: Minden (X, i)(1 ≤ X ≤ E, 1 ≤ i ≤ N) számpárra vegyük azt a részproblémát, hogy az X érték felváltható-e legfeljebb az els˝o p1 , . . . , pi pénzzel. Jelölje V (X, i) az (X, i) részprobléma megoldását, ami logikai érték; V (X, i) = Igaz, ha az X összeg el˝oállítható legfeljebb az els˝o i pénzzel, egyébként Hamis. Összefüggések a részproblémák és megoldásaik között. Nyilvánvaló, hogy az alábbi összefüggések teljesülnek a részproblémák megoldásaira: 1. V (X, i) = (X = pi ), ha i = 1 2. V (X, i) = V (X, i − 1) ∨ (X > pi ) ∧V (X − pi , i − 1) ha i > 1 Rekurzív megoldás. Mivel a megoldás kifejezhet˝o egy V(X,i) logikai érték˝u függvénnyel, ezért a felírt összefüggések alapján azonnal tudunk adni egy rekurzív függvényeljárást, amely a pénzváltás probléma megoldását adja. 1 2 3 4 5 6
f u n c t i o n V(X, i : i n t e g e r ) / / Globális :P begin V:= (X==P [ i ] ) or ( i >1) and ( V(X, i −1) or (X>P [ i ] ) and V(X−P [ i ] , i −1) ) ; end {V} ; Ez a megoldás azonban igen lassú, legrosszabb esetben a futási id˝o Ω(2n ).
5
2.8.
Feladat: Járdakövezés
Számítsuk ki, hogy hányféleképpen lehet egy 3 × n egység méret˝u járdát kikövezni 1 × 2 méret˝u lapokkal! Megoldás
2. ábra. Jelölje A(n) a megoldás értékét 3 × n egység méret˝u járda esetén. Az els˝o oszlop középs˝o négyzete háromféleképpen fedhet˝o le. Az egyes esetek csak az alábbi módon folytathatók:
3. ábra. 1. eset
4. ábra. 2. eset Jelölje B(n) azt, hogy hányféleképpen fedhet˝o le egy 3 × n egység méret˝u járda, amelynek a bal alsó sarka már le van fedve. Szimmetria miatt a jobb fels˝o sarok lefedettsége esetén is B(n)-féle lefedés van. 0 3 A(n) = A(n − 2) + 2B(n − 1) 1 0 B(n) = A(n − 1) + B(n − 2)
6
n=1 n=2 n>2
(1)
ha n = 1 ha n = 2 ha n > 2
(2)
ha ha ha
5. ábra. 3. eset
6. ábra. Az 1. eset csak így folytatható
7. ábra. A 2. eset csak így folytatható
8. ábra. A 3. eset csak így folytatható
9. ábra. Az 1. eset csak így folytatható
10. ábra. Az 2. eset csak így folytatható
7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
program j a r d a ; f u n c t i o n B ( n : i n t e g e r ) : l o n g i n t ; forward ; f u n c t i o n A( n : i n t e g e r ) : l o n g i n t ; begin i f ( n =1) t h e n A := 0 e l s e i f ( n = 2) t h e n A := 3 else A := A( n−2)+2ΛB ( n −1); end {A} ; f u n c t i o n B( n : i n t e g e r ) : l o n g i n t ; begin i f ( n =1) t h e n B := 1 e l s e i f ( n = 2) t h e n B := 0 else B := A( n−1)+B ( n −2); end {B} ; begin w r i t e l n (A ( 3 2 ) ) ; end .
A(6)41
+2*
+
A(4) 11
B(5) 15 +2*
+
A(2) 3
+
B(3) 4 +
A(2) 3
+
B(3) 4
A(4) 11 +
B(1) 1
+2* B(3) 4
+
A(2) 3
+
A(2) 3
+
A(2) 3
+
B(1) 1
+
B(1) 1
11. ábra. Rekurziós fa
2.9.
Feladat: Ördöglakat kinyitása
Az ördöglakat fém gy˝ur˝ukb˝ol összeállított szerkezet. Minden gy˝ur˝unek van szára, amelyet körbefog a sorrendben következ˝o gy˝ur˝u. Zárt állapotban a szárakat körbefogja egy fémb˝ol készült hurok. Az a cél, hogy a lakatot kinyissuk, azaz a hurkot eltávolítsuk. A gy˝ur˝uket balról-jobbra 1-t˝ol n-ig sorszámozzuk. Minden lépésben egy gy˝ur˝u vehet˝o le, vagy tehet˝o fel az alábbi két szabály betartásával. 1. Az els˝o gy˝ur˝u bármikor levehet˝o, illetve felrakható. 2. Minden i > 1 sorszámú gy˝ur˝u akkor és csak akkor vehet˝o le, illetve tehet˝o fel, ha az i − 1-edik gy˝ur˝u fent van, és minden i − 1-nél kisebb sorszámú gy˝ur˝u lent van. A lakat akkor van kinyitva, ha minden gy˝ur˝u lent van. Írjon olyan rekurzív eljárást, amely megadja lépések olyan sorozatát, amely kinyitja a lakatot!
Megoldás Részproblémákra bontás: MindLe(m) Leveszi az els˝o m gy˝ur˝ut (tetsz˝oleges sorrendben), a többit változatlanul hagyja. 8
Le(i) Leveszi az i. gy˝ur˝ut, minden j > i sorszámút változatlanul hagy. (A j < i sorszámúak helyzete akármilyen lehet a m˝uvelet után.) Fel(i) Felteszi az i. gy˝ur˝ut, minden j > i sorszámút változatlanul hagy. (A j < i sorszámúak helyzete akármilyen lehet a m˝uvelet után.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
program o r d o g l a k a t ; const maxN= 32 ; var l a k a t : a r r a y [ 1 . . maxN ] o f b o o l e a n ; i , n: integer ; p r o c e d u r e Le ( i : i n t e g e r ) forward ; p r o c e d u r e F e l ( i : i n t e g e r ) forward ; p r o c e d u r e MindLe (m : i n t e g e r ) ; var i : i n t e g e r ; begin f o r i :=m downto 1 do i f l a k a t [ i ] t h e n Le ( i ) ; end { MindLe } ; p r o c e d u r e Le ( i : i n t e g e r ) ; begin i f ( i >1 ) and n o t l a k a t [ i −1] t h e n F e l ( i −1); i f ( i >2 ) t h e n MindLe ( i −2); lakat [ i ]:= false ; w r i t e l n ( i , ’ . Le ’ ) ; end { Le } ; procedure Fel ( i : i n t e g e r ) ; begin i f ( i >1 ) and n o t l a k a t [ i −1] t h e n F e l ( i −1); i f ( i >2 ) t h e n MindLe ( i −2); lakat [ i ]:= true ; writeln ( i , ’ . Fel ’ ) ; end { F e l } ; begin n:=5; f o r i :=1 t o n do l a k a t [ i ] : = t r u e ; MindLe ( n ) ; end .
2.10.
Rekurzív görbék
2.11.
Feladat: Hópihe görbe rajzolás
Görbe leírása Lindenmayer rendszerrel Mag=F++F++F, F => F-F++F-F, alfa=0, delta=120 fok Megvalósítás tekn˝oc grafikával Tekn˝oc állapota: 9
12. ábra. 1. rend˝u hópihe
10
13. ábra. 2. rend˝u hópihe
11
14. ábra. 5. rend˝u hópihe.
12
tartózkodási helye : (x, y) koordinátáju pont a síkon irány : a vízszintes egyenessel bezárt α szög elmozdulás mértéke : d (konstans) elfordulás szöge : δ (konstans) M˝uveletek: • E : el˝oremegy az adott irányítással d távolságot • + (B): balra fodul δ szöggel • - (J): jobbra fodul δ szöggel 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
program Hopihe ; u s e s PSteknoc ; / / Mag=F++F++F , / / F => F−F++F−F , / / a l f a =0 , / / d e l t a =120 f o k procedure F( n : i n t e g e r ) ; begin i f n=1 t h e n E e l s e begin F ( n −1); J ; F ( n −1);B ; B ; F ( n −1); J ; F ( n −1); end ; end ; p r o c e d u r e Mag( n : i n t e g e r ) ; begin F( n ) ; B;B;F( n ) ; B;B;F( n ) ; end ; begin kezd ( 1 0 0 , 2 0 0 , 0 , 5 , P i / 3 , ’ h o p i h e . ps ’ ) ; Mag ( 5 ) ; zar ; end .
1 2 3 4 5 6 7 8 9 10 11 12 13 14
u n i t PSTeknoc ; interface const / / A4−e s l a p m é r e t p o s t c r i p t pontokban , 1 p t = 2 5 , 4 / 7 2 ( = 0 , 3 5 2 8 )mm maxX= 5 95 ; maxY= 8 42 ; p r o c e d u r e kezd ( x0 , y0 , a l f a 0 , d0 , d e l t a 0 : d o u b l e ; f n e v : s t r i n g ) ; procedure E; procedure J ; procedure B; procedure zar ; p r o c e d u r e M; p r o c e d u r e V; procedure t o l l S z i n ( r , g , b : s i n g l e ) ;
15 16 17 18 19
implementation const P i 2 =2Λ P i ; Vmax=1 0 00 0; var 13
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
x , y , a lf a , d , d e l t a : double ; psf : text ; Vt : a r r a y [ 1 . . Vmax ] o f d o u b l e ; Vm: i n t e g e r ; p r o c e d u r e kezd ( x0 , y0 , a l f a 0 , d0 , d e l t a 0 : d o u b l e ; f n e v : s t r i n g ) ; begin x := x0 ; y := y0 ; a l f a := a l f a 0 ; d := d0 ; d e l t a := d e l t a 0 ; Vm: = 0 ; a s s i g n ( psf , fnev ) ; r e w r i t e ( psf ) ; w r i t e l n ( p s f , ’%!PS−Adobe −2.0 ’ ) ; w r i t e l n ( psf , ’ 0 . 5 s e t l i n e w i d t h ’ ) ; w r i t e l n ( p s f , x : 8 : 3 , ’ ’ , y : 8 : 3 , ’ moveto ’ ) ; end { kezd } ; procedure E; begin x := x + d Λ c o s ( a l f a ) ; y := y + d Λ s i n ( a l f a ) ; w r i t e l n ( psf , x : 8 : 3 , ’ ’ , y : 8 : 3 , ’ l i n e t o ’ ) ; end ; procedure J ; begin a l f a := a l f a −d e l t a ; i f ( a l f a <0 ) t h e n a l f a := a l f a + P i 2 ; end ; procedure B; begin a l f a := a l f a + d e l t a ; i f ( a l f a > P i 2 ) t h e n a l f a := a l f a −P i 2 ; end ; procedure zar ; begin w r i t e l n ( psf , ’ stroke ’ ) ; close ( psf ) end { z a r } ; p r o c e d u r e M; begin i n c (Vm) ; Vt [Vm] : = a l f a ; i n c (Vm) ; Vt [Vm] : = y ; i n c (Vm) ; Vt [Vm] : = x ; end ; p r o c e d u r e V; begin x := Vt [Vm] ; dec (Vm) ; y := Vt [Vm] ; dec (Vm) ; a l f a := Vt [Vm] ; dec (Vm) ; w r i t e l n ( p s f , x : 8 : 3 , ’ ’ , y : 8 : 3 , ’ moveto ’ ) ; end ; procedure t o l l S z i n ( r , g , b : s i n g l e ) ; begin w r i t e l n ( psf , r : 8 : 3 , ’ ’ , g : 8 : 3 , b : 8 : 3 , ’ s e t r g b c o l o r ’ ) ; end ;
14
2.12.
Feladat: Hilbert-görbe rajzolás
15. ábra. 1. rend˝u Hilbert-görbe
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
program H i l b e r t ; u s e s PSteknoc ; / / X => +YE−XEX−Y+ / / Y => −XE+YEY+Y− p r o c e d u r e Y( n : i n t e g e r ) forward ; p r o c e d u r e X( n : i n t e g e r ) ; begin i f n=0 t h e n e x i t ; B ; Y( n −1);E ; J ; X( n −1); E ; X( n −1); J ; E ; Y( n −1); B ; end {X} ; p r o c e d u r e Y( n : i n t e g e r ) ; begin i f n=0 t h e n e x i t ; J ; X( n −1); E ; B ; Y( n −1); E ; Y( n −1); B ; E ; X( n −1); J ; end {Y} ; p r o c e d u r e Mag( n : i n t e g e r ) ; begin X( n ) ; end ; var n: integer ; h , d : double ; 15
16. ábra. 2. rend˝u Hilbert-görbe
Hilbert görbe
X E
X
E
E Y
Y 1. ábra.
X = +Y E − XEX − EY + Y = −XE +Y EY + EX−
17. ábra.
16
18. ábra. 7. rend˝u Hilbert-görbe
17
20. ábra. Mag=F, F => FF-[-F+F+F]+[+F-F-F], alfa=Pi/2, delta=25 fok
18
21. ábra. Mag=F, F => FF, X => F[+X]F[-X]+X, alfa=Pi/2, delta=22.5 fok
19
22. ábra. Mag=X, F => FF, X => F+[[X]-X][-FX]+X, alfa=Pi/2, delta=22.5 fok
20
23. ábra. Bogáncs. Mag=[X]Y, X => [FF-YF+X-F], Y => [FF+XF-Y+F], alfa=Pi/2, delta=Pi/10
21
24. ábra. 12 éves feny˝ofa. Mag=SLEEE, S => [+++G][—G]TS, G => +H[-G]L, H => -G[+H]L, T => TL, L => [-EEE][+EEE]E, alfa=Pi/2, delta=Pi/10
22