Problem

4/5

Iterazione sulle righe #1

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.
#include<iostream> utilizzando lo spazio dei nomi std; void TumbaWords( stringa A, stringa &w, int N ) // 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 (precedenti – 0). { int io; if (N == w.size()) {   // se tutti i caratteri sono già stati impostati sulla parola,     // quindi è necessario emettere una stringa e terminare la procedura cout << con<< finel; ritorno; } for ( i = 1; i < A.size(); i ++ ) {   // se la condizione 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[N] = A[i]; TumbaParole ( A, w, N+1 ); } } principale() { int; parola stringa; int; cin>> N; parola.resize(n); // aumenta la stringa alla dimensione n TumbaWords("KLMN", parola, 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++
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!