# include < iostream >
using namespace std ;
int n, m, p;
int solutie [ 100 ];
bool utilizat[ 100 ];
int obiecte_precizate [ 100 ];
void tipar () {
for ( int i = 0 ; i < m; i++) {
cout << solutie [i] << ' ' ;
}
cout << endl ;
}
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
}
if (utilizat[obiect]) count_precizate ++;
// Pentru cazul a)
return count_precizate == p;
}
void bt ( int k, int start) {
if (k == m) {
tipar ();
return ;
}
for ( int i = start; i <= n; i++) {
if ( valid (k, i)) {
solutie [k] = i;
bt (k + 1 , i + 1 );
}
}
}
int main () {
cout << " Introduceti numarul de obiecte (n): " ;
cin >> n;
cout << " Introduceti numarul de obiecte din solutie (m): " ;
cin >> m;
cout << " Introduceti numarul de obiecte precizate (p): " ;
cin >> p;
cout << " Introduceti obiectele precizate: " ;
for ( int i = 0 ; i < p; i++) {
int obiect;
cin >> obiect;
utilizat[obiect] = true ;
}
bt ( 0 , 1 );
return 0 ;
}
Pentru a rezolva această problemă, voi prezenta un exemplu care se ocupă de cazul a) și voi arăta cum să modifici programul pentru a face față celorlalte cazuri.
Pentru a rezolva celelalte cazuri (b-g), trebuie să modifici funcția valid() în consecință și să adaugi variabile suplimentare, dacă este necesar. De exemplu, pentru cazul b), condiția de validare ar fi count_precizate == 0
Pentru a rezolva cazul c), trebuie să modificăm funcția valid() astfel încât să se asigure că soluția curentă conține exact un obiect din cele p obiecte precizate. Iată cum ar trebui să arate funcția valid() pentru acest caz:
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
}
if (utilizat[obiect]) count_precizate ++;
// Pentru cazul c)
if (k == m - 1 ) {
return count_precizate == 1 ;
} else {
return count_precizate <= 1 ;
}
}
Aici, am modificat condiția de validare pentru a verifica dacă ne aflăm la ultimul obiect din soluție (k == m - 1). Dacă acesta este cazul, ne asigurăm că count_precizate este exact 1, ceea ce înseamnă că am inclus exact un obiect dintre cele p obiecte precizate în soluție. Dacă nu suntem la ultimul obiect, ne asigurăm că count_precizate nu depășește 1, astfel încât să lăsăm loc pentru exact un obiect precizat.
Restul programului rămâne neschimbat, iar funcția bt () va genera toate soluțiile posibile care îndeplinesc condiția specificată în funcția valid() .
d) Conţin cel puţin un obiect din p obiecte precizate:
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
}
if (utilizat[obiect]) count_precizate ++;
// Pentru cazul d)
if (k == m - 1 ) {
return count_precizate >= 1 ;
} else {
return true ;
}
}
e) Conţin exact q obiecte din p obiecte precizate:
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
}
if (utilizat[obiect]) count_precizate ++;
// Pentru cazul e)
if (k == m - 1 ) {
return count_precizate == q;
} else {
return count_precizate <= q;
}
}
f) Conțin exact q obiecte din p obiecte precizate și nu conțin r obiecte precizate:
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
int count_r = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
if ( utilizat_r [ solutie [i]]) count_r ++;
}
if (utilizat[obiect]) count_precizate ++;
if ( utilizat_r [obiect]) count_r ++;
// Pentru cazul f)
if (k == m - 1 ) {
return count_precizate == q && count_r == 0 ;
} else {
return count_precizate <= q && count_r == 0 ;
}
}
g) Conțin exact q obiecte din p obiecte precizate și nu conţin s obiecte din r obiecte precizate:
bool valid ( int k, int obiect) {
int count_precizate = 0 ;
int count_r = 0 ;
for ( int i = 0 ; i < k; i++) {
if (utilizat[ solutie [i]]) count_precizate ++;
if ( utilizat_r [ solutie [i]]) count_r ++;
}
if (utilizat[obiect]) count_precizate ++;
if ( utilizat_r [obiect]) count_r ++;
// Pentru cazul g)
if (k == m - 1 ) {
return count_precizate == q && count_r <= r - s;
} else {
return count_precizate <= q && count_r <= r - s;
}
}