Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda backtraking |
# include < iostream >
void backtrack ( int n, int sum , int count3, int count5) {
if ( sum == n) {
std :: cout << count3 << " * 3 + " << count5 << " * 5 = " << n << std :: endl ;
return ;
}
if ( sum > n) {
return ;
}
if ( sum + 3 <= n) {
backtrack (n, sum + 3 , count3 + 1 , count5);
}
if ( sum + 5 <= n) {
backtrack (n, sum + 5 , count3, count5 + 1 );
}
}
int main () {
int n;
std :: cout << " Introduceti numarul natural n: " ;
std ::cin >> n;
backtrack (n, 0 , 0 , 0 );
return 0 ;
}
void backtrack ( int n, int sum , int count3, int count5) {
if ( sum == n) {
std :: cout << count3 << " * 3 + " << count5 << " * 5 = " << n << std :: endl ;
return ;
}
if ( sum > n) {
return ;
}
if ( sum + 3 <= n) {
backtrack (n, sum + 3 , count3 + 1 , count5);
}
if ( sum + 5 <= n) {
backtrack (n, sum + 5 , count3, count5 + 1 );
}
}
int main () {
int n;
std :: cout << " Introduceti numarul natural n: " ;
std ::cin >> n;
backtrack (n, 0 , 0 , 0 );
return 0 ;
}
Acest program folosește o funcție de backtracking numită backtrack () , care primește patru argumente: n este numărul care trebuie descompus, sum este suma parțială actuală, iar count3 și count5 sunt numărul de apariții ale numerelor 3 și 5 în suma parțială, respectiv.
Funcția de backtracking verifică dacă suma parțială este egală cu n . Dacă este, afișează descompunerea. Altfel, se adaugă la suma parțială fie 3, fie 5, dacă acest lucru nu depășește n . Apoi, se continuă procesul de backtracking pentru a explora posibilitățile rămase.
Rețineți că această abordare poate fi ineficientă pentru valori mari ale lui n , iar optimizarea acesteia depinde de cerințele și constrângerile problemei.