Post on 12-Aug-2015
transcript
1
Structuri de Date în Java (VII)
● Aplicaţie pentru stive şi cozi● Evaluarea expresiei aritmetice postfixate● Translatarea din formă infixată în postfixată● Recursivitate● Explicaţii şi teste● Fractali. Proprietăţi● Setul Mandelbrot● O culme muntoasă● Setul Sierpinski
2
Aplicaţie pentru stive şi cozi
● Temă de laborator● Translatarea unei expresii aritmetice din forma
infixată cu paranteze în forma poloneză inversă (postfixată)
● Calcularea expresiei obţinute● Se citeşte întreaga expresie de la tastatură, într-
un string● Programul trebuie să evalueze expresia şi să
afişeze forma postfixată asociată● Eventualele erori trebuie semnalizate
3
Expresie aritmetică postfixată
● notaţia infixată: 2 + 3● notaţia prefixată: + 2 3 (forma poloneză)● inventată de matematicianul polonez Jan Lukasiewicz● expresia (2 + 3) * 7 se scrie în formă poloneză * + 2 3 7
(scăpăm de paranteze)● notaţia poloneză inversă, sau notaţia postfixată pentru
expresia (2 + 3) * 7 este 2 3 + 7 *● notaţia postfixată nu necesită paranteze şi poate fi evaluată
uşor folosind o stivă● principiul: se citeşte expresia postfixată; dacă se întâlneşte un
număr, acesta se pune în stivă; un semn se foloseşte de îndată ce este întâlnit
4
Evaluarea unei expresii postfixate
while mai există cuvinte în expresie dociteşte cuvântul următorif cuvântul este o valoare then
push (cuvânt)else cuvântul este un operator
pop () două valori de pe stivărezultat = aplicarea operator-ului valorilorpush (rezultat)
rezultatul final = pop ()// rezultatul evaluării expresiei se găseşte pe vârful stivei
5
Exemplu de evaluare postfixată5 3 2 * + 4 – 5 +
5
5 3 2 * + 4 – 5 +
35
5 3 2 * + 4 – 5 +
2 35
5 3 2 * + 4 – 5 +
65
5 3 2 * + 4 – 5 +
11
5 3 2 * + 4 – 5 +
411
5 3 2 * + 4 – 5 +
7
5 3 2 * + 4 – 5 +
57
5 3 2 * + 4 – 5 +
12
Rezultatulevaluăriiexpresiei
6
Translatarea unei expresii din forma infixată în forma postfixată (i)
3 * X + (Y – 12) - Z
Tiparit:
3
3 * X + (Y – 12) - Z
*Tiparit:3
3 * X + (Y – 12) - Z
*Tiparit:3 X
3 * X + (Y – 12) - Z
+
Tiparit:3 X *
3 * X + (Y – 12) - Z
(+
Tiparit:3 X *
3 * X + (Y – 12) - Z
(+
Tiparit:3 X * Y
numerele se tipăresc înmulţirea pe stivă operandul se tipăreşte
* are precedenţă maimare decât + şi setipăreşte
( se pune pe stivă operandul se tipăreşte
7
Translatarea unei expresii din forma infixată în forma postfixată (ii)
3 * X + (Y – 12) - Z
- (+
Tiparit:3 X * Y
3 * X + (Y – 12) - Z
- (+
Tiparit:3 X * Y 12
3 * X + (Y – 12) - Z
+
Tiparit:3 X * Y 12 -
3 * X + (Y – 12) - Z
-
Tiparit:3 X * Y 12 - +
3 * X + (Y – 12) - Z
-
Tiparit:3 X * Y 12 - + Z
3 * X + (Y – 12) - Z
Tiparit:3 X * Y 12 - + Z -
- este pus pe stivă (era doar paranteza)
numerele se tipăresc se scoate tot până la paranteza (
tipăreşte, + are aceeaşi precedenţă cu -
operandul se tipăreşte goleşte stiva
8
Algoritmul de translatare● iniţializează stiva● repetă paşii următori
● dacă urmează o paranteză deschisă “(“, atunci o pune în stivă● dacă însă urmează un număr sau operand, atunci îl tipăreşte● dacă însă e un operator, atunci:
● dacă în vârful stivei este un alt operator cu precedenţa mai mare sau egală cu a acestuia, atunci se scoate acel operator din stivă şi se tipăreşte
● se pune pe stivă operatorul● altfel, ceea ce urmează este o paranteză închisă “)”
● se scot simboluri din stivă şi se afişează până se întâlneşte paranteza deschisă corespondentă, care se scoate şi ea din stivă
● până când expresia se termină● se scot şi se afişează operatorii care au mai rămas în stivă (nu ar trebui să
mai avem paranteze deschise)
9
Recursivitate
“În matematică sau computer science, recursivitatea specifică (sau construieşte) o clasă de obiecte sau metode prin definirea câtorva cazuri de bază (deseori doar unul) şi prin descrierea regulilor ce descompun cazurile complexe într-unele mai simple.”
(Wikipedia)
10
Metode recursive
● recursivitatea înseamnă rezolvarea unei probleme cu ajutorul rezultatului obţinut prin rezolvarea unei aceleiaşi probleme dar de mărime mai redusă
● practic o metodă se poate autoapela dar cu un argument de mărime mai mică
● se poate formula o abordare recursivă pentru o problemă● la formularea unei metode recursive, trebuie acordată
atenţie la evoluţia argumentului metodei, pentru a nu ajunge la valori invalide
11
:-P
RecursionIf you still don't get it, See: "Recursion".
Recursive acronyms● GNU: GNU's Not Unix● PHP: PHP Hypertext Preprocessor● GNU HURD: HIRD of Unix-Replacing Daemons● HIRD: HURD of Interfaces Representing Death
(hurd/hird/herd of gnus – i.e. the antelope)
12
Metoda writeVertical● problema: să se scrie cifrele unui număr pe verticală,
folosind o metodă recursivă
public class RecWrite{ public static void writeVertical (int number) { if( number < 10 ) System.out.println (number); else { writeVertical (number / 10); System.out.println (number % 10); } } public static void main (String[] args) { writeVertical (1234); }}
problema opririi
apelul recursiv
13
Desfăşurarea apelurilor (I)apel writeVertical( 1234 )
1234 < 10 ? NUapelăm writeVertical(123)scriem cifra '4'
apel writeVertical( 123 )
123 < 10 ? NUapelăm writeVertical( 12 )scriem cifra '3'
apel writeVertical( 12 )
12 < 10 ? NUapelăm writeVertical(1)scriem cifra '2'
apel writeVertical( 1 )
1 < 10 ? DAscriem cifra '1'
14
Desfăşurarea apelurilor (II)
apel writeVertical( 1234 )
1234 < 10 ? NUapelăm writeVertical(123)scriem cifra '4'
apel writeVertical( 123 )
123 < 10 ? NUapelăm writeVertical( 12 )scriem cifra '3'
apel writeVertical( 12 )
12 < 10 ? NUapelăm writeVertical(1)scriem cifra '2'
apel writeVertical( 1 )
1 < 10 ? DAscriem cifra '1'
15
Desfăşurarea apelurilor (III)
● Colecţia de parametri ai metodei curente precum şi variabilele sale locale sunt salvate pe stivă înainte de efectuarea apelului recursiv
● La întoarcerea din apel, se refac aceste valori tot folosind stiva
● Instrucţiunea de după apel se execută după ce s-a revenit din apel, valorile parametrilor rămîn aceleaşi cu cele de dinainte de apel
16
Teste - A
// ce se afişează pentru apelul f(3) ?
public static void f(int n) {System.out.println (n);if (n > 1)
f (n-1);}
17
Teste - B
// ce se afişează pentru apelul f(3) ?
public static void f(int n) {if (n > 1)
f (n-1);System.out.println (n);
}
18
Teste - C
// ce se afişează pentru apelul f(3) ?
public static void f(int n) {System.out.println (n);if (n > 1)
f (n-1);System.out.println (n);
}
19
Fractali
● Noţiunea de “fractal” inventată de Benoît Mandelbrot (1975) descrie obiecte a căror porţiune mărită (cu o lupă) prezintă similaritate cu întregul obiect
● Denumire derivată din latinescul fractus● Un fractal matematic este bazat pe o ecuaţie
iterativă, bazată pe recursie● Structuri geometrice folosite de programatori
pentru a realiza scene naturale reprezentînd arbori, munţi, nori etc.
20
Setul Mandelbrot
detaliu:
21
Proprietăţi
● Are o structură fină oricât de mult ar fi “mărit”
● Este mult prea neregulat pentru a fi descris cu ajutorul geometriei euclidiene
● Întregul are aceeaşi formă ca una sau mai multe părţi ale sale (self-similarity)
● Are o definiţie simplă şi recusivă
22
Generarea fractalilor● Punctul situat la jumătatea segmentului este deplasat în sus sau în jos cu
o distanţă aleatoare● Se aplică regula din nou pe subsegmentele create● Se opreşte când mărimea unui subsegment devine relativ mică
a) segmentul iniţial b) mijlocul segmentului estemutat mai sus sau mai jos
c) două mijloacesunt mutate d) se mută patru mijloace
23
O coamă muntoasă
Procedeul se aplicărecursiv până cânddistanţa dintre douăpuncte devine < 50
(rezoluţie 512 x 512)
24
randomFractal (0, height/2, width, height/2)
public void randomFractal ( int leftX, int leftY, int rightX, int rightY) { final int STOP = 50; int midX, midY, deltam, deltap, delta; if ((rightX - leftX) <= STOP) drawArea.drawLine (leftX, leftY, rightX, rightY); else { midX = (leftX + rightX) / 2; midY = (leftY + rightY) / 2; deltam = - (int)(Math.random() * midY / 2); deltap = (int)(Math.random () * (width - midY) / 2); delta = -deltam < deltap ? deltam : deltap; midY += delta; randomFractal (leftX, leftY, midX, midY); randomFractal (midX, midY, rightX, rightY); } }
25
Un fractal cu pătrate
● Care este regularecursivăde formare?
● Care este condiţiade oprire ?
26
cubFractal (0, 0, width, height); public void cubFractal ( int leftX, int leftY, int rightX, int rightY) { final int STOP = 4; int midX, midY; if (rightX - leftX <= STOP) drawArea.drawRect (leftX, leftY,
rightX - leftX, rightY - leftY); else { midX = (leftX + rightX) / 2; midY = (leftY + rightY) / 2; drawArea.drawRect (leftX, leftY,
midX - leftX, midY - leftY); drawArea.drawRect (midX, midY,
rightX - midX, rightY - midY); cubFractal (midX, midY, rightX, rightY); cubFractal (midX, leftY, rightX, midY); cubFractal (leftX, midY, midX, rightY); } }
27
Triunghiul Sierpinski
Fractal descrisîn 1915 de cătrematematicianulpolonezWaclaw Sierpinski
28
Abstractizarea unui punct static class Pair { public int x; public int y; public Pair (int x, int y) { this.x = x; this.y = y; } public static Pair mid (Pair a, Pair b) { return new Pair ((a.x + b.x) / 2,
(a.y + b.y) / 2); } public static int len (Pair a, Pair b) { double x = a.x - b.x; double y = a.y - b.y; x *= x; y *= y; return (int)Math.sqrt (x + y); } }
29
Triunghiul iniţial
public void sierpinski () { Pair a = new Pair (width / 2, 0); Pair b = new Pair (0, height); Pair c = new Pair (width, height); sierpinski (a, b, c); }
30
Procedura de generare public void sierpinski (Pair a, Pair b, Pair c) { if (Pair.len (a, b) < 10) { drawArea.drawLine (a.x, a.y, b.x, b.y); drawArea.drawLine (b.x, b.y, c.x, c.y); drawArea.drawLine (a.x, a.y, c.x, c.y); return; } Pair ab = Pair.mid (a, b); Pair bc = Pair.mid (b, c); Pair ac = Pair.mid (a, c); sierpinski (a, ab, ac); sierpinski (ab, b, bc); sierpinski (ac, bc, c); }
31
Mult mai mult
http://en.wikipedia.org/wiki/Fractal