FractaliDesenarea arborilor

binari

Motto: Ionformatica

nu inseamna calcul.Calculul este facut de masini de calcul.Informaticii ii apartine fantezia, imaginatia, demonstratia.

Fractali

Fractalii au fost introdusi in anul 1975 prin lucrarea revolutionara a matematicianului francez Benoit Mandelbrot,' O teorie a seriilor fractale' ce reuneste totodata diversele teorii dinaintea sa.

El este cel care a inventat cuvantul ,,fractal", de provenienta latina(,,frângere"-a sparge in fragmente nenumarate).

Notiunea de fractal a aparut ca urmare a studiului vietii reale in care informatia genetica continuta in nucleul unei celule se repeta la diferite scari . Calculatorul perimte ca o anumita figura (de ex:un segment) sa se transforme intr-o alta,formata din mai multe figuri initiale (de ex: o linie franta)si fiecare figura obtinuta sa se transforme in mod asemanator (aceste transformari necesita foarte multe calcule).

Aceste forme geometrice au fost considerate in trecut haotiice sau ,,aberatii geometrice", iar multe dintre ele erau atat de complexe incat necesitau calculatoare performante pentru a le vizualiza.Pe parcurs, domenii stiintifice ca fizica,chimia,biologia sau meteorologia descopereau elemente asemanatoare , care de multe ori contrazic aparenta ,dar acestea depasesc cu mult cunostintele de matematica din liceu.

Inainte de a va prezenta cateva exemple trebuie cunoscute notiunile de baza pt a lucra in mod grafic.

Generatitati

ELEMENTE DE GRAFICALimbajul Pascal contine o serie de proceduri si functii care permit realizarea unor aplicatii grafice.Acestea sunt reunite un unitatea GRAPH ce se gaseste in subacatalogul UNITS.Pentru ca o imagine sa poata aparea pe ecran calculatorul utilizeaza o placa video care difera in functie de memoria video si alti parametrii.Pt a accesa o placa video trebuie sa folosim anumite rutine speciale specifice lor numite Driver-e.Limbajul Pascal detine o colectie de astfel de component software si in functie de placa ce a fost detectata de sistem se incearca un driver sau altul. Aceste fisiere au extensia “bgi “ .In continuare ne vom referi doar la driverul VGA ( Video Graphics Array ) dezvoltat de firma IBM.Driverul VGA poate lucre in mai multe moduri insa vom prefer modul standard de inalta rezolutie “VGAHI”( constanta de tip intreg) ce poate afisa 640x480 puncte in 16 culori.

Selectarea driver-ului si a modului de lucru se face prin utilizarea procedurii initgraph. Aceasta are 3 parametrii: gdriver (de tip integer) care contine codul asociat drever-ului, gmode (de tip integer) care retine modul de lucru si o variabila de tip string, care arata calea catre unitatea GRAPH.Forma generala o procedurii este:

initpraph(gdriver,gmode, ‘cale’); .Primii doi parametrii sunt transmisi prin

referinta.

INITIALIZAREA SITEMULUI GRAFIC SE POATE FACE IN 2 FELURI:

1)Prin a solicita sa se identifice automat placa grafica si corespunzator ei sa se incarce un naumit driver si sa se selecteze modul de lucru

procedure initg; begin gdriver:= detect; initgraph (gdriver,gmode, ‘c:\tp\bgi’); if graphresult <> 0 then begin writeln (‘Tentativa esuata!”); halt end end;

Constanta detect are valoarea 0 si se specifica procedurii identificarea automata a driver-ului si a modului de lucru.

2) Prin indicarea cu ajutorul primilor 2 parametri ai unu driver si a unui mod de lucru solicitate de progamator

  griver:= VGA; gmode:=VGAHI; initgraph (gdriver,gmode, ‘c:\tp\bgi’); if graphresult <> 0 then begin writeln (‘Tentativa esuata!”); halt end end;

Tentativa de initializare grafica poate esua din diverse motive, cum ar fi lipsa unitatii GRAPH,calea indicate gresit etc.Testarea se realizeaza cu functia intreaga graphresult care returneaza 0 in caz afirmativ si o valoare diferita de 0 in caz contrar.

Elementele uni fractal1.Initiatorul

2.Legea de constructie

3.Procesul de generare

Copac fractal

Primii fractali faimosiTriunghiul lui Sierpinski

Sita lui Sierpinski

Covorul lui Sierpinski 1

Covorul lui Sierpinski 2

Praful lui Cantor

Curba lui Koch

Fulgul lui Coch

Ultra fractal

Arborele binar fractal

DEFINITIE Un arbore binar este o multime finita de noduri care

este fie vida,fie reprezinta un arbore ordonat in care fiecare nod are cel mult 2 descendenti.

Din definitie rezulta ca un arbore binar contine cel mult doi sub-arbori binari(stang sau drept).Ei se obtin deci prin suprimarea radacinii si a muchiilor incidente cu aceasta.Oricare din ei poate sa fie vid.Daca arborele binar este format dintr-un singur nod,atunci ambii subarbori sunt vizi.

Un nod fara descendenti se numeste nod terminal sau frunza.

Un arbore binar in care fiecare nod care nu este terminal are exact doi descendenti,se numeste arbore binar complet

Se da un segment AB. Cu ajutorul lui se construieste un arbore,asa cum se vede in figura de mai jos:

Lungimea fiecarei ramuri este o treime din lungimea initiala a segmentului .Fiecare latura se transforma in mod asemanator.Se cere sa se vizualizeze figura astfel rezultata ,dupa 1s transformari.

Pentru obtinerea ramurilor se procedeaza astfel: se considera punctul situat pe dreapta

determinata de segment si pentru care avem:k= CA/CB=3 ; X=(X1-3*x2)/(1-3);

y=(y1-3*y2)/(1-3)=(3*y2-y1)/2; se roteste acest punct in jurul punctului B (x2,y2)

cu un unghi de π/4; se roteste punctul in jurul lui B cu unghiul -π/4

In urma acestei rotatii se obtin coordonatele punctelor care ,impreuna cu punctul B,determina segmentele ce constituie ramurile arborelui.

Procedura desenez are ca parametri de intrare coordonatele unui segment ,numarul de transformari efectuate(n) si numarul de transformari care trebuie efectuate (1s).In cazul in care nu s-au efectuat toate transformarile ,se treseaza segmentul (cu o culoare oarecare), se calculeaza coordonatele punctelor care determina ramurile si,pentru fiecare segment ,se reapeleaza procedura.

PROGRAMUL DE DESENARE A ARBORILOR :

uses graph,crt; var gdriver,gmode,1s:integer xmax,ymax:integer; procedure initg; .... procedure retplan

(xc,yx,x1,y1:integer;x,y :integer;unghi:real); ... procedure desenez(x1 ,y1 x2,y2,n,ls:integer); var x,y :integer; begin if n<=1s then

begin setcolor(1+random(15)); moveto(x1,y1); lineto(x2,y2); rotplan(x2,y2,(3*x2-x1) div 2, (3*y2-y1) div 2,x,y,pi?4); desenez (x2,y2,x,y,n+1,1s); end end; begin randomize; write ( ‘1s=’);readln(1s); initg; setbkcolor(white); desenez (getmaxx div 2, getmaxy, getmaxx div 2, getmaxy-

250,1,1s); readln end.

APLICATIEPentru evidenţa elevilor unei şcoli se defineşte un arbore binar de căutare, în care fiecare nod va memora numărul matricol, numele şi numărul de absenţe ale unui elev. Căutarea în arbore se va face după numărul matricol al elevilor. Scrieţi un program care, prin intermediul unui meniu, selectează în mod repetat, atâta timp cât utilizatorul doreşte acest lucru, una din următoarele acţiuni:

adăugarea unui elev; afişarea absenţelor pentru numărul matricol minim; afişarea absenţelor pentru numărul matricol maxim; modifică numărul de absenţe al unui elev pentru

care se cunoaşte numărul matricol; afişează toţi elevii al căror nume începe cu litera „B”.

program aplicatie; type pnod=^nod; nod=record nr:integer; nume:string; abs:integer; st, dr: pnod; end; var r:pnod; n,op: integer; num:string; abs1:integer; exista:boolean; procedure creare (var p:pnod;n:integer; num:string; abs1:integer); {creeaza un nod al arborelui ce va contine un elev cu numarul matricol n, numele num si nr. de absente abs1} begin if p<>nil then begin if n<p^.nr then creare(p^.st, n, num, abs1) else if n>p^.nr then creare(p^.dr, n, num, abs1) else writeln(' elevul exista') end else begin new(p); p^.nr:=n; p^.nume:=num; p^.abs:=abs1; p^.st:=nil;p^.dr:=nil; end; end;

procedure SRD(p:pnod); begin if p<>nil then begin SRD(p^.st); writeln(' ',p^.nr,' ',p^.nume,' ',p^.abs); SRD(p^.dr); end; end; function min(p:pnod):integer; { cheia minima se gaseste in nodul cel mai din stinga, pornind de la radacina} begin if p^.st<>nil then min:=min(p^.st) else min:=p^.abs; end; function max(p:pnod):integer; {cheia maxima se gaseste in nodul cel mai din dreapta, pornind de la radacina} begin if p^.dr<>nil then max:=max(p^.dr) else max:=p^.abs; end;

procedure elevi_B(p:pnod); { afiseaza elevii care au numele incepind cu litera B} begin if p<>nil then begin if (p^.nume[1]='B') then begin exista:=true; writeln(' ',p^.nr,' ',p^.nume,' ',p^.abs); end; elevi_B(p^.st); elevi_B(p^.dr); end end; procedure modifica_abs(p:pnod;n:integer); { modifica nr. de absente pentru care se cunoaste numarul matricol} begin if p<>nil then begin if n<p^.nr then modifica_abs(p^.st, n) else if n>p^.nr then modifica_abs(p^.dr, n) else begin write(' absenta='); readln(abs1); p^.abs:=abs1; end end else writeln(' Elevul cu numarul matricol ',n,' nu exista'); end;

begin r:=nil; repeat writeln(' alegeti optiunea:'); writeln(' 1 - ADAUGAREA unui elev'); writeln(' 2 – Absente pentru matricol MINIM'); writeln(' 3 – Absente pentru matricol MAXIM'); writeln(' 4 - MODIFICA numarul de absente'); writeln(' 5 - ELEVII cu numele - B'); writeln(' 6 - LISTA tuturor elevilor'); writeln(' 0 - IESIRE'); writeln; readln(op); case op of

1:begin write(' numar matricol= '); readln(n); write(' nume elev= '); readln(num); write(' numar absente= '); readln(abs1); creare(r,n,num,abs1); end; 2:begin writeln(' Valoarea absentei pentru matricol MINIM'); writeln(' min=',min(r)); end; 3: begin writeln(' Valoarea absentei pentru matricol MAXIM'); writeln(' max=',max(r)); end; 4: begin write(' numar matricol='); readln(n); modifica_abs(r,n); end; 5:begin exista:=false; elevi_B(r); if not exista then writeln(' nu exista elevi cu numele - B'); end; 6:begin writeln; writeln(' lista tuturor elevilor'); SRD(r); end; end; until op=0; readln; end.

Realizatori:

COSTEA ANNELIESE

CALUGAR ANDREI

CREMINE DENISA

Activitatea Conţinut Responsabil/Durata

1. Documentarea şi conceperea machetei PPT

- căutarea de informaţii şi planificarea conţinutului PPT

Calugar AndreiCostea AnnelieseCremine Denisa

2. Editare documente şi PPT

- completarea documentelor

- Verificarea corectitudinii

Calugar AndreiCremine Denisa

3. Grafică PPT şi pagina WIKI

- Identitatea grafică a proiectului: logo/imagini/video

Costea AnnelieseCremine Denisa

4. Încărcarea fişierelor pe pagina WIKI şi personalizarea paginii

- încărcarea paginilor prin interfaţa WIKI

Costea Anneliese

5. Coordonator al echipei - împarte activităţile de lucru

- ajută membri echipei

Cremine Denisa

Rolurile in echipa

Manuanual informatica intensiv Editura L&S Soft

http://cnamd.wikispaces.com www.google.ro (imagini) http://facultate.regielive.ro http://ro.wikipedia.org

BIBLIOGRAFIE: