interclasare divide et impera

Sortarea prin interclasare (merge-sort)

mergesort

Utilizand metoda divide et impera, sa se sorteze prin interclasare un sir

#include<iostream.h>
int a[20],n;

void mergesort(int i,int m,int j)

{int b[20],x=i,k=1,y=m+1;
while(x<=m && y<=j)
if (a[x]<a[y])
b[k++]=a[x++];
else
b[k++]=a[y++];
while (x<=m)
b[k++]=a[x++];
while (y<=j)
b[k++]=a[y++];
int t=i;
for (k=1;k<=(j-i)+1;k++)
a[t++]=b[k];
}

void divimp(int i,int j)
{if (i<j)
{int m=(i+j)/2;
divimp(i,m);
divimp(m+1,j);
mergesort(i,m,j);}
}

void main()
{
cout<<“n=”;
cin>>n;
for(int i=1;i<=n;i++)
{cout<<“a[“<<i<<“]=”;
cin>>a[i];
}
divimp(1,n);
cout<<“vectorul sortat este: “<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<‘ ‘;
}

cmmdc divide et impera

Sa se calculeze cmmdc pentru n numere utilizand metoda divide et impera

cmmdc

#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);
}

suma elementelor unui vector divide et impera

Sa se calculeze folosind metoda divide et impera suma elementelor unui vector

suma

#include<iostream.h>
int v[20],n;
int suma(int li,int ls)
{int m, d1 ,d2;
 if(li!=ls)           
     {m=(li+ls)/2;
      d1=suma(li,m); 
      d2=suma(m+1,ls);
       return d1+d2;
      }
 else 
    return v[li];
}
     
void main() 
{           
 cout<<“n=”;
 cin>>n;    
 for(int i=1;i<=n;i++)
   {cout<<“v[“<<i<<“]=”;
    cin>>v[i];}
cout<<“suma celor “<<n<<” elemente ale vectorului “<<suma(1,n);
}

sortare rapida (quick sort)

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 final ordonat: toate elementele aflate in stanga vor fi mai mici si toate elementele din dreapta lui vor fi mai mari ; parametrul k este transmis prin referinta (adresa) fiind astfel vizibil si in afara functiei poz
-vectorul V se imparte in doua parti : li,(k-1) si (k+1),ls
-pentru fiecare din aceste parti se reapeleaza functia quick
-fiecare din cele doua parti va fi impartita in alte doua parti ;procesul continua pana cand li depaseste ls ,in acest moment toate elementele vectorului au fost mutate exact pe pozitiile ce le vor ocupa in vectorul final ;deci vectorul este ordonat

#include<iostream.h>

int v[100],n,k;

void poz(int li,int ls,int & k,int v[100])
{
int i=li,j=ls,c,i1=0,j1=-1;
while(i<j)
{
if(v[i]>v[j])
{
c=v[j];v[j]=v[i];v[i]=c;
c=i1;i1=-j1;j1=-c;
}
i=i+i1;
j=j+j1;
}
k=i;
}

void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls,k,v);
quick(li,k-1);
quick(k+1,ls);
}
}

void main()
{
int i;
cout<<“n=”;cin>>n;
for(i=1;i<=n;i++)
{
cout<<“v[“<<i<<“]=”;
cin>>v[i];
}
quick(1,n);
for(i=1;i<=n;i++) cout<<v[i]<<” “;
}

maximul unui vector

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

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()
{
cout<<“n=”;cin>>n;
for(int i=0;i<n;i++)
{
cout<<“v[“<<i<<“]=”;
cin>>v[i];
}
cout<<“numarul cautat:”;cin>>x;
caut(0,n-1);
}

{joscommentenable}

turnurile din hanoi

Turnurile din Hanoi

Se dau 3 tije simbolizate prin a,b,c. Pe tija a se gasesc n discuri de diametre diferite, asezate in ordine descrescatoare a diametrelor. Se cere sa se mute de pe tija a pe b, utilizand ca tija intermediara tija c, toate cele n discuri, respectand urmatoarele reguli:

-la fiecare pas se muta un singur disc ;

-nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametrul mai mic.

Rezolvare:

Daca n=1 se face mutarea ab, adica se muta discul de pe tija a pe tija b.

Daca n=2 se fac mutarile ac,ab,cb.

Daca n>2 . Notam cu H(n,a,b,c) sirul mutarilor celor n discuri de pe tija a pe tija b , utilizand ca tija intermediara, tija c.

Conform strategiei Divide et impera incercam sa descompunem problema in alte doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor. Deci:mutarea celor n discuri de pe tija a pe tija b,utilizand ca tija intermediara tija c, este echivalenta cu:

muatrea a n-1 discuri de pe tija a pe tija c , utilizand ca tija intermediara tija b;

mutarea discului ramas de pe tija a pe tija b;

mutarea a n-1 discuri de pe tija c pe tija b , utilizand ca tija intermediara tija a.

#include<iostream.h>
char a,b,c;
int n;
void h(int n,char a,char b, char c)
{
if(n==1) cout<<a<<b<<” “;
else
{
h(n-1,a,c,b);
cout<<a<<b<<” “;
h(n-1,c,b,a);
}
}
void main()
{
cout<<“n=”;cin>>n;
h(n,’a’,’b’,’c’);
}

{joscommentenable}