Module: subrutinas recursión


Problem

11/12

Iterando sobre líneas

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í.
// 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 (al principio – 0) static void TumbaWords( cadena A, ref cadena w, int N ) { if (N == w.Length) // w.Length - el número de caracteres en la cadena {   // si ya se han establecido todos los caracteres en la palabra,       // entonces es necesario generar una cadena y finalizar el procedimiento Consola.WriteLine(w); devolver; } for ( int i = 0; i < w.Length; i ++ ) // si la condición anterior es falsa (es decir, no todos los caracteres están espaciados, {     // 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 += A[i]; TumbaPalabras(A, ref w, N+1); w = w.Remove(w.Length - 1); // y luego elimine el último carácter agregado,   // para hacer una nueva palabra con el mismo prefijo } } vacío estático principal () { int n = Convert.ToInt32(Console.ReadLine()); palabra de cadena = ""; TumbaWords("KLMN", ref 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#
1 
using System;
2 
class Program
3 
{
4 
    static void TumbaWords(string A, ref string w, int N)
5 
    {
6 
        if (N == w.Length)
7 
        {
8
9
10
11
12 
        for (int i = 0; i < A.Length; i++)
13 
        {
14 
            w += A[i];
15
16 
            w = w.Remove(w.Length - 1);
17 
        }
18 
    }
19 
    static void Main()
20 
    {
21 
        int n = Convert.ToInt32(Console.ReadLine());
22 
        string word = "";
23
24 
    }
25 
}

     

Program check result

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