Probleme Rezolvate

O bară are lungimea L. Se consideră n repere de lungimi diferite. Să se genereze toate posibilitățile de a tăia bara după reperele existente, fără să rămână rest la tăiere, un reper putând fi folosit de mai multe ori. Se poate ca unele repere să nu fie folosite Se citesc dintr-un fişier text, de pe primul rând, lungimea barei — L şi numărul de repere —n, iar de pe următorul rând, reperele. Numerele de pe un rând sunt separate prin spațiu.

# include < iostream >
# include < fstream >
const int MAX_REPERE = 100 ;
void backtrack ( int L, int currentLength , int repere[], int n, int solution [], int size ) {
if ( currentLength == L) {
for ( int i = 0 ; i < size ; ++i) {
std :: cout << solution [i] << (i < size - 1 ? " + " : " = " );
}
std :: cout << L << std :: endl ;
return ;
}
if ( currentLength > L) {
return ;
}
for ( int i = 0 ; i < n; ++i) {
solution [ size ] = repere[i];
backtrack (L, currentLength + repere[i], repere, n, solution , size + 1 );
}
}
int main () {
int L, n;
int repere[MAX_REPERE];
std :: ifstream inputFile ( "date_intrare.txt" ) ;
if (! inputFile. is_open ()) {
std :: cout << "Eroare la deschiderea fisierului ." << std :: endl ;
return 1 ;
}
inputFile >> L >> n;
for ( int i = 0 ; i < n; ++i) {
inputFile >> repere[i];
}
inputFile. close ();
int solution [MAX_REPERE];
backtrack (L, 0 , repere, n, solution , 0 );
return 0 ;
}

În acest cod, funcția backtrack explorează toate posibilitățile de tăiere a barei, adăugând succesiv lungimile reperele și verificând dacă lungimea curentă ajunge la L . Dacă lungimea curentă depășește L , funcția de backtracking se întoarce imediat, fără a explora în continuare posibilitățile. În cazul în care lungimea curentă este egală cu L , soluția parțială este afișată.
Asigurați-vă că aveți un fișier date_intrare.txt în directorul în care rulează programul, cu datele de intrare în formatul specificat.
E de fișier de intrare (date_intrare.txt) pentru programul de mai sus:
20 5
2 3 5 7 10
Acest fișier indică următoarele informații:
Programul va afișa toate combinațiile posibile de a tăia bara de lungime 20 folosind reperele date.