Metoda backtracking
Introducere
Metoda backtracking poate fi aplicată în rezolvarea problemelor care respectă următoarele condiții:
- soluția poate fi reprezentată printr-un tablou x[]=(x[1], x[2], ..., x[n]), fiecare element x[i] aparținând unei mulțimi cunoscute Ai;
- fiecare mulțime Ai este finită, iar elementele ei se află într-o relație de ordine precizată – de multe ori cele n mulțimi sunt identice;
- se cer toate soluțiile problemei sau se cere o anumită soluție care nu poate fi determinată într-un alt mod (de regulă mai rapid).
Algoritmul de tip backtracking construiește vectorul x[] (numit vector soluție) astfel:
- Fiecare pas k, începând (de regulă) de la pasul 1, se prelucrează elementul curent x[k] al vectorului soluție:
- x[k] primește pe rând valori din mulțimea corespunzătoare Ak;
La fiecare pas se verifică dacă configurația curentă a vectorului soluție poate duce la o soluție finală – dacă valoarea lui x[k] este corectă în raport cu x[1], x[2], … x[k-1]:
dacă valoarea nu este corectă, elementul curent X[k] primește următoarea valoare din Ak sau revenim la elementul anterior x[k-1], dacă X[k] a primit toate valorile din Ak – pas înapoi;
dacă valoarea lui x[k] este corectă (avem o soluție parțială), se verifică existența unei soluții finale a problemei:
dacă configurația curentă a vectorului soluție x reprezintă soluție finală (de regulă) o afișăm;
dacă nu am identificat o soluție finală trecem la următorul element, x[k+1], și reluăm procesul pentru acest element – pas înainte.
Pe măsură ce se construiește, vectorul soluție x[] reprezintă o soluție parțială a problemei. Când vectorul soluție este complet construit, avem o soluție finală a problemei.
Probleme rezolvate
Problema 1
Se citeste un cuvant format din maxim 10 litere mici distincte. Afisati in ordine lexicografica toate anagramele cuvantului citit care au proprietatea ca nu contin doua vocale alaturate si nici doua consoane alaturate (practic vocalele si consoanele trebuie sa alterneze).
Daca acest lucru nu este posibil se va afisa mesajul IMPOSIBIL.
Exemplu:
Daca s="cosmina"
anagramele vor fi:
caminos
camison
camonis
...
sonimac
Daca s="cosmin" se va afisa IMPOSIBIL
Rezolvare
#include < iostream> #include < cstring> #include < cstdlib> using namespace std; int n,X[12],P[12]; char s[12]; void afisare() { for(int i=1;i<=n;i++) cout<<s[X[i]-1]; cout<< endl; } int valid(int k) { if(k>1) //daca sunt cel putin la cea de-a doua litera { if(strchr("aeiou",s[X[k]-1])==0 && strchr("aeiou",s[X[k-1]-1])==0) return 0; //doua consoane alaturare => 0 if(strchr("aeiou",s[X[k]-1])!=0 && strchr("aeiou",s[X[k-1]-1])!=0) return 0; //doua vocale alaturate => 0 } return 1; } void back(int k) { for(int i=1;i<=n;i++) if(!P[i]) { P[i]=1; X[k]=i; if(valid(k)) if(k==n) afisare(); else back(k+1); P[i]=0; } } void ordonare(char s[]) { int l=strlen(s); for(int i=0;i<l;i++) for(int j=i+1;j<l;j++) if(s[i]>s[j]) { char aux=s[i]; s[i]=s[j]; s[j]=aux; } } int main() { cin>>s; n=strlen(s); int cv=0,cc=0; for(int i=0;i<n;i++) if(strchr("aeiou",s[i])==0) cc++;//numaram consoanele else cv++;//numaram vocalele if(abs(cc-cv)>1) cout<<"IMPOSIBIL";//diferenta>1 => imposibil else { ordonare(s);//ordonez alfabetic cuvantul back(1); } return 0; }
Problema 2
Se citesc numerele naturale n,a,b,p,q (n<=20, a<=b<=n, p<=q) si apoi n punctaje diferite ale unor intrebari. Sa se afiseze toate modurile in care se poate alege pentru un test un numar de intrebari cuprins intre a si b si care sa aiba punctajul total intre p si q.
Exemplu:
7 4 5 20 25
6
5
7
8
2
3
10
se vor afisa
6 5 7 2
6 5 7 2 3
6 5 7 3
6 5 8 2
6 5 8 2 3
....
8 2 3 10
Rezolvare
#include < fstream>
using namespace std;
ifstream fin("i.in");
ofstream fout("i.out");
int X[21],Q[21],n,a,b,p,q;
void afisare(int k)
{
for(int i=1;i<=k;i++)
fout<<Q[X[i]]<<" ";
fout<<endl;
}
void back(int k, int pp)
{
for(int i=X[k-1]+1;i<=n;i++)
{
X[k]=i;
pp=pp+Q[X[k]];
if(pp<=q)
{
if(k>=a && k<=b && pp>=p) afisare(k);
back(k+1,pp);
}
pp=pp-Q[X[k]];
}
}
int main()
{
fin>>n>>a>>b>>p>>q;
for(int i=1;i<=n;i++)
fin>>Q[i];
back(1,0);
return 0;
}
Probleme propuse
1) Sa se afiseze in ordine alfabetica anagramele unui cuvant format din litere distincte.
Exemplu:
date.in
rac
date.out
acr
arc
car
cra
rac
rca
2) Se citeste un numar natural n. Generati si afisati toate combinatiile de cate n cifre binare care nu au doua cifre de 1 alaturate.
Exemplu:
n=3
combinatiile sunt:
0 0 0
0 0 1
0 1 0
1 0 0
1 0 1
3) Se citeste un numar natural n si apoi o multime cu n elemente numere naturale. Folosind interschimbari de elemente generati si afisati permutarile multimii citite.
4) Se citesc doua numere naturale n si k, k fiind mai mic decat numarul de cifre ale numarului n. Afisati cel mai mare numar care se poate forma eliminand k cifre din numarul n.
Exemplu:
n=3452234
k=4
numarul cautat este 534
5) Se citesc doua numere naturale n si k. Generati si afisati toate toate numerele naturale formate din n cifre care contin exact k cifre de 1.