online: 6; azi: 611; total: 51066 Manual clasa a xi a - Tehnici de programare - Metoda backtraking

Probleme Rezolvate



Manual clasa a Xi a

Tehnici de programare

Metoda backtraking

Se consideră n mulțimi de cuvinte Ai, fiecare mulțime având nj cuvinte. Să se genereze toate textele de n cuvinte care se pot forma cu cuvintele din aceste mulțimi, cuvântul i din text aparținând mulțimii Aj .
# include < iostream >
const int MAX_SETS = 10 ;
const int MAX_WORDS = 10 ;
const int MAX_WORD_LENGTH = 20 ;
void backtracking ( int level , int n, char sets [MAX_SETS][MAX_WORDS][MAX_WORD_LENGTH], char solution [MAX_SETS][MAX_WORD_LENGTH]) {
if ( level == n) {
for ( int i = 0 ; i < n; ++i) {
std :: cout << solution [i] << ' ' ;
}
std :: cout << std :: endl ;
return ;
}
for ( int i = 0 ; i < MAX_WORDS && sets [ level ][i][ 0 ] != '\0' ; ++i) {
for ( int j = 0 ; j < MAX_WORD_LENGTH; ++j) {
solution [ level ][j] = sets [ level ][i][j];
if ( sets [ level ][i][j] == '\0' ) break ;
}
backtracking ( level + 1 , n, sets , solution );
}
}
int main () {
int n;
std ::cin >> n;
char sets [MAX_SETS][MAX_WORDS][MAX_WORD_LENGTH] = { 0 };
for ( int i = 0 ; i < n; ++i) {
int nj ;
std ::cin >> nj ;
for ( int j = 0 ; j < nj ; ++j) {
std ::cin >> sets [i][j];
}
}
char solution [MAX_SETS][MAX_WORD_LENGTH] = { 0 };
backtracking ( 0 , n, sets , solution );
return 0 ;
}

Date de intrare:
3
2
ana are
2
mere pere
2
verzi rosii
Explicație:
Date de ieșire:
ana mere verzi
ana mere rosii
ana pere verzi
ana pere rosii
are mere verzi
are mere rosii
are pere verzi
are pere rosii