INFORMATICA/C/C++

METODA BACKTRACKING

Metoda Bactracking se poate folosi pentru problemele in care trebuie sa se genereze toate solutiile, o sulutie a problemei putand fii data de un vector:
S={X1,X2,…………,Xn}, ale carui elemente apartin, fiecare, unor multimi finite A(XiϵAi ), iar asupra elementelor unei solutii exista anumite restrictii, specifice problemei care trebuie rezolvata, numite conditii interne.
Multimile Ai sunt multimi ale caror elemente sunt in relatii bine stabilite. Multimile Ai pot sa coincide sau nu.Pentru a gasi toate solutiile unei astfel de problem folosind o metoda clasica de rezolvare, se executa urmatorul algoritm:

pas1. se genereaza toate elementele produsuli cartezian A1 xA2x…..xAn
pas2. se verifica fiecare element al produsului cartezian, daca indeplineste
conditiile interne impuse ca sa fie solutie a problemei
Metoda Bactracking construieste progresiv vectorul solutiei pornind de la primul element si adaugand la vector urmatoarele elemente cu revenire la elemental anterior din vector- in caz de insucces. Elementul care trebuie adaugat se cauta in multime, printre elementele care eprezinta conditii interne.

IMPLEMENTAREA METODEI

Date si structure de date
Se foloseste o structura de date de tip vector iar pentru indicele elementului care se adauga la solutie se foloseste variabila k.
Se mai folosesc urmatoarele variabile de memorie:
• as- pentru a stii daca pentru elementul Xk al solutiei mai exista un successor,adica daca mai exista un element in multimea Ak care ar putea fi elementul Xk al solutiei(este o variabila logica, ce are valoarea 1-true, daca exista succesor;astfel, are valoarea 0-false).
• ev- pentru a stii daca succesorul gasit respecta conditia de continuare si poate fi elementul Xk al solutiei(este o variabila logic ace are valoarea 1-true, daca succesorul este element al solutiei;astfel, are valoarea 0-false).
• n- pentru dimensiunea solutiei(numarul de elemente al solutiei, in cazul problemelor in care toate solutiile au acelasi numar de elemente)



Subprograme
• subprogramul init (functie procedurala), se initializeaza elementul care urmeaza sa se adauge la solutie (elementul de pe nivelul k)

void init()
{
s[k]=0;
}

• subprogramul succesor (functie operand), verifica daca mai exista in multimea Ak un element pentru nivelul k al solutiei(un succesor). Daca mai exista un succesor, se trece la urmatorul element din multimea Ak, iar functia va returna valoare 1(true). Daca nu exista va returna valoarea 0(false).

int succesor()
{
if(s[k]<n)
{
s[k]++;
return 1;
{
else
return 0;
}

• subprogramul valid(functie operand), verifica daca valoarea atribuita elementului Xk al solutiei indeplineste conditia de continuare, adica poate fi considerate ca face parte din solutia problemei(daca succesorul gasit este element al solutiei). Daca este indeplinita conditia va returna 1, altfel 0.
int valid()
{
for(int i=1;i<k;i++)
if(s==s[k]);
return 0;
return 1;
}
• subprogramul solutie(functie operand), verifica daca sau obtinut toate elementele solutie.Daca s-a obtinut solutia intoarce valoare 1(true), altfel 0(false).
int solutie()
{
return k==n;
}
• subprogramul tipar(functie procedurala), afiseaza elementele solutiei. De obicei afisarea solutiei consta in afisare valorilor din vectorul solutie
void tipar()
{
for(int i=1;i<=n;i++)
cout<<s<<” “;
cout<<endl;
}
• subprogram care va fi acelasi pentru toti algoritmii de rezolvare prin metoda Backtracking(parte fixa)

IMPLEMENTARE ITERATIVA

void bt()
{
k=1;
init();
while(k>0)
{
as=1;
ev=0;
while(as && !ev)
{
as=succesor();
if(as)
ev=valid();
}
if(as)
if(solutie)
tipar();
else
{
k++;
init();
}
else
k--;
}
}
void main()
{
………
bt();
…….
}

IMPLEMENTAREA RECURSIVA
void bt(int k)
{
int k;
while(succesor(k))
if(valid(k))
if(solutie(k))
tipar(k);
else
bt(k);
else
bt(k+1);
}
void main()
{
…….
bt(1);
……
}


EXEMPLU: Problema celor n dame

#include<iostream.h>
#include<math.h>
int n,k,ev,as,s=0,suma,este=0,a[10],s[100];
void init()
{ s[k]=0; }
int succesor()
{
if(s[k]<n)
{
s[k]=s[k+1];
return 1;
}
else return 0;
}
int valid()
{
for(int i=1;i<k;i++)
if(s[k]==s || abs(s[k]-s)==k-1)
return 0;
return 1;
}
int solutie()
{return k==n;}
void tipar()
{
for(int i=1;i<=n;i++)
cout<<s<<” “;
cout<<endl;
}
void bt() {……..} // partea fixa a algoritmului
void main(){
cout<<”n=”; cin>>n
bt();
}

METODA DIVIDE ET IMPERA

Se poate folosi pentru problem care pot fi descompuse in subprogram similar cu problema initiala(care se rezolva prin aceeasi metoda) si care prelucreaza multimi de date de dimensiuni mai mici, independente unele de altele(care folosesc multimi de date de intrare disjuncte).
IMPLEMENTARE(RECURSIV)
d - dimensiunea problemei
s – solutia problemei

divide_et _impera(d,s)
inceput
daca dimensiunea d corespunde unui caz de baza
atunci se determina solutia s a problemei;
altfel
pentru i=1,n executa
se determina dimensiunea d_i a subproblemei p_i
se determina solutia s_i a subproblemei p_i prin apelul
divide_et_impera(d_i,s_i);
sfarsit_pentru;
se combina solutiile s_1,s_2,s_3,……..s_n;
sfarsit_daca;
sfarsit.

Exemplu1: Sa se calculeze suma elementelor pare dintr-un vector V care contine numere intregi. Numarul de elemente al vectorului(n) si elementele lui se citesc de la tastatura.
#include<iostream.h>
int v[100],n;
void divizeaza(int s, int d, int &m)
{
m=(s+d)/2;
}
void combina(int x,int y, int &z)
{
z=x+y;
}
void dei(int s, int d, int &z)
{
int m,x1,x2;
if(d==s)
if(v%2==0)
z=v;
else
z=0;
else
{
divizeaza(s,d,m);
dei(s,m,x1);
dei(m+1,d,x2);
combina(x1,x2,z);
}
}
void main()
{
int i,z;
cout<<”n=”; cin>>n;
for(i=1;i<=n;i++)
{
cout<<”v[“<<i<<”]=”;
cin>>v;
}
dei(1,n,z);
cout<<”suma=”<<z;
}

Exemplu2: Sa se calculeze suma 1X2+2X3+…….+nX(n+1)

#include<iostream.h>
int n, suma;
void divizeaza(int s, int d, int &m)
{
m=(s+d)/2;
}
void combina(int x,int y, int &z)
{
z=x+y;
}
void dei(int s, int d, int &z)
{
int m,x1,x2;
if(d==s)
z=s*(s+1);
else
{
divizeaza(s,d,m);
dei(s,m,x1);
dei(m+1,d,x2);
combina(x1,x2,z);
}
}
void main()
{
int z;
cout<<”n=”; cin>>n;
dei(1,n,z);
cout<<”suma=”<<z;
}

Exemplu3:Sa se calculeze termenul n al sirului lui Fibonacci

#include<iostream.h>
int n;
void combina(int x1,int x2,int &z)
{
z=x1+x2;
}
void dei(int n, int &z)
{
int x1,x2;
if(n==1 || n==2)
z=1;
else
{
dei(n-1,x1);
dei(n-2,x2);
combina(x1,x2,z);
}
}
void main()
{
int z;
cout<<”n=”; cin>>n;
dei(n,z);
cout<<z;
}

SORTAREA PRIN INTERCLASARE(mergeSort)

Se executa pe doi vectori ordonati dupa acelasi criteriu, pentru a obtine un al treilea vector, care sa contina elementele primilor doi vectori, ordonate dupa acelasi criteriu.

pas1: se descompune problema in subprobleme similar prin impartirea vectorilor
in doi subvectori avand multimea indicilor [s,m] si [m+1,d], unde m este
indicele din mijlocul intervalului m=(s+d)/2;
pas2: daca subvectorul contine un singur element, atunci se considera sortat;
altfel se continua descompunerea lui in subvectorii care au multimea
indicilor [s,m] si multimea indicilor [m+1,d];
pas3: se combina solutiile celor doua subprobleme prin interclasarea celor doi
vectori sortati, obtinandu-se un vector sortat.
Vectorul care se sorteaza este X.
#include<iostream.h>
int x[100],n;
void divizeaza(int s,int d,int &m)
{
int i=s,j=m+1,k=1,v[100];
while(i<=m && j<=d)
{
if(x<x[j])
{
v[k]=x;
i++;
}
else
{
v[k]=x[j];
j++;
}
k++;
}
if(i<=m)
while(i<=m)
{
v[k]=x;
i++;
k++;
}
else
while(j<=d)
{
v[k]=x[j];
j++;
k++;
}
for(k=1,i=s;k=d;k++;i++)
x=v[k];
}
void mergesort(int s,int d)
{
int m;
if(s<d)
{
divizeaza(s,d,m);
mergesort(s,m);
mergesort(m+1,d);
interclaseaza(s,d,m);
}
}
void main()
{
int n;
cout<<”n=”;
cin>>n;
for(i=1;i<=n;i++)
{
cout<<”[“<<i<<”]=”;
cin>>x;
}
mergesort(1,n);
cout<<”vectorul este sortat”<<endl;
for(i=1;i<=n;i++)
cout<<x<<” ”;
}

SORTAREA RAPIDA(QuickSort)

Prin aceasta metoda se executa urmatoarele operatii prin care sunt rearanjate elementele din cadrul vectorului:
- primul element din vector, numit pivot, este mutat in cadrul vectorului pe pozitia pe care trebuie sa se gaseasca in vectorul sortat;
- toate elementele mai mici decat el vor fi mutate in vector, in fata sa;
- toate elementele mai mari decat el vor fi mutate in vector, dupa el;
varianta 1:
#include<iostream.h>
int x[100], n;
void schimb(int &a, int &b)
{
int aux=a;
a=b;
b=aux;
}
void divizeaza(int s, int d,int &m)
{
int i=s, j=d,pi=0,pj=1;
while(i<j)
{
if(x>x[j])
{
schimb(v, v[j]);
schimp(pi,pj);
}
i=i+pi;
j=j-pj;
}
m=i;
}
void quicksort(int s,int d)
{
int m;
if(s<d)
{
divizeaza(s,d,m);
quicksort(s,m-1);
quicksort(m+1,d);
}
}
void main()
{
int i;
cout<<”n=”; cin>>n;
for(i=1;i<=n;i++)
{
cout<<”x[“<<i<<”]=”;
cin>>x;
}
quicksort(1,n);
cout<<”vectorul sortat”<<endl;
for(i=1;i<=n;i++)
cout<<x<<” ”;
}

varianta 2:

void divizeaza(int s,int s,int &m)
{
int pivot=v,i=s,j=d;
while(i<j)
{
while(vMax nested elements reachedMax nested elements reached