Tarefa
No alfabeto da língua da tribo «Tumba-Yumba» quatro letras: "K", "L", "M" e "N". É necessário exibir na tela todas as palavras compostas por 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).
Primeiro, coloque 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 no
n-1 restante código> posições e .etc. (Ver foto)
Assim, chegamos a uma solução recursiva: em um loop, percorra todas as primeiras letras possíveis (colocando cada letra do alfabeto na primeira posição) e para cada caso construa todas as "caudas" possíveis; comprimento n-1
.
Interação recursiva de caracteres
Você precisa parar a recursão e produzir a palavra finalizada quando a parte restante estiver vazia (n = 0
), ou seja, todas as letras já estão selecionadas.
O procedimento recursivo ficaria assim:
def TumbaWords(palavra, alfabeto, n):
se n < 1:
imprimir(palavra)
retornar
para c no alfabeto:
TumbaWords(palavra+c, alfabeto, n - 1)