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

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <string>
#include <iostream>
using namespace std;

void TumbaWords( string A, string &w, int N )
{                      
}

main()
{
  string word;
  int n;
  cin>>n;
  word.resize(n);
  TumbaWords ( "KLMN", word, 0 );
}

     

Program check result

To check the solution of the problem, you need to register or log in!