Manual clasa a X a |
Tehnici de implementarea algoritmilor |
Recursivitate |
Se citesc de la tastatură două şiruri de caractere, s1 şi s2. Scrieţi un subprogram recursiv care să verifice dacă şirul s1 este anagrama şirului s2.
Pentru a verifica dacă un şir de caractere este o anagramă a altui şir , trebuie să verificăm dacă cele două şiruri conţin aceleaşi caractere, cu aceeaşi frecvenţă , dar într-o ordine diferită. Pentru a implementa această verificare prin intermediul unui subprogram recursiv, putem urma următorul algoritm:
# include < iostream >
# include < cstring >
using namespace std ;
bool verificaAnagrama ( char s1[], char s2[]) {
int n1 = strlen (s1);
int n2 = strlen (s2);
// Daca lungimea celor doi siruri este diferita, atunci nu sunt anagrame
if (n1 != n2) {
return false ;
}
// Cauta fiecare litera din primul sir in al doilea sir
for ( int i = 0 ; i < n1; i++) {
int gasit = false ;
for ( int j = 0 ; j < n2; j++) {
if (s1[i] == s2[j]) {
s2[j] = '0' ; // marcheaza litera gasita in al doilea sir
gasit = true ;
break ;
}
}
if (! gasit ) { // daca nu a gasit litera din primul sir in al doilea sir, atunci nu sunt anagrame
return false ;
}
}
return true ;
}
int main () {
char s1[ 100 ], s2[ 100 ];
cout << " Introduceti primul sir: " ;
cin >> s1;
cout << " Introduceti al doilea sir: " ;
cin >> s2;
if ( verificaAnagrama (s1, s2)) {
cout << "Cele doua siruri sunt anagrame." << endl ;
} else {
cout << "Cele doua siruri nu sunt anagrame." << endl ;
}
return 0 ;
}
Programul citeste de la tastatura cele doua siruri de caractere si le trimite catre functia verificaAnagrama , care verifica daca sirul s1 este anagrama sirului s2 . Daca cele doua siruri sunt anagrame, se afiseaza un mesaj corespunzator , altfel se afiseaza un alt mesaj.