Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda backtraking |
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 100 ;
char chars [MAX_N];
bool used [MAX_N];
void generateWords ( int n, int m, int len , char * word ) {
if ( len == m) {
cout << word << endl ;
return ;
}
for ( int i = 0 ; i < n; i++) {
if (! used [i]) {
used [i] = true ;
word [ len ] = chars [i];
generateWords (n, m, len+ 1 , word );
used [i] = false ;
}
}
}
int main () {
int n, m;
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> chars [i];
}
cin >> m;
char word [MAX_N];
memset ( used , false , sizeof ( used ));
generateWords (n, m, 0 , word );
return 0 ;
}
# include < cstring >
using namespace std ;
const int MAX_N = 100 ;
char chars [MAX_N];
bool used [MAX_N];
void generateWords ( int n, int m, int len , char * word ) {
if ( len == m) {
cout << word << endl ;
return ;
}
for ( int i = 0 ; i < n; i++) {
if (! used [i]) {
used [i] = true ;
word [ len ] = chars [i];
generateWords (n, m, len+ 1 , word );
used [i] = false ;
}
}
}
int main () {
int n, m;
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> chars [i];
}
cin >> m;
char word [MAX_N];
memset ( used , false , sizeof ( used ));
generateWords (n, m, 0 , word );
return 0 ;
}
În acest caz, putem implementa o soluție backtracking folosind un șir de caractere ca și soluție parțială, cu o lungime inițială de 0 și o lungime maximă de m. Vom folosi un șir de caractere pentru a stoca caracterele distincte citite de la tastatură și un șir de bool -uri pentru a urmări care dintre caractere au fost deja folosite în soluție.
În funcția backtracking , vom parcurge recursiv toate caracterele distincte și vom adăuga caracterul curent în soluție parțială dacă acesta nu a fost deja folosit și dacă lungimea soluției parțiale este mai mică decât m. Dacă lungimea soluției parțiale este egală cu m, vom afișa soluția. În caz contrar, vom continua să adăugăm caractere și să generăm soluții parțiale până la atingerea lungimii maxime.