Problem

4/5

Iterando sobre las líneas #1

Theory Click to read/hide

Tarea
En el alfabeto de la lengua de la tribu "Tumba-Yumba"; cuatro letras: "K", "L", "M" y "N". Debe mostrar todas las palabras que constan de n letras que se pueden construir a partir de las letras de este alfabeto.

El problema es un problema normal de fuerza bruta que se puede reducir a un problema más pequeño.
Sustituiremos secuencialmente las letras por la palabra.
La primera posición de una palabra puede ser una de las 4 letras del alfabeto (K. L, M, N).
Pongamos la letra K primero. Luego, para obtener todas las variantes con la primera letra K, debe enumerar todas las combinaciones posibles de letras en las posiciones restantes de n - 1 y así sucesivamente. (ver imagen).
Así, el problema se reduce a resolver cuatro problemas de longitud n - 1.
 
Iterar sobre n caracteres recursivamente
w[0]='K'; // iterar sobre los últimos caracteres L-1 w[0]='L'; // iterar sobre los últimos caracteres L-1 w[0]='M'; // iterar sobre los últimos caracteres L-1 w[0]='N'; // iterar sobre los últimos caracteres L-1 w - una cadena de caracteres que almacena la palabra de trabajo.
Así, tenemos recursividad. Podemos disponer la solución del problema en forma de procedimiento recursivo. 
¿Queda por determinar cuándo terminará la recursividad? Cuando todos los caracteres están configurados, es decir, el número de caracteres configurados es n. En este caso, debe mostrar la palabra resultante en la pantalla y salir del procedimiento.

El programa C++ se verá así.
#incluir<iostream> utilizando el espacio de nombres estándar; void TumbaWords( cadena A, cadena &w, int N ) // w - parámetro modificable (resultado de cadena) // Al procedimiento TumbaWords se le pasa el alfabeto como cadena de caracteres, // la palabra palabra y el número de caracteres ya establecidos (antes de – 0). { ent yo; if (N == w.tamaño()) {   // si ya se han establecido todos los caracteres en la palabra,     // entonces es necesario generar una cadena y finalizar el procedimiento cout << w<< fin; devolver; } for ( i = 1; i < A.tamaño(); i ++ ) {   // si la condición anterior es falsa (es decir, no todos los caracteres están espaciados,   // luego en el bucle repasamos todos los caracteres del alfabeto y // coloca alternativamente el carácter en el primer espacio libre w[N] = A[i]; TumbaPalabras ( A, w, N+1 ); } } principal() { interno; palabra de cadena; interno; cin>> norte; palabra.redimensionar(n); // aumenta la cadena al tamaño n TumbaPalabras( "KLMN", palabra, 0 ); }
TENGA EN CUENTA que w es un parámetro mutable (cadena de resultado)!

Problem

En el alfabeto de la lengua de la tribu «tumba-yumba» cuatro letras: "K", "L", "M" y "N". Debe mostrar todas las palabras que constan de n letras que se pueden construir a partir de las letras de este alfabeto.
(c) K.Yu. Poliakov

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!