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)!
|