Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda backtraking |
# include < iostream >
void bt ( int solutie [], int k, int suma, int n) {
if (suma == n) {
for ( int i = 0 ; i < k; i++) {
std :: cout << solutie [i] << " " ;
}
std :: cout << std :: endl ;
} else {
for ( int i = (k > 0 ? solutie [k - 1 ] + 1 : 1 ); i <= n; i++) {
if (suma + i <= n) {
solutie [k] = i;
bt ( solutie , k + 1 , suma + i, n);
}
}
}
}
int main () {
int n;
std :: cout << " Introduceti numarul natural n: " ;
std ::cin >> n;
int solutie [n];
bt ( solutie , 0 , 0 , n);
return 0 ;
}
void bt ( int solutie [], int k, int suma, int n) {
if (suma == n) {
for ( int i = 0 ; i < k; i++) {
std :: cout << solutie [i] << " " ;
}
std :: cout << std :: endl ;
} else {
for ( int i = (k > 0 ? solutie [k - 1 ] + 1 : 1 ); i <= n; i++) {
if (suma + i <= n) {
solutie [k] = i;
bt ( solutie , k + 1 , suma + i, n);
}
}
}
}
int main () {
int n;
std :: cout << " Introduceti numarul natural n: " ;
std ::cin >> n;
int solutie [n];
bt ( solutie , 0 , 0 , n);
return 0 ;
}
Acest program citește un număr natural n și generează toate descompunerile sale în numere naturale distincte. Funcția bt () este recursivă și generează soluțiile posibile pentru un anumit nivel k . Atunci când suma elementelor din soluție este egală cu n , soluția este afișată.
Rețineți că acest cod poate fi optimizat în funcție de cerințe și constrângeri.