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]<<‘ ‘;
}

constructie vectorul TATA

Se citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se citeste varful radacina. Sa se construiasca si sa se afiseze vectorul TATA.

vector_tata2noduri1

Vectorul de tati de declara astfel: T[i]=parintele(tata) nodului i.

Pentru arborele din figura vectorul TATA este 0,1,2,1 si radacina este 1.Muchiile care se citesc sunt 1-2,2-1,1-4

#include<iostream.h>
int n, r, T[20], a[20][20], p[20];void citire()
{ int i,x,y;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“cititi muchiile de forma x-y : “<<endl;
  for(i=1;i<=n-1;i++)
    { cin>>x>>y;
      a[x][y]=a[y][x]=1;;
    }
  cout<<“dati radacina : “<<endl;
  cin>>r;
}void BF(int r)
{  int s,d,i,x[100];
   d=s=1;
   x[1]=r; p[r]=1;
   while (s<=d)
   { for(i=1;i<=n;i++)
      if(a[x[s]][i] &&!p[i])
    { d++; x[d]=i;
      p[i]=1; T[i]=x[s];
    }
     s++;
   }
}void main()
{ int i;
  citire();
  BF(r);
  cout<<“vectorul TATA este :”<<endl;
  for(i=1;i<=n;i++) cout<<T[i]<<” “;
}

arbori binari vector TATA

Se citeste un arbore cu n varfuri dat prin vectorul TATA.
1) Sa se afiseze muchiile arborelui
2) Sa se construiasca si sa se afiseze matricea de adiacenta a arborelui.

noduri1vector_tata1

Observatie: vectorul TATA  precizeaza pentru fiecare varf i, nodul TATA[i] care reprezinta parintele sau

Pentru arborele din imagine vectorul TATA este: 0,1,2,1.

#include<iostream.h>
int n, t[20], a[20][20];void afis()
{ int i,j;
  for(i=1;i<=n;i++)
    { for(j=1;j<=n;j++)
     cout<<a[i][j]<<” “;
     cout<<endl;
    }
}void main()
{ int i;
  cout<<“nr de noduri: “;cin>>n;
  cout<<“dati vectorul tata “<<endl;
  for(i=1;i<=n;i++)
  {
  cout<<“t[“<<i<<“]=”;
  cin>>t[i];
  }
  cout<<“muchiile sunt: “<<endl;
  for(i=1;i<=n;i++)
    if(t[i]!=0)
      { cout<<“[“<<t[i]<<“,”<<i<<“] “;
    a[i][t[i]]=a[t[i]][i]=1;
      }
  cout<<endl;
  cout<<“matricea de adiacenta este: “<<endl;
  afis();
}

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

subprogram inlocuire cifre

Scrieţi definiţia completă a subprogramului numar, cu trei parametri, care primeşte prin intermediul parametrului n un număr natural format din cel mult 9 cifre, iar prin intermediul parametrilor c1 şi c2 câte o cifră nenulă. Subprogramul caută fiecare apariţie a cifrei c1 în n, şi dacă aceasta apare, o înlocuieşte cu c2. Subprogramul furnizează tot prin n numărul astfel obţinut. Dacă cifra c1 nu apare în n, atunci valoarea lui n rămâne nemodificată.

#include<iostream.h>
void numar( long & n,int c1,int c2)
{
int p=0,p1=1,c;
long nr=n;
while(nr)
{
p=p+1;
if(nr%10==c1)
{
p1=1;
for(int i=1;i<p;i++)
p1=p1*10;
cout<<p1<<endl;
c=n%p1;
cout<<“c=”<<c;
cout<<endl;
p1=p1*10;
n=n/p1;
n=n*10+c2;
p1=p1/10;
n=n*p1+c;
cout<<n<<endl;
}
nr=nr/10;
}
}
void main()
{
long n;
int c1,c2;
cin>>n>>c1>>c2;
numar(n,c1,c2);
cout<<n;
}

arbore partial de cost minim algoritmul lui Kruskal

Sa se determine un arbore partial de cost minim folosind algoritmul Kruskal

Pentru memorarea muchiilor grafului si a costurilor acestora se defineste o structura de date cu trei campuri (nodurile muchiei si costul ei) pe care o numim muchie

#include<iostream.h>
#include<fstream.h>
typedef struct{int u,v,c;} muchie;
int l[30],n,m;
muchie e[30];
void citire()
{int i;
fstream f(“apm.txt”, ios::in);
f>>n;
f>>m;
for(i=1;i<=m;i++)
f>>e[i].u>>e[i].v>>e[i].c;
f.close();}

void main()
{int k,ultim,i,u,v,ct,ind,ms,lu,lv;
muchie aux;
citire();
for(i=1;i<=n;i++)
l[i]=i;
ultim=m;
while(ultim>1)
{k=0;
for(i=1;i<=ultim-1;i++)
if(e[i].c>e[i+1].c)
{aux=e[i];
e[i]=e[i+1];
e[i+1]=aux;
k=1;
}
ultim=k;}
cout<<“APM contine muchiile:”<<endl;
ct=0;ms=0;ind=0;
while(ms<n-1)
{
do
ind++;
while(l[e[ind].u]==l[e[ind].v]);
u=e[ind].u;
lu=l[u];
v=e[ind].v;
lv=l[v];
cout<<u<<”  “<<v<<endl;
ct=ct+e[ind].c;
ms++;
for(i=1;i<=n;i++)
if(l[i]==lu)
l[i]=lv;}
cout<<“costul APM este:”<<ct;}

sistem de ecuatii liniare cu doua necunoscute

Rezolvarea unui sistem de doua ecuatii liniare cu doua necunoscute in C++

Să se rezolve un sistem de două ecuaţii liniare cu două necunoscute:
a1*x+b1*y=c1
a2*x+b2*y=c2

Soluţiile sistemului de ecuaţii sunt:
x=dx/d=(b2*c1-b1*c2)/(a1*b2-b1*a2)
y=dy/d=(a1*c2-a2*c1)/(a1*b2-b1*a2)

#include<iostream>
void main(){
int a1, b1, c1, a2, b2, c2, d, dx, dy;
float x, y;
cout<<“a1=”; cin>>a1;
cout<<“b1=”; cin>>b1;
cout<<“c1=”; cin>>c1;
cout<<“a2=”; cin>>a2;
cout<<“b2=”; cin>>b2;
cout<<“c2=”; cin>>c2;
d=(a1*b2-b1*a2);
dx=(b2*c1-b1*c2);
dy=(a1*c2-a2*c1);
if (d==0)
if (dx==0)
cout<<”Sistem nedeterminat.”;
else
cout<<”Sistem incompatibil.”;
else{
x=dx/d;
y=dy/d;
cout<<”x=”<<x<<endl;
cout<<”y=”<<y;
}
}

patrat perfect

Se citeste un număr natural n. Să se verifice dacă n este pătrat perfect.

#include<iostream>
#include<cmath>
void main(){
int n; // n – numãrul citit de la tastaturã care se verificã dacã este pãtrat perfect
cout<<“n=”; cin>>n;
if (sqrt(n)==(int)(sqrt(n)))
cout<<n<<” este patrat perfect “<<endl;
else
cout<<n<<” nu este patrat perfect “<<endl;
}

cel mai mic numar par aflat intre 2 numere

Sa se scrie un program care citeste dintr-un fisier 2 numere si afiseaza cel mai mic numar par aflat intre cele doua numere.

#include<fstream.h>
void main()
{
int a,b,i,gasit=0,nr;
fstream f(“numere.in”,ios::in);
f>>a; cout<<a<<endl;
f>>b; cout<<b<<endl;
if(a>b)
{
nr=a;a=b;b=nr;
}
for(i=a;i<=b && gasit==0;i++)
if(i%2==0)   gasit=1;
nr=i-1;
cout<<“am gasit numarul “<<nr;
f.close();
}