precizati si descrieti variabilele si functiile utilizate pentru generarea permutarilor unei multimi de n elemente
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
int x[10] ,n;
void Afis()
{
for( int j=1;j<=n;j++)
cout<<x[j]<<" ";
cout<<endl;
}
bool OK(int k){
for(int i=1;i<k;++i)
if(x[k]==x[i])
return false;
return true;
}
bool Solutie(int k)
{
return k == n;
}
void back(int k){
for(int i=1 ; i<=n ; ++i)
{
x[k]=i;
if( OK(k) )
if(Solutie(k))
Afis();
else
back(k+1);
}
}
int main(){
cin>>n;
back(1);
return 0;
}
Explicație:
Problema se rezolva prin metoda backtracking.
Semnificația funcțiilor
void Afis(); afișează soluția curentă. Când se apelează, vectorul soluție x are n elemente, reprezentând o permutare completă;
bool OK(int k); verifică condițiile interne. La apel, x[k] tocmai a primit o valoare conform condițiilor externe. Prin funcția OK() se va verifica dacă această valoare este validă;
bool Solutie(int k); verifică dacă avem o soluție completă. Acest lucru se întâmplă când permutarea este completă – am dat o valoare corectă ultimului element al tabloului, x[n], adică atunci când k=n;
void back(int k); – apelul acestei funcții dă valori posibile elementului x[x] al vectorului soluție și le verifică:
se parcurg valorile pe care le pot lua elementele vectorului, conform condițiilor externe (în acest caz, 1..n);
se memorează în x[k] valoarea curentă;
dacă valoarea lui x[k] este corectă, conform condițiilor interne, se verifică dacă avem o soluție completă. În caz afirmativ se afișează această soluție, în caz contrar se trece la următorul element, prin apelul recursiv;
la finalul parcurgerii, se revine la elementul anterior al vectorului x, prin revenirea din apelul recursiv.