Referat Divide Et Impera

Mai jos puteti citi fragmente din Referat Divide Et Impera si de asemenea puteti face Download Referat Divide et impera

Citeste fragmente din Referat Divide Et Impera

DIVIDE ET IMPERA Prezentare generalã Divide et impera este o tehnica speciala prin care se pot rezolva anumite probleme. Divide et impera se bazeaza pe un principiu extrem de simplu:descompunem problema in doua sau mai multe subprobleme (mai usoare),care se rezolva, iar solutia pentru problema initiala se obtine combinand solutiile problemelor in care a fost descompusa. Se presupune ca fiecare din probleme in care a fost descompusa problema initiala, se poate descompune in alte subprobleme, la fel cum a fost descompusa problema initiala. Procedeul se reia pana cand (in urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediata. Evident nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Fara teama de a gresi, putem afirma ca numarul lor este relativ mic, tocmai datorita cerintei ca problema sa admita o descompunere repetata. Divide et impera este o tehnica ce admite o implementare recursiva. Am invatat principiul general prin care se elaboreaza algoritmi recursivi: ce se intampla la un nivel, se intampla la un nivel, se intampla la orice nivel (avand grija sa asiguram conditiile de terminare). Tot asa, se elaboreaza un algoritm prin divide et imoera: la un anumit nivel avem doua posibilitati: am ajuns la o problema care admite o rezolvare imediata, caz in care se rezolva si se revine din apel(conditia de terminare); nu am ajuns in situatia de la punctul 1, caz in care sdescompunem problema in doua sau mai multe subprobleme, pentru fiecare din ele reapelam functia, combinam rezultatele si revnim din apel. Aplicatii Maximul dintr-un vector Se citeste un vector cu n componente, numere naturale. Se cere sa se tipareasca valoare maxima. Trebuie tiparita valoarea maxima dintre numerele retinute in vector de la i la j(initial i= 1, j=n). Pentru aceasta procedam astfel : daca i=j, valoare maxima va fi v[i] ; contrar vom imparti vectorul in doi vectori (primul vector va contine componentele de la i la (i+j) div 2, al doilea va contine componentele de la ((i+j) div 2 +1 la j ) , rezolvam subproblemele (aflam maximul pentru fiecare din ele) iar solutia problemei va fi data de valoarea maxima dintre rezultatele celor doua subprobleme. #include int v[10],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; } } main( ) { cout<<”n=”;cin>>n; for (int i=1;i<=n;i++) {cout<<”v[“<>v[i]; } cout<<”max=”< int v[100],n,nr; void caut(int i, int j) { if (nr==v[(i+j)/2]) cout<<”gasit”<<’ ‘<<”indice”<<(i+j)/2; else if (i>n; for (int i=1;i<=n;i++) { cout<<”v[“<>v[i];} cout<<”nr=”;cin>>nr; caut (1,n); } Sortarea prin interclasare Se considerã vectorul a cu n componente numere întregi ( sau reale ). Sã se sorteze crescãtor, utilizând sortarea prin interclasare. Dacã dispunem de douã siruri de valori, primul cu m elemente, al diolea cu n elemente, ambele sortate, atunci se poate obtine un vector care contine toate valorile soratate. Algoritmul de interclasare este performant, pentru cã efectueazã cel mult m+n-1 comparatii. Algoritmul de sortare prin interclasare se bazeazã pe urmãtoarea idee: pentru a sorta un vector cu n elemente îl împãtim în doi vectori care, odatã sortati, se interclaseazã. Conform strategiei Divide et impera, problema este descompusã în alte douã subprobleme de acelasi tip si, dupã rezolvarea lor, rezultatele se combinã (în particular se interclaseazã). Descompunerea unui vector în alti doi vectori care urmeazã a fi sortati are loc pânã când avem de sortat vectori de una sau douã componente. În aplicatie, functia sort sorteazã un vector cu maximum douã elemente; interc interclaseazã rezultatele; divimp implementeazã strategia generalã a metodei studiate. #include int a[10],n; void sort (int p,int q, int a[10] ) { int m; if (a[p]>a[q]) { m=a[p]; a[p]=a[q]; a[q]=m;} } void interc (int p,int q, int m, int a[10]) { int b[10],i,j,k; i=p; j=m+1; k+1; while ((i>n; for (i=1;i<=n;i++) { cout<<”a[“<>a[i];} divimp(1,n,a); for (i=1;i<=n;i++) cout<2 problema se complicã. Notãm cu H(n,a,b,c) sirul mutãrilor celor n discuri de pe tija a pe tija b , utilizând ca tijã intermediarã, tija c. Conform strategiei Divide et impera încercãm sã descompunem problema în alte douã subprobleme de acelasi tip, urmând apoi combinarea solutiilor. În acest sens, observãm cã mutarea celor n discuri de pe tija a pe tija b,utilizând ca tijã intermediarã tija c, este echivalentã cu: muatrea a n-1 discuri de pe tija a pe tija c , utilizând ca tijã intermediarã tija b; mutarea discului rãmas pe tija b; mutarea a n-1 discuri de pe tija c pe tija b , utilizând ca tijã intermediarã tija a. Parcurgerea celor trei etape permite definirea recursivã a sirului H(n,a,b,c) astfel: H(n,a,b,c) = { a,b dacã n=1 H(n-1,a,c,b),ab,H(n-1,c,b,a), dacã n>1 Exemple: Pentru n=2 avem: H(2,a,b,c)=H(1,a,c,b),ab,H(1,c,b,a)=ac,ab,cb. Pentru n=3 avem : H(3,a,b,c)=H(2,a,c,b),ab,H(2,c,b,a)=H(1,a,b,c),ac,H(1,b,c,a),ab,H(1,c,a, b),cb,H(1,a,b,c)=ab,ac,bc,ab,ca,cb,ab. include char a,b,c; int n; void han (int n, char a, char b, char c) { if (n==1) cout<>n; a=’a’; b=’b’; c=’c’ ; han(n,a,b,c); } 쥁@