INFORMATICA METODA DIVIDE ET IMPERA

 

 

METODA DIVIDE ET IMPERA

ENUNTUL

Sa se scrie un program care calculeaza :

Valoarea minima si valoarea maxima dintr-un vector ;

Suma a doua polinoame .

Metoda Divide Et Impera

Expresia  Divide Et Impera  provine din limba latina si a constituit unul dintre principiile de guvernare ale imparatului roman Iulius Cezar.In traducere inseamna "dezbina si stapaneste" si exprima un adevar,din pacate valabil si in ziua de azi: o masa de oameni poate fi mai usor stapanita,atunci cand este dezbinata !

Ceea ce este trist pentru o societate,poate fi benefic atunci cand un informatician vrea sa rezolve o problema,asa cum se va vedea in continuare.Numele acestei tehnici de programare arata foarte clar in ce consta ea : prin analogie cu exemplul din istorie, o problema poate fi mult mai usor  stapanita  si astfel rezolvata, daca este  despicata  in mai multe parti.

Algoritmii  Divide Et Impera  sunt in general rapizi, deoarece prin descompunere, de cele mai multe ori, se obtin probleme pentru care rezolvarea si combinarea solutiilor au grad de complexitate mai mic decat problema initiala.

Algoritmii Divide Et Impera se implementeaza, de obicei, intr-un subprogram recursiv.

Principiul metodei

In programare, aplicarea acestui principiu se face astfel:

Se descompune problema data in doua sau mai multe probleme de aceeasi natura. Acestea pot fi de doua tipuri : elementare sau ne-elementare.

Cele elementare se rezolva direct, iar cele ne-elementare se descompun in continuare in alte suprobleme elementare si ne-elementare. Procesul de descompunere continua pana cand s-au obtinut numai probleme elementare.

Solutia problemei initiale se obtine prin reconstituirea si recombinarea solutiilor subproblemelor, in ordine inversa. Datorita acestui principiu de functionare, algoritmii Divide Et Impera au un caracter recursiv.

Probleme pentru care metoda Divide Et Impera determina solutia optima

1.Valoarea minima si valoarea maxima dintr-un vector

Sa se determine simultan valoarea minima si valoarea maxima dintr-un vector care contine numere intregi.Numarul de elemente al vectorului si elementele lui se citesc de la tastatura.

#include <iostream.h>

int v[100],n ;

void divizeaza(int s,int d,int &m)

void combina(int x1,int y1,int &z1,int x2,int y2,int &z2)

void dei(int s,int d,int &z1,int &z2)

}

void main()

dei(1,n,z1,z2);

cout<<"minimul ="<<z1<<endl<<"maximul ="<<z2<<endl ;

getch() ;

Implementarea metodei divide et impera in aceasta problema se face astfel:

Subprogramul divizeaza() - Numarul de subprobleme in care se descompune problema este 2. Multimea datelor de intrare este divizata in doua submultimii disjuncte de indicii,adica multimea indicilor [s,d] este divizata in doua submultimi disjuncte [s,m] si [m+1,d unde m este indicele din mijlocul intervalului: m=(s+d)/2. In subprogram, procesul de divizare consta in determinarea mijlocului intervalului - m.

Suprogramul combina() - Combinarea solutiei inseamna determinarea minimului (z1) si a maximului (z2) dintre cele doua valori minime (x1 si y1), respectiv maxime (x2 si y2), obtinute prin rezolvarea celor doua subprobleme. In subprogram sunt combinate cele doua perechi de valori obtinute din cele doua intervale.

Subprogramul dei() - O subproblema corespunde cazului de baza atunci cand submultimea contine un singur element. Daca s-a terminat procesul recursiv, atunci se prelucreaza cazul de baza, altfel, se apeleaza subprogramul pentru divizarea intervalului, se apeleaza subprogramul dei() pentru primul interval, se apeleaza subprogramul dei() pentru al doilea interval si se combina cele doua rezultate.

2.Suma a doua polinoame

Sa se calculeze suma a doua polinoame. Gradele celor doua polinoame, n si m, si coeficientii celor doua polinoame se citesc de la tastatura. Coeficientii celor doua polinoame se memoreaza in vectorii p si q, iar coeficientii polinomului suma se memoreaza in vectorul r.

#include <iostream.h>

int p[10],q[10],r[10],n,m;

int maxim(int x,int y)

int minim(int x,int y)

void divizeaza(int s,int d,int &mij)

void dei(int s,int d)

void main()

for(i=1;i<=m+1;i++)

dei(1,maxim(n,m)+1);

for(i=maxim(n,m)+1;i>=1;i--)

if(r[i]!=0)

if(i>2)

cout<<"x^"<<i-1;

else

if(i==2)

cout<<"x";

if(i!=1)

cout<<"+";

}

getch(

Implementarea metodei Divide Et Impera in aceasta problema se face astfel :

Subprogramul divizeaza() - Numarul de subprobleme in care se descompune problema este 2. Deoarece exista doua multimi de date de intrare, se va lua ca reper multimea cu cele mai multe elemente. Multimea datelor de intrare este divizata in doua submultimi disjuncte, prin divizarea multimii indicilor in doua submultimi disjuncte de indicii, adica multimea indicilor [s,d] este divizata in doua submultimi disjuncte [s,mij] si [mij+1,d], unde mij este indicele din mijlocul intervalului : mij =(s+d) /2. Procesul de divizare este identic cu cel de la problema anterioara.

Subprogramul combina() - Deoarece in cazul de baza se determina unul dintre coeficientii polinomului suma care se scrie direct in vectorul r , acest subprogram nu mai este necesar.

Subprogramul dei() - O subproblema corespunde cazului de baza atunci cand submultimea contine un singur element. Daca s-a terminat procesul recursiv, atunci se prelucreaza cazul de baza, prin care se calculeaza coeficientul polinomului suma pentru acel indice(daca termenul care se calculeaza are indicele mai mic decat gradul minim al polinoamelor, atunci el este egal cu suma coeficientilor celor doua polinoame, altfel, daca polinomul p are gradul mai mic decat al polinomului q, atunci el este egal cu coeficientul polinomului q, altfel, el este egal cu coeficientul polinomului p), altfel, se apeleaza subprogramul pentru divizarea intervalului, se apeleaza subprogramul dei() pentru primul interval si apoi pentru al doilea interval.

Codul sursa al programului propriu-zis

#include<iostream.h>

#include<conio.h>

int v[100],n,p[10],q[10],r[10],nr,m;

void pg1()

void pg2()

void sfarsit()

void meniu()

int maxim(int x,i nt y)

int minim(int x, int y)

void divizeaza(int s, int d, int &mij)

void combina(int x1, int y1, int &z1, int x2, int y2, int &z2)

void dei(int s, int d, int &z1, int &z2)

void dei2(int s, int d)

void main()

dei(1,n,z1,z2);

cout<<'minimul='<<z1<<endl<<'maximul='<<z2<<endl;

getch();

}

break;

case 2 :

for(i=1;i<=m+1;i++)

dei2(1,maxim(nr,m)+1);

for(i=maxim(nr,m)+1;i>=1;i--)

if(r[i]!=0)

if(i>2)

cout<<'x^'<<i-1;

else

if(i==2)

cout<<'x';

if(i!=1)

cout<<'';

}

getch();

}

break;

}

sfarsit();

}

getch();