Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda backtraking |
# include < iostream >
using namespace std ;
int n;
int cifre[ 10 ] = { 0 , 2 , 4 , 6 , 8 }; // cifrele pare posibile
int solutie [ 10 ];
void afisare () {
for ( int i = 1 ; i <= n; i++) {
cout << solutie [i];
}
cout << endl ;
}
void back ( int k) {
if (k == n + 1 ) { // solutie gasita
afisare ();
} else {
for ( int i = 1 ; i <= 4 ; i++) { // parcurgem cifrele posibile
if (k == 1 && cifre[i] == 0 ) { // daca suntem la prima cifra si cifra curenta e 0, trecem la urmatoarea
continue ;
}
solutie [k] = cifre[i]; // adaugam cifra la solutie
back (k + 1 ); // generam solutiile pentru cifrele ramase
}
}
}
int main () {
cout << " Introduceti numarul de cifre: " ;
cin >> n;
back ( 1 );
return 0 ;
}
using namespace std ;
int n;
int cifre[ 10 ] = { 0 , 2 , 4 , 6 , 8 }; // cifrele pare posibile
int solutie [ 10 ];
void afisare () {
for ( int i = 1 ; i <= n; i++) {
cout << solutie [i];
}
cout << endl ;
}
void back ( int k) {
if (k == n + 1 ) { // solutie gasita
afisare ();
} else {
for ( int i = 1 ; i <= 4 ; i++) { // parcurgem cifrele posibile
if (k == 1 && cifre[i] == 0 ) { // daca suntem la prima cifra si cifra curenta e 0, trecem la urmatoarea
continue ;
}
solutie [k] = cifre[i]; // adaugam cifra la solutie
back (k + 1 ); // generam solutiile pentru cifrele ramase
}
}
}
int main () {
cout << " Introduceti numarul de cifre: " ;
cin >> n;
back ( 1 );
return 0 ;
}
În această soluție, am declarat un vector cifre care conține cifrele pare posibile și un vector solutie care va conține cifrele numărului pe care îl generăm. Apoi, am definit funcția afisare pentru a afișa soluția curentă și funcția back pentru a genera toate numerele posibile.
În funcția back , verificăm dacă am găsit o soluție completă, adică dacă am adăugat n cifre la soluție. Dacă nu, parcurgem cifrele posibile și verificăm dacă putem adăuga cifra curentă la soluție (de exemplu, dacă suntem la prima cifră, nu putem adăuga 0). Apoi, apelăm recursiv back pentru a genera soluțiile pentru cifrele ramase.
În funcția main , citim de la tastatură numărul de cifre și apelăm funcția back pentru a genera toate numerele posibile.