Probleme rezolvate
Pentru fiecare dintre problemele de mai jos sunt prezentate 2 modalitati de rezolvare:
- cu functii de tip void
- cu functii (care returneaza o valoare)
Folosind metoda Divide et impera sa se afiseze produsul numerelor de la 1..n. n se citeste de la tastura.
#include<iostream.h>
int a[20],n;
void citire()//datele de intrare
{
cout<<"n=";cin>>n;
}
int produs(int p,int u)/*p-pozitia primului element din sirul de numere p..u, u-pozitia ultimului element din sirul p..u*/
{int m;
if(p==u)return p;//daca avem un singur element
else
{m=(p+u)/2; //impartim sirul p..u in 2 subsiruri
return produs(p,m)*produs(m+1,u); /*inmultim rezultatele celor 2 subsiruri*/
}
}
void main()
{
citire();
cout<<"produs="<<produs(1,n)<<endl;/*sirul intitial este 1..n. prin urmare p o sa fie 1 si u o sa fie n*/
}
A doua metoda
#include<iostream.h>
int a[20],n,pr;
void citire()//citirea datelor de intrare
{
cout<<"n=";cin>>n;
}
void produs(int p,int u,int &pr)/*p-pozitia primului element, u-pozitia ultimului element din sirul de numere p...u. pr-rezultatul problemei adica produsul numerelor dintre p..u*/
{int m,p1,p2;
if(p==u)pr=p;/*daca sirul are un singur element atunci produsul este valoarea acestui numar*/
else
{m=(p+u)/2;
produs(p,m,p1);/*in p1 retinem produsul elementelor p...m*/
produs(m+1,u,p2);/*in p2 retinem produsul elementelor m+1...u*/
pr=p1*p2;/*inmultim cele 2 rezultate pentru a gasi produsul elementelor p...u*/
}
}
void main()
{
citire();
pr=1;/*initializam produsul cu 1*/
produs(1,n,pr);/*primul element care trebuie inmultit este 1, ultimul este n, pozitiile lor in sirul 1...n sunt 1 respectiv n*/
cout<<"produsul="<<pr<<endl;
}
Se citesc de la tastatura n elemente intregi. Folosind metoda Divide et impera gasiti suma numerelor citite.
Prima metoda:
#include<iostream.h>
int a[20],n;
void citire()//citirea datelor de intrare: vectorul cu n elemente si numarul n
{
cout<<"n=";cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
}
int suma(int p,int u) //functia care calculeaza suma
{int m;
if(u<p)return 0; /*acest if nu e neaparat necesar. Insa daca se ajunge la o astfel de situatie, functia suma va returna valoarea 0.*/
else if(p==u)return a[p]; /*daca avem un singur element in subproblema pe care trebuie sa o rezolvam atunci suma este egala cu acest numar*/
else
{m=(p+u)/2;//gasim pozitia elementului din mijloc
return suma(p,m)+suma(m+1,u);/*impartim problema in doua subprobleme si adunam rezultatele de la fiecare subproblema*/
}
}
void main()
{
citire();
cout<<"suma="<<suma(1,n)<<endl;/*primul element se gaseste pe pozitia 1 si ultimul pe pozitia n*/
}
A doua metoda
#include<iostream.h>
int a[20],n,s;/*datorita faptului ca trebuie aflata o valoare, declaram variabila care retine acea valoare ca variabila globala*/
void citire()
{
cout<<"n=";cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
}
void suma(int p,int u,int &s) //s retine rezultatul
{int m,s1,s2;
if(u<p)s=0; /*daca se ajunge in situatia ca pozitia primului sa fie mai mare decat pozitia ultimului, adica un caz anormal, suma este 0*/
else if(p==u)s=a[p]; /*daca subsirul (subproblema) are un singur element atunci suma este egala cu valoarea elementului*/
else
{m=(p+u)/2;//gasim pozitia elementului din mijloc
suma(p,m,s1);//s1- suma elementelor din primul subsir
suma(m+1,u,s2);//s2- suma elementelor din cel de-al doilea sir
s=s1+s2;
}
}
void main()
{
citire();
s=0;
suma(1,n,s);/*primul element se gaseste pe pozitia 1 iar ultimul pe pozitia n. Suma se initializeaza cu 0 inainte de a trece la adaugarea elementelor la suma*/
cout<<"suma="<<s<<endl;
}
Folosind metoda Divide et impera sa se gaseasca valoare minima dintr-un sir de n numere intregi.
Prima metoda
#include<iostream.h>
int a[20],n;
void citire()//citim datele de intrare
{
cout<<"n=";cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
}
int minim(int p,int u)/*functia pentru calcularea minimului; p-pozitia primului element din subsir iar u-pozitia ultimului element din subsir*/
{int m,m1,m2;
if(p==u)return a[p];/*daca avem un singur element in subsir, minimul este egal cu acel element*/
else
{m=(p+u)/2;/*gasim pozitia elementului din mijloc*/
m1=minim(p,m);/*m1- valoare minima din prima parte a subsirului*/
m2=minim(m+1,u);/*m2- valoarea minima din cea de-a doua parte a subsirului*/
if(m1<m2) return m1; /*vedem care dintre cele 2 rezultate este cel mai mic*/
else return m2;
}
}
void main()
{
citire();
cout<<"valoarea minima="<<minim(1,n)<<endl;/*primul elemet din sir se gaseste pe pozitia 1 iar ultimul pe pozitia n*/
}
A doua metoda
#include<iostream.h>
int a[20],n,s,min;
void citire()//citirea datelor de intrare
{
cout<<"n=";cin>>n;
for(int i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
}
void minim(int p,int u,int &min)
{int m,m1,m2;/*primul element din subsir se afla pe pozitia p, ultimul pe pozitia u, iar rezultatul va fi retinut in variabila min*/
if(p==u)min=a[p];/*daca subsirul are un singur element, atunci aceasta este si valoarea minima*/
else
{m=(p+u)/2;/*gasim pozitia elementului din mijloc*/
minim(p,m,m1);/*m1 reprezinta valoarea minima din primul subsir*/
minim(m+1,u,m2);/*m2-valoarea minima din cel de-al doilea subsir*/
if(m1>m2)min=m2; /*valoarea minima este minimul dintre rezultatele subproblemelor*/
else min=m1;
}
}
void main()
{
citire();
min=a[1];/*initializam variabila care retine valoarea minima*/
minim(1,n,min);/*primul element se afla pe pozitia 1, ultimul pe pozitia n, rezultatul se retine in variabila min*/
cout<<"valoarea minima="<<min<<endl;
}
