Probleme rezolvate2
Folosind metoda Divide et impera sa se gaseasca suma numerelor pare dintre 1...n. n se citeste de la tastatura.
Prima metoda
#include<iostream.h>
int a[20],n;
void citire()//datele de intrare
{
cout<<"n=";cin>>n;
}
int suma(int p,int u)/*p-pozitia primului element din sirul de numere p..u. u-pozitia ultimului element din sirul p..u*/
{int m,s1,s2;
if(p==u) //daca in sirul p..u avem un singur element
if(p%2==0)return p; /*verificam daca elementul e par. In acest caz suma este valoarea acestui element*/
else return 0;/*daca elementul este impar la suma nu se adauga nicio valaore*/
else
{m=(p+u)/2;/*pozitia elementului din mijloc in sirul p..u*/
/*liniile urmatoare pot fi inlocuite cu return suma(p,m)+suma(m+1,u)*/
s1=suma(p,m);/*s1 suma elementelor pare din prima parte a sirului p..u*/
s2=suma(m+1,u);/*s2-suma elementelor pare din a doua parte a sirului p..u*/
return s1+s2;/*suma elementelor pare din sirul p..u este suma elementelor pare din cele 2 subsiruri*/
}
}
void main()
{
citire();
cout<<"suma="<<suma(1,n)<<endl; /*primul element din sirul 1...n se gaseste pe pozitia 1 iar ultimul pe pozitia n*/
}
A doua metoda
#include<iostream.h>
int a[20],n,s;
void citire()//citirea datelor de intrare
{
cout<<"n=";cin>>n;
}
void suma(int p,int u,int &s)/*suma elementelor pare din sirul p..u; p-pozitia primului element, u-pozitia ultimului element. s- suma elementelor pare*/
{int m,s1,s2;
if(p==u)/*daca sirul p..u are un singur element*/
if (p%2==0) s=p;/*verificam daca elementul e par, in caz afirmativ il adaugam la suma. in caz negativ la suma nu se adaga nimic*/
else s=0;
else
{m=(p+u)/2;/*gasim pozitia elementului din mijloc*/
suma(p,m,s1);/*s1- suma elementelor pare din sirul p...m*/
suma(m+1,u,s2);/*s2-suma elementelor pare din dirul m+1..u*/
s=s1+s2;/*suma elementelor pare din sirul p...u este suma rezultatelor celor 2 subsiruri*/
}
}
void main()
{
citire();
s=0;//initializam suma
suma(1,n,s);/* primul element se afla pe pozitia 1 si ultimul element pe pozitia n. s-suma elementelor pare din sirul 1...n*/
cout<<"suma="<<s<<endl;
}
Problema turnurilor din Hanoi
Se dau trei tije notate a, b, c si n discuri de diamtre diferite.
Initial, pe tija a se gasesc toate discurile pus in ordine crescatoare a diamtrelor lor (cel cu diametrul cel mai mare este pus la baza).
Sa se mute toate discurile de pe tija a pe tija b, folosind tija c ca tija intermediara, respectand urmatoarele conditii:
- de fiecare data se muta un singur disc
- un disc se poate pune numai deasupra unui disc cu diametru mai mare.
Daca avem un singur disc, mutam discul pe tija b si problema este rezolvata. (a->b)
Daca avem doua discuri: mutam primul disc pe tija c, al doilea disc pe tija b, apoi discul de pe tija c il mutam pe tija b.
(a->c,a->b,b->c)
Daca n>2 problema se complica, in sensul ca trebuie mult mai multe mutari de efectuat.
Pentru rezolvare vom folosi metoda Divide et impera.
Conform algoritmului general avem:
Imparte. Se descompune problema in 2 subprobleme: prima va contine n-1 discuri iar a doua un singur disc.
Stapaneste. Mutam cele n-1 discuri de pe tija a pe tija c folosind tija intermediara b prin apeluri succesive ale subprogramului recursiv.
Se muta discul ramas pe b, apoi se muta discurile de pe tija c pe tija b prin intermediul tijei a.
Combina. Combinarea solutiilor nu este necesara datorita faptului ca prin mutarea discurilor se realizeaza si secventa de rezolvare a problemei initiale.
functia muta are structura: muta(numar discuri,de pe discul, pe discul,prin intermediul discului)
#include <iostream.h>
int n;
void muta(int n, char a,char b,char c)
{
if (n==1) cout<<a<<"->"<<b<<endl;/*daca avem un singur disc pe tija a il mutam pe tija b*/
else
{
muta(n-1,a,c,b);/*mutam n-1 discuri de pe tija a, pe tija c folosind ca tija intermediara tija b*/
cout<<a<<"->"<<b<<endl; /*mutam discul ramas de pe tija a pe tija b*/
muta(n-1,c,b,a);/*mutam cele n-1 discuri de pe tija c, pe tija b folosind ca tija intermediara tija a*/
}
}
void main()
{
cout<<"n=";cin>>n;
muta(n,'a','b','c');/*mutam n discuri de pe tija a, pe tija b folosind tija intermediara c - a,b,c sunt numele discurilor*/
}
Cautare binara
Se citesc de la tastatura n elemente si un numar x. Elementele se citesc in ordine crescatoare. Sa se afiseze pozitia pe care se afla x in sirul de elemente citit.
De exemplu:
1) n=5, a=(2,5,6,7,8), x=5 => elementul se gaseste pe pozitia 2
2) n=5, a=(2,5,6,7,8),x=4 => elementul nu se gaseste in sir
Ideea de rezolvare consta in impartirea sirului in 3 parti: elementele pana la pozitia din mijloc, elementul din mijloc si elementele de dupa elementul din mijloc.
Analizand pozitiile elementelor din sir si coansiderand ca avem p-pozitia primului element, u-pozitia ultimului element si m-pozitia elementului din mijloc, avem:
p...m-1,m,m+1...u
Daca tot impartim repetat sirul si nu gasim elementul x, pozitia primului element va ajunge sa fie mai mare ca valoare ca pozitia ultimului element, fapt ce nu este normal. Acest lucru se intampla doar in cazul in care elementul x nu se gaseste in sir.
La fiecare pas verificam daca elementul x este egal cu elementul din mijloc (x=a[m]). In caz afirmativ s-a gasit pozitia elementului in sir. Daca cele 2 elemente nu sunt egale verificam daca a[m]>x. Deoarece sirul a are elementele in ordine crescatoare deducem ca e de ajuns ca in cazul in care se intampla sa fie adevarata aceasta relatie, sa cautam pe x in sirul (p..m-1). In cazul in care a[m]<x vom cauta pe x in sirul (m+1..u)
#include<iostream.h>
int a[100],n,x;
void cauta(int p,int u) /*p-pozitia primului element,u-pozitia ultimului element*/
{int m;
if(p>u)cout<<"elementul nu se gaseste in sir"<<endl; /*daca prin impartiri succesive a sirului ajungem la aceasta relatie, elementul nu se gaseste in sir*/
else{
m=(p+u)/2;/*gasim pozitia elementului din mijloc*/
if(a[m]==x)cout<<"elementul se gaseste pe pozitia "<<m<<endl;/*daca x este egal cu elementul din mijloc, problema e rezolvata*/
else if(a[m]<x)cauta(m+1,u); /*daca x este mai mare ca elementul din mijloc, sirul a avand elementele in ordine crescatoare, vom cauta pe x printre elementele aflate pe pozitiile m+1...u*/
else cauta(p,m-1); /*daca x este mai mic ca elementul din mijloc il vom cauta pe x in prima parte a sirului*/
}
}
void citire()/*citirea datelor 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];
}
cout<<"elementul cautat x=";cin>>x;
}
void main()
{
citire();
cauta(1,n);/*initial primul element se gaseste pe pozitia 1 iar ultimul pe pozitia n*/
}
