Module: subroutine. ricorsione


Problem

11/12

Iterare sulle righe

Theory Click to read/hide

Attività
Nell'alfabeto della lingua della tribù "Tumba-Yumba"; quattro lettere: "K", "L", "M" e "N". Devi visualizzare tutte le parole costituite da n lettere che possono essere costruite dalle lettere di questo alfabeto.

Il problema è un normale problema di forza bruta che può essere ridotto a un problema minore.
Sostituiremo in sequenza le lettere per la parola.
La prima posizione di una parola può essere una delle 4 lettere dell'alfabeto (K. L, M, N).
Mettiamo prima la lettera K. Quindi, per ottenere tutte le varianti con la prima lettera K, devi enumerare tutte le possibili combinazioni di lettere nelle rimanenti posizioni n - 1 e così via. (vedi foto).
Quindi, il problema si riduce a risolvere quattro problemi di lunghezza n - 1.
 
Itera su n caratteri in modo ricorsivo
w[0]='K'; // itera sugli ultimi caratteri L-1 w[0]='L'; // itera sugli ultimi caratteri L-1 w[0]='M'; // itera sugli ultimi caratteri L-1 w[0]='N'; // itera sugli ultimi caratteri L-1 w - una stringa di caratteri che memorizza la parola di lavoro.
Così, abbiamo ottenuto la ricorsività. Possiamo organizzare la soluzione del problema sotto forma di una procedura ricorsiva. 
Resta da determinare quando finirà la ricorsione? Quando tutti i caratteri sono impostati, cioè, il numero di caratteri impostati è n. In questo caso è necessario visualizzare sullo schermo la parola risultante ed uscire dalla procedura.

Il programma C# avrà questo aspetto.
// w - parametro modificabile (risultato stringa) // Alla procedura TumbaWords viene passato l'alfabeto come stringa di caratteri, // la parola parola e il numero di caratteri già impostati (all'inizio – 0) static void TumbaWords( string A, ref string w, int N ) { if (N == w.Length) // w.Length - il numero di caratteri nella stringa {   // se tutti i caratteri sono già stati impostati sulla parola,       // quindi è necessario emettere una stringa e terminare la procedura Console.WriteLine(w); ritorno; } for ( int i = 0; i < w.Length; i ++ ) // se la condizione precedente è falsa (ovvero, non tutti i caratteri sono spaziati, {     // se la condizione di cui sopra è falsa (ovvero, non tutti i caratteri sono spaziati,     // quindi nel ciclo passiamo attraverso tutti i caratteri dell'alfabeto e   // metti alternativamente il carattere nel primo spazio libero w += LA[i]; TumbaWords(A, ref w, N+1); w = w.Rimuovi(w.Lunghezza - 1); // e poi rimuovi l'ultimo carattere aggiunto,   // per creare una nuova parola con lo stesso prefisso } } vuoto statico Main() { int n = Convert.ToInt32(Console.ReadLine()); parola stringa = ""; TumbaWords("KLMN", ref word, 0); }
NOTA che w è un parametro mutabile (stringa di risultato)!

Problem

Nell'alfabeto della lingua della tribù «tumba-yumba» quattro lettere: "K", "L", "M" e "N". Devi visualizzare tutte le parole costituite da n lettere che possono essere costruite dalle lettere di questo alfabeto.
(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#
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!