Module: (C++) Recursão


Problem

11/12

Iterando sobre as linhas #1

Theory Click to read/hide

Tarefa
No alfabeto da língua da tribo "Tumba-Yumba"; quatro letras: "K", "L", "M" e "N". Você precisa exibir todas as palavras que consistem em n letras que podem ser construídas a partir das letras deste alfabeto.

O problema é um problema normal de força bruta que pode ser reduzido a um problema menor.
Substituiremos sequencialmente as letras da palavra.
A primeira posição de uma palavra pode ser uma das 4 letras do alfabeto (K. L, M, N).
Vamos colocar a letra K primeiro. Então, para obter todas as variantes com a primeira letra K, você precisa enumerar todas as combinações possíveis de letras nas posições n - 1 restantes e assim por diante. (veja a foto).
Assim, o problema se reduz a resolver quatro problemas de comprimento n - 1.
 
Iterar sobre n caracteres recursivamente
w[0]='K'; // itera sobre os últimos caracteres L-1 w[0]='L'; // itera sobre os últimos caracteres L-1 w[0]='M'; // itera sobre os últimos caracteres L-1 w[0]='N'; // itera sobre os últimos caracteres L-1 w - uma cadeia de caracteres que armazena a palavra de trabalho.
Assim, temos recursão. Podemos organizar a solução do problema na forma de um procedimento recursivo. 
Resta determinar quando a recursão terminará? Quando todos os caracteres são definidos, ou seja, o número de caracteres definidos é n. Nesse caso, você precisa exibir a palavra resultante na tela e sair do procedimento.

O programa C++ ficará assim.
#include<iostream> usando namespace std; void TumbaWords( string A, string &w, int N ) // w - parâmetro alterável (string-result) // O procedimento TumbaWords recebe o alfabeto como uma string de caracteres, // a palavra word e o número de caracteres já definidos (precedendo – 0). { int eu; if (N == w.size()) {   // se todos os caracteres já tiverem sido definidos para a palavra,     // então é necessário enviar uma string e terminar o procedimento cout << w<< endl; retornar; } for ( i = 1; i < A.size(); i++ ) {   // se a condição acima for falsa (ou seja, nem todos os caracteres são espaçados,   // então no loop passamos por todos os caracteres do alfabeto e // coloca alternadamente o caractere no primeiro espaço livre w[N] = A[i]; Palavras Tumba ( A, w, N+1 ); } } principal() { int; palavra-chave; int; cin>> n; palavra.resize(n); // aumenta a string para o tamanho n TumbaPalavras("KLMN", palavra, 0); }
OBSERVE que w é um parâmetro mutável (string de resultado)!

Problem

No alfabeto da língua da tribo «tumba-yumba» quatro letras: "K", "L", "M" e "N". Você precisa exibir todas as palavras que consistem em n letras que podem ser construídas a partir das letras deste 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!