Divide et impera

Cautare Binara

by

#508 Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x. Date de intrare Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și … Read more

cmmdc divide et impera

by

Sa se calculeze cmmdc pentru n numere utilizand metoda divide et impera #include<iostream.h>int cmmdc(int a[20], int li, int ls){ if(li==ls) return a[li];  else   { int x,y;    x=cmmdc(a,li,(li+ls)/2);    y=cmmdc(a,(li+ls)/2+1,ls);    while(x!=y)       if(x>y) x=x-y;       else y=y-x;    return x;     }    }void main(){int a[20],n,i;cout<<“n=”;cin>>n;for(i=1;i<=n;i++) cin>>a[i];cout<<“cmmdc este: “<<cmmdc(a,1,n);}

sortare rapida (quick sort)

by

QUICK SORT 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 … Read more

maximul unui vector

by

Se citeste un vector cu n componente numere intregi.Se cere sa se afiseze valoarea maxima folosind metoda divide et impera #include<iostream.h>int v[100],n; int max(int i,int j){int a,b;if(i==j) return v[i];else { a=max(i,(i+j)/2); b=max((i+j)/2+1,j); if(a>b) return a; else return b; }} void main(){cout<<“n=”;cin>>n;for(int i=0;i<n;i++){ cout<<“v[“<<i<<“]=”; cin>>v[i]; }cout<<“maximul este:”<<max(0,n-1);} {joscommentenable}

cautare binara

by

Cautare binara 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.h> int v[100],n,x; 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”; } void main() { … Read more