Probleme rezolvate3
Se citesc de la tastaura n numere. Folosind metoda Divide et impera afisati cate dintre cele n numere citite sunt prime.
#include<iostream.h>
int a[100],n,x;
void citire()/*citim datele de intrare*/
{
cout<<"numarul de elemente=";cin>>n;
cout<<"sirul de elemente\n";
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";cin>>a[i];
}
}
int prim(int n)/*verificam daca numarul e prim*/
{
if(n<=1) return 0;/*primul numar prim este 2*/
int i=2;
while(i<=n/2) /*daca numarul are divizori proprii, nu este prim*/
if(n%i==0)return 0;
else i++;
return 1;
}
int numara(int p,int u) /*cautam numarul de numere prime*/
{ int m,n1,n2;
if(u==p) if(prim(a[p])) return 1;/*daca subsirul are un singur element verificam daca este prim. in caz afirmativ returnam 1 deoarece numarul de numere prime creste cu 1*/
else return 0;/*daca elementul nu e prim, valoarea returnata de contor nu se schimba*/
else
{
m=(p+u)/2;/*gasim pozitia elementului din mijloc si gasim numarul de numere prime din fiecare subproblema*/
n1=numara(p,m);
n2=numara(m+1,u);
return n1+n2;
}
}
void main()
{
citire();
cout<<"numarul de numere prime="<<numara(1,n);/*primul numar se gaseste pe pozitia 1 iar ultimul pe pozitia n*/
}
Se citesc de la tastatura n numere. Sa se afiseze cmmdc-ul celor n numere citite. Sa se foloseasca metoda Divide et impera.
De exemplu: n=4, a=(12,16,20,8)=>cmmdc=4
#include<iostream.h>
int a[100],n,x;
void citire()/*citim datele de intrare*/
{
cout<<"numarul de elemente=";cin>>n;
cout<<"sirul de elemente\n";
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";cin>>a[i];
}
}
int cmmdc(int a,int b)/*functia pentru a gasi cmmdc dintre 2 numere*/
{if(a==b)return a;
else if(a>b)return cmmdc(a-b,b);
else return cmmdc(a,b-a);
}
int cmmdc_n(int p,int u)/*functia gaseste cmmdc dintre n numere prinmetoda Divide et impera*/
{ int m;
if(u-p==1) cmmdc(a[p],a[u]); /*daca in subsir avem 2 elemente apelam functia pentru calculul cmmdc dintre cele 2 elemente. Subsirul are doua elemente daca diferenta dintre pozitia primului element si pozitia ultimului element din sir este 1*/
else
if(p==u) return a[p];/*daca sirul are un singur element atunci cmmdc=cu acest element*/
else
{
m=(p+u)/2;/*gasim pozitia elementului din mijloc*/
return cmmdc(cmmdc_n(p,m),cmmdc_n(m+1,u));/*gasim cmmdc dintre cele 2 cmmdc rezultate prin rezolvarea celor 2 subprobleme*/
}
}
void main()
{
citire();
cout<<"cmmdc="<<cmmdc_n(1,n);/*primul element din sir este pe pozitia 1, ultimul element din sir este pe pozitia n*/
}
