Attività
Nell'alfabeto della lingua della tribù «Tumba-Yumba» quattro lettere: "K", "L", "M" e "N". È necessario visualizzare sullo schermo tutte le parole composte da n lettere che possono essere costruite dalle lettere di questo alfabeto
Il problema è un normale problema di forza bruta che può essere ridotto a un problema minore.
Sostituiremo in sequenza le lettere per la parola.
La prima posizione di una parola può essere una delle 4 lettere dell'alfabeto (
K, L, M, N).
Per prima cosa, metti prima la lettera '
K'. Quindi, per ottenere tutte le varianti con la prima lettera '
K', devi enumerare tutte le possibili combinazioni di lettere nel restante
n-1 posizioni e .etc. (Guarda l'immagine)
Così, abbiamo trovato una soluzione ricorsiva: in un ciclo, passa attraverso tutte le possibili prime lettere (mettendo ogni lettera dell'alfabeto a sua volta al primo posto) e per ogni caso costruisci tutte le possibili "code"; lunghezza n-1.
Iterazione ricorsiva di caratteri
Devi interrompere la ricorsione e produrre la parola finita quando la parte rimanente è vuota (n = 0), cioè tutte le lettere sono già selezionate.
La procedura ricorsiva sarebbe simile a questa:
def TumbaWords(parola, alfabeto, n):
se n < 1:
stampa (parola)
ritorno
per c in alfabeto:
TumbaParole(parola+c, alfabeto, n - 1)