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