Tâche
Dans l'alphabet de la langue de la tribu "Tumba-Yumba" ; quatre lettres : "K", "L", "M" et "N". Vous devez afficher tous les mots composés de n lettres qui peuvent être construits à partir des lettres de cet alphabet.
Le problème est un problème normal de force brute qui peut être réduit à un problème plus petit.
Nous substituerons séquentiellement des lettres au mot.
La première position d'un mot peut être l'une des 4 lettres de l'alphabet (K. L, M, N).
Mettons la lettre K en premier. Ensuite, afin d'obtenir toutes les variantes avec la première lettre K, vous devez énumérer toutes les combinaisons possibles de lettres dans les positions n - 1 restantes et ainsi de suite. (voir photo).
 Ainsi, le problème se réduit à résoudre quatre problèmes de longueur n - 1.
Itérer sur n caractères de manière récursive
w[0]='K'; // itération sur les derniers L-1 caractères
w[0]='L'; // itération sur les derniers L-1 caractères
w[0]='M'; // itération sur les derniers L-1 caractères
w[0]='N'; // itération sur les derniers L-1 caractères
w - une chaîne de caractères qui stocke le mot de travail.
Ainsi, nous avons obtenu la récursivité. Nous pouvons organiser la solution du problème sous la forme d'une procédure récursive.
Reste à déterminer quand la récursivité prendra fin ? Lorsque tous les caractères sont définis, c'est-à-dire que le nombre de caractères définis est n. Dans ce cas, vous devez afficher le mot résultant à l'écran et quitter la procédure.
Le programme C++ ressemblera à ceci.
#include<iostream>
en utilisant l'espace de noms std ;
void TumbaWords( chaîne A, chaîne &w, int N )
// w - paramètre modifiable (string-result)
// La procédure TumbaWords reçoit l'alphabet sous forme de chaîne de caractères,
// le mot mot et le nombre de caractères déjà définis (précédant – 0).
{
int je ;
si (N == w.taille())
{
// si tous les caractères ont déjà été définis pour le mot,
// alors il faut sortir une chaîne et terminer la procédure
cout << w<< fin ;
retour;
}
pour ( je = 1; je < A.size(); je ++ )
{
// si la condition ci-dessus est fausse (c'est-à-dire que tous les caractères ne sont pas espacés,
// puis dans la boucle on parcourt tous les caractères de l'alphabet et
// place alternativement le caractère sur la première case libre
w[N] = A[i] ;
TumbaWords ( A, w, N+1 );
}
}
principal()
{
international ;
mot-clé ;
international ;
cin>> n;
word.resize(n); // augmente la chaîne à la taille n
TumbaWords( "KLMN", mot, 0 );
}
NOTEZ que w est un paramètre modifiable (chaîne de résultat) !
|