meniu principal
logare



bacalaureat
rezolvari probleme c++
competente digitale
manuale pentru elevi
prezentari power point
Acasa divide et impera
Cele mai citite
  1. probleme rezolvate atestat informatica c++ (40249)
  2. Algoritmi in pseudocod (37999)
  3. probleme rezolvate bacalaureat informatica (12613)
  4. rezolvare probleme (9399)
  5. palindrom (8269)
  6. Formule in excel 2007 (8206)
  7. competente digitale (7538)
  8. probleme rezolvate atestat informatica visual fox (5972)
  9. ecuatia de grad 2 (5253)
  10. problema damelor (5248)

divide et impera

Probleme rezolvate in C++ 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ă.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

  1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
  2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
sursa:Wikipedia
Filtru titlu     Arată # 
Nr. Titlu articol Afişări
1 interclasare divide et impera 537
2 cmmdc divide et impera 742
3 suma elementelor unui vector divide et impera 524
4 sortare rapida (quick sort) 2313
5 maximul unui vector 1214
6 cautare binara 2215
7 turnurile din hanoi 4047
 
teste online

Public quizzes

View all quizzes
cele mai citite tag-uri
Statistics
Membri : 436
Conţinut : 542
Link-uri web : 5
Număr afişări conţinut : 751413

Ultimele articole

Prev Next Page:

litere de A si M backtracking

Metoda Backtracking Sa se genereze toate sirurile de lungime n, formate numai din literele A si M, siruri care sa nu... Read more

17 Feb 2012 Hits:27 backtracking

probleme rezolvate atestat informatica c++ p2

SUBIECTE SI REZOLVARI C++ PENTRU EXAMENUL DE ATESTAT LA INFORMATICĂ 25.Se citeşte de la tastatura un număr natural nenul n care... Read more

07 Feb 2012 Hits:319 atestat

Varianta 30 bacalaureat informatica 2007

Varianta 30 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_030.pdf|600|600} Rezolvari probleme 1) #include<fstream.h>ofstream g("bac.txt");int a[101][101],i,j,n;void fct(){ for(i=1;i<=n;i++) ... Read more

31 Ian 2012 Hits:59 bacalaureat 2007

Varianta 29 bacalaureat informatica 2007

Varianta 29 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_029.pdf|600|600} Rezolvari probleme 1) #include<fstream.h>ofstream g("bac.txt");void main(){ int n; cin>>n; for(int i=1;i<=n;i++) g<<i*3<<" ";} 2) #include<iostream.h>long n;void f(){ cin>>n; int i=0,a[10]; while(n) { i++; a[i]=n%10; n/=10; } int x=a[1]; int y=a[2]; int ok=1; for(int j=3;j<=i;j++) { if(j%2==1) if(a[j]!=x) ok=0; if(j%2==0) if(a[j]!=y) ok=0; } if(ok) cout<<"DA"; else cout<<"NU";}void... Read more

31 Ian 2012 Hits:60 bacalaureat 2007

Varianta 28 bacalaureat informatica 2007

Varianta 28 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_028.pdf|600|600} Rezolvari 1) #include<iostream.h>#include<math.h>long a,v[11],i,j,ok=1;void fct(){ int x=a%10; v[1]=x; int y=x; for(i=2;i<=10;i++) { y=y*x; v[i]=y%10; if(v[i]==v[1]) i=11; else ok++; }}void main(){ cin>>a; fct(); int n=2007%ok; cout<<v[n];} 2) #include<iostream.h>int a[101][101],i,j,n;void fct(){ for(j=1;j<=n;j++) a[1][j]=j; for(i=2;i<=n;i++) for(j=1;j<=n;j++) { if(a[i-1][j+1]==0) a[i][j]=a[i-1][n-j+1]; else a[i][j]=a[i-1][j+1]; }}void afis(){ for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cout<<a[i][j]<<" "; cout<<endl; }}void main(){ cin>>n; fct(); afis();} 3) #include<iostream.h>#include<math.h>long k;int panta(long... Read more

31 Ian 2012 Hits:38 bacalaureat 2007

Varianta 27 bacalaureat informatica 2007

Varianta 27 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_027.pdf|600|600} Rezolvari 1) #include<iostream.h>int n,i;void main(){ cin>>n; for(i=1;i<=n;i++) cout<<i*10<<" ";} 2) #include<iostream.h>#include<string.h>char a[101],b[101];int n;int aparitii(char s[101],char x){ int ok=0; for(int i=0;i<strlen(s);i++) if(s[i]==x) ok++; return ok;}void main(){ cin>>a; cin>>b; int ok=1; for(int... Read more

31 Ian 2012 Hits:33 bacalaureat 2007

Varianta 26 bacalaureat informatica 2007

Varianta 26 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_026.pdf|600|600} Rezolvari 1) #include<iostream.h>#include<math.h>void main(){ float a; int x,y; cin>>a; cout<<floor(a)<<" "; if(ceil(a)==a) cout<<ceil(a)+1; else cout<<ceil(a);} 2) #include<iostream.h>#include<math.h>int A[11][11];void citire(){ for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) cin>>A[i][j];}int maxim(int A[11][11],int i1,int i2){ int max=0; for(int... Read more

31 Ian 2012 Hits:31 bacalaureat 2007

Varianta 25 bacalaureat informatica 2007

Varianta 25 bacalaureat informatica 2007Cerinte si rezolvari {pdf=pdf/bacalaureat2007/varianta_025.pdf|600|600} Rezolvari 1) #include<fstream.h>ifstream f("bac.txt");#include<math.h>int i,n;float min;struct vect { float x,y;};vect v[100];void citire(){ f>>n; for(i=1;i<=n;i++) f>>v[i].x>>v[i].y; }void f1(){ min=sqrt(pow(v[1].x,2)+pow(v[1].y,2)); for(i=2;i<=n;i++) if(sqrt(pow(v[i].x,2)+pow(v[i].y,2)) < min) { min=sqrt(pow(v[i].x,2)+pow(v[i].y,2)); }}void f2(){ for(i=1;i<=n;i++) { float d... Read more

31 Ian 2012 Hits:33 bacalaureat 2007
feed-image

created by dacsa