Module: (C++) Récursivité


Problem

11/12

Itérer sur les lignes #1

Theory Click to read/hide

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) !

Problem

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 pouvant être construites à partir des lettres de cet alphabet.
(c) K.Yu. Polyakov