Divide et Impera

Ce este Divide et Impera?

Aceasta metoda este o tehnica de programare care rezolva problemele in care se prelucreaza multimi de elemente.

Algoritmul presupune impartirea multimii in care se face cautarea solutiei in submultimi pana cand se epuizeaza elementele asupra carora se face cautarea sau pana cand s-a gasit o solutie partiala. Solutia finala se construieste din combinarea tuturor solutiilor determinate partial.

In ce consta?

CerinteCerinte Elevul responsabil

1.Prelucrarea vectorilor cu metoda “Divede et Impera”: a.Determinarea sumei si produsului elementelor vectorului;b.Determinarea elementului maxim/minim;c.Determinarea cmmdc si cmmmc al elementelor vectorului

Toi Oana,Vicentiu Mihaela

CerinteCerinte Elevul responsabil2.Problema turnurilor din Hanoi

Iordache Robert

3.Cautarea binara a unui element intr-un vector

Iordache Robert

4.Problema taieturilor Nitu Valentina

5.Sortarea prin interclasare- algoritmul MergeSort

Nitu Valentina

6.Sortarea rapida- algortimul QuickSort

Vicentiu Mihaela

7.Desenarea fractalilor: Curba lui Koch pentru unsegment, triunghi,patrat

Toi Oana

a)determinarea sumei si produsului elementelor vectorului;b)Determinarea elementului maxim/minim;c)Determinarea cmmdc si cmmmc al elementelor vectorului;

Prelucrarea vectorilor cu metoda DEI:

#include<iostream>using namespace std;int v[50], i, n, z, z1;void deicitire (int s, int d){int m;if(s==d) cin>>v[s];else{m=(s+d)/2;deicitire(s, m);deicitire(m+1, d);}}void deis(int s, int d, int &z){ int m, x1, x2;if(s==d)z=v[s];else{m=(s+d)/2;deis(s, m, x1);deis(m+1, d, x2);z=x1+x2;}}

void deip(int s, int d, int &z1){int m, x1, x2;if(s==d)

z1=v[s];else{m=(s+d)/2;deip(s, m, x1);deip(m+1, d, x2);z1=x1*x2;}}int main(){cin>>n;deicitire(1, n);for(i=1; i<=n;i++)cout<<v[i]<<" ";deis(1,n,z);deip(1,n,z1);cout<<endl<<"suma elementelor="<<z;cout<<endl<<"produsul elementelor="<<z1;return 0;}

#include<iostream>using namespace std;int v[20], i, n, z, k;void deicitire (int s, int d){int m;if(s==d) cin>>v[s];else{m=(s+d)/2;deicitire(s, m);deicitire(m+1, d);}}void deimax(int s, int d, int &z){ int m, x1, x2;if(s==d)z=v[s];else{m=(s+d)/2;deimax(s, m, x1);deimax(m+1, d, x2);if(x1>x2)z=x1;else z=x2;}}

void deimin(int s, int d, int &k){int m, x1, x2;if(s==d)k=v[s];else{m=(s+d)/2;deimin(s, m, x1);deimin(m+1, d, x2);if(x1<x2) k=x1;else k=x2;}}int main(){cin>>n;deicitire(1, n);for(i=1; i<=n;i++)cout<<v[i]<<" ";deimax(1,n,z);deimin(1,n,k);cout<<endl<<"max="<<z;cout<<endl<<"min="<<k;return 0;}

#include <iostream>using namespace std;int n, i, v[20], z, p, cmmmc;void deicitire (int s, int d){int m;if(s==d) cin>>v[s];else{ m=(s+d)/2; deicitire(s,m); deicitire(m+1, d); }}void deicmmdc(int s, int d, int &z){int x1, x2, m;if(s==d) z=v[s];else{m=(s+d)/2;deicmmdc(s, m, x1);deicmmdc(m+1, d, x2);while(x1!=x2){if(x1>x2) x1=x1-x2;else x2=x2-x1;}z=x1;}}

void deip(int s, int d, int &p){int x1, x2, m;if(s==d) p=v[s];else{ m=(s+d)/2;deip(s,m,x1);deip(m+1,d,x2);p=x1*x2; }}int main(){cin>>n;deicitire(1,n);for(i=1; i<=n; i++) cout<<v[i]<<" ";deicmmdc(1,n,z);deip(1,n,p);cmmmc=p/z;cout<<endl<<"cmmdc="<<z;cout<<endl<<"cmmmc="<<cmmmc;return 0;}

Problema turnurilor din Hanoi Turnul din Hanoi sau Turnurile din Hanoi este un joc matematic

sau puzzle. Este format din trei tije și un număr variabil de discuri, de diferite mărimi, care pot fi poziționate pe oricare din cele 3 tije. Jocul începe având discurile așezate în stivă pe prima tijă, în ordinea mărimii lor, astfel încât să formeze un turn. Scopul jocului este acela de a muta întreaga stivă de pe o tijă pe alta, respectând următoarele reguli:Doar un singur disc poate fi mutat, la un moment dat.Fiecare mutare constă în luarea celui mai de sus disc de pe o tija și glisarea lui pe o altă tijă, chiar și deasupra altor discuri care sunt deja prezente pe acea tijă.Un disc mai mare nu poate fi poziționat deasupra unui disc mai mic.

Pasi: 1.Mutarea a n-1 discuri de pe tija a pe tija c,utilizand ca tija

intermediara tija b; 2.Mutarea discului ramas pe tija b; 3.Mutarea a n-1 discuri de pe tija c pe tija b, utilizand ca tija

intermediara tija a.

PROGRAM C++

#include <iostream>using namespace std;char i,j,k;int n,nr=1;void hanoi (int n, char i, char j, char k) { if (n==1) cout<<i<<j<<endl; else { hanoi(n-1,i,k,j);//mutam "n-1" discuri de pe tija 1 pe tija 3 prin intermediul tijei auxiliare 2 nr++; cout<<i<<j<<endl;//mutam discul ramas de pe tija 1 pe tija 2 hanoi(n-1,k,j,i);//mutam "n-1" discuri de pe tija 3 pe tija 2 prin intermediul tijei 1 nr++; }}

int main(){  cin>>n;//n=nr de discuri i='1';j='2';k='3';//i,j,k=cele 3 tije hanoi(n,i,j,k); cout<<nr; return 0;}

*Cautarea binara a unui element intr-un vector

*Enunt: Se citeste un vector cu n componente numere intregi,ordonate crescator si o valoare intreaga x.Sa se decida daca x se gaseste sau nu printre componentele vectorului

#include<iostream> using namespace std; int v[100],n,x,i,j; void caut(int i,int j) { if(x==v[(i+j)/2]) cout<<"gasit"<<"

"<<"indice "<<(i+j)/2; else if(i<j) if(x<v[(i+j)/2])

caut(i,(i+j)/2 -

1); else

caut((i+j)/2+1,j); else cout<<"nu

s-a gasit"; }

int main()

{ cout<<"n=";cin>>n;

for(int i=0;i<n;i++) {

cout<<"v["<<i<<"]=";

cin>>v[i]; } cout<<"numarul

cautat:"; cin>>x; caut(0,n-1); return 0; }

Program C++

PROBLEMA TAIETURILOR

Sortarea prin interclasare- algoritmul MergeSort

• Se imparte vectorul in secvente din ce in ce mai mici, astfel incat fiecare secventa sa fie ordonata la un moment dat si interclasata cu o alta secventa din vector, corespunzatoare;

• Interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor alcatui un subsir ordonat din vector mai mare, la randul lui se va interclasa cu subsirul corespunzator si tot asa.

Program C++ #include <iostream> using namespace std; int v[1000],n; void citire () { int i; cin>>n; for(i=1;i<=n;i++) cin>>v[i]; } void ordo(int p,int u) { int aux; if(v[p]>v[u]) { aux=v[p]; v[p]=v[u]; v[u]=aux; } } void interclas(int p,int u,int m) { int i,j,a[1000],k=0; i=p; j=m+1; while(i<=m && j<=u) if(v[i]<v[j]) { k++; a[k]=v[i]; i++; } else { k++; a[k]=v[j]; j++; } if(i<=m) for(j=i;j<=m;j++) { k++; a[k]=v[j]; } else for(i=j;i<=u;i++) { k++; a[k]=v[i]; }

for(i=1;i<=k;i++) v[p+i-1]=a[i]; } void divide(int p,int u) { int m; if(u-p<=1) ordo(p,u); else { m=(p+u)/2; divide(p,m); divide(m+1,u); interclas(p,u,m); } } void afis () { int i; for(i=1;i<=n;i++) cout<<v[i]<<" "; cin>>i; } int main () { citire(); divide(1,n); afis(); return 0; }

Sortarea rapida- algortimul QuickSort

Enunt: Sa se ordoneze crescator un vector v, folosind metoda de sortare rapida (quick sort).

Etapele de rezolvare ale algoritmului QUICK SORT: -se apeleaza functia quick cu limita inferioara li=1 si limita

superioara ls=n-functia poz realizeaza mutarea elementului de pe prima pozitie exact pe pozitia k ce o va ocupa acesta in vectorul final ordonat: toate elementele aflate in stanga vor fi mai mici si toate elementele din dreapta lui vor fi mai mari ; parametrul k este transmis prin referinta (adresa) fiind astfel vizibil si in afara functiei poz-vectorul V se imparte in doua parti : li,(k-1) si (k+1),ls-pentru fiecare din aceste parti se reapeleaza functia quick-fiecare din cele doua parti va fi impartita in alte doua parti; procesul continua pana cand li depaseste ls ,in acest moment toate elementele vectorului au fost mutate exact pe pozitiile ce le vor ocupa in vectorul final ;deci vectorul este ordonat

Program C++• #include<iostream>• using namespace std;• int v[100],n,k;• void poz(int li,int ls,int & k,int v[100])

{int i=li,j=ls,c,i1=0,j1=-1;while(i<j) { if(v[i]>v[j]) { c=v[j];v[j]=v[i];v[i]=c; c=i1;i1=-j1;j1=-c; } i=i+i1; j=j+j1; }k=i;}

• void quick(int li,int ls){if(li<ls) { poz(li,ls,k,v); quick(li,k-1); quick(k+1,ls); }}

• int main(){int i;cout<<"n=";cin>>n;for(i=1;i<=n;i++) { cout<<"v["<<i<<"]="; cin>>v[i]; }quick(1,n);for(i=1;i<=n;i++) cout<<v[i]<<" ";

return 0;}

Curba lui koch a fost creata de matematicianul suedez Neils Fabian Helge von Koch. Pentru a ne da seama cum arata aceasta constructie,imaginati-va un triunghi echilateral,apoi adaugati pe fiecare latura un alt triunghi echilateral.Orice parte a ei,marita,arata fix ca originalul.De fiecare data cand un nou triunghi este adaugat la figura centrala, lungimea liniei creste insa aria interioara a curbei lui Koch ramane mai mica decat aria unui cerc desenat in jurul triunghiului original.

Pe scurt,este o linie de o lungime infinita ce inconjoara o zona finita

Desenarea fractalilor: Curba lui Koch pentru unsegment, triunghi,patrat

• Curba lui Koch dupa o iteratie

• Curba lui Koch dupa doua iteratii

• Curba lui Koch dupa 7 iteratii

• Acelasi principiu se aplica si in cazul unui patrat. Fiecare latura a unui patrat se transforma conform figurii alaturate:

• Dupa un numar mai mare de iteratii patratul arata in felul urmator

*Participare

Actiuni Elevii Asezarea in pagina Vicentiu Mihaela; Toi OanaAdaugarea efectelor Vicentiu MihaelaCautarea informatiilor Iordache Robert; Nitu Valentina

Vicentiu Mihaela; Toi OanaVerificarea programelor Nitu ValentinaVerificarea proiectului Iordache Robert; Nitu ValentinaImagini si animatii Vicentiu Mihaela

Thanks for watching• Proiectul a fost prezentat de elevii:• Iordache Robert • Nitu Valentina • Toi Oana• Vicentiu Mihaela• Clasa a X-a B• Colegiul National “Mihai Eminescu”