Module: (Python) Sub-rotinas. 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". É 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 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)

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.