[C++] Metoda 'divide et impera'

[Dookie]

 

 

 

Metoda 'divide et impera'

 

Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

 

Aplicații

Maximul dintr-un vector

Se citește un vector cu n componente, numere naturale. Se cere să se tipărească valoarea maximă.

Funcția căutată va genera valoarea maximă dintre numerele reținute în vector pe o poziție dintre i și j (inițial, i=1, j=n). Pentru aceasta, se procedează astfel:

 

 #include <iostream>
 using namespace std;
 int v[10],n;
 
 int max(int i, int j)
 {
   int a, b, m;
   if (i==j) return v[i];
   else
   {
     m = (i+j)/2;
     a = max(i, m);
     b = max(m+1, j);
     if  (a>b) return a;
     else return b;
   }
 }
 
 int main( )
 {
   cout<<”n=”;cin>>n;
   for (int i=1; i<=n; i++)
   {
     cout<<”v[“<<i<<”]=”; cin>>v[i];
   }
   cout<<”max=”<<max(1,n);
   return 0;
 }

 

Căutare binară

Se citește un vector cu n componente numere întregi (numerele se presupun ordonate crescător) și o valoare întreagă ("nr"). Să se decidă dacă nr se găsește sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conține această valoare.

 

 #include <iostream>
 using namespace std;
 int v[100], n, nr;
 
 void caut(int i, int j)
 {
   int m = (i+j)/2;
   if (nr==v[m])
     cout<<”gasit, indice=”<<m;
   else 
     if (i<j)
       if  (nr<v[m])
         caut(i, m-1);
       else caut(m+1, j);
     else cout<<”nu a fost gasit.”;
 }
 
 int main( )
 {
     cout<<”n=”; cin>>n;
     for (int i=1; i<=n; i++)
     {
       cout<<”v[“<<i<<”]=”; cin>>v[i];
     }
     cout<<”nr=”; cin>>nr;
     caut (0,n);
     return 0;
 }

 

Daca aveti nelamuriri va rog sa imi lasati aici in comentarii.

Daca doriti puteti sa imi trimiteti PM cu aplicatii C/C++/JavaScript/HTML/CSS/C#/Pascal si voi incerca sa va explic cat mai pe inteles.

O zi placuta in continuare si spor.

Edited October 4, 2017 by Dookie

[Cdorsu]

Copy-paste de pe wikipedia.

Cel putin n-ai copiat chiar tot de acolo.