Esercizio 5 seconda simulazione d'esame

a
alessio.palma (1480 points)
0 34 56
asked Jan 27, 2019 in Info sul corso e sugli esami by alessio.palma (1,480 points)
edited Jan 28, 2019 by alessio.palma

def es5(parola):
    '''
    Es 5: 6 punti
        
    Si definisca la funzione ricorsiva (o che usa una vostra funzione ricorsiva)  
    es2(parola), che presa in input una stringa di caratteri  parola restituisce la lista delle  
    diverse "sottoparole crescenti"  di parola. Le sottoparole devono comparire nella lista in ordine lessicografico.
    Si ricorda che una sottoparola e' quello che si ottiene da una parola concellandone 0 o piu'
    caratteri (in testa, in coda o nel mezzo).
    Inoltre una sottoparola si dice crescente se i caratteri che la compongono
    letti da sinistra  a destra risultano ordinati lessicograficamente.
    
    Ad esempio  la lista restituita da es5('zanzara') sara'
    ['a', 'aa', 'aaa', 'aar', 'an', 'anr', 'anz', 'ar', 'az', 'n', 'nr', 'nz', 'r', 'z', 'zz']
    '''
    # inserisci qui il tuo codice

Idee per risolverlo? 

366 views

1 Answer

_andrea_ (45670 points)
2 40 297
answered Jan 27, 2019 by _andrea_ (45,670 points)
Caso base se la parola ha una lettera, ritorna {lettera}. Caso ricorsivo: crei un insieme, per ogni lettera la togli creando così una sottoparola, la aggiungi all'insieme e lo espandi con tutte le sottoparole di quella sottoparola. Ritorni l'insieme finale ottenuto dalle sottoparole di parola e dalle sottoparole di tutte le sottoparole di parola. Prima di chiamare la ricorsione controlli che quella sottoparola non sia già presente nell'insieme, sennò crei ripetizioni e ci mette troppo
a
alessio.palma (1480 points)
0 34 56
commented Jan 28, 2019 by alessio.palma (1,480 points)
edited Jan 28, 2019 by alessio.palma
con l'algoritmo che ho trovato sul diario delle lezioni non riesco a visualizzare il risultato degli ultimi due test (troppo lento), @_andrea_ puoi postare il tuo algoritmo?
_andrea_ (45670 points)
2 40 297
commented Jan 28, 2019 by _andrea_ (45,670 points)
Scambiarsi codice è vietato, non so se vale anche in questo caso però. Comunque l'ho spiegato già abbastanza bene: come caso base metto se la parola ha una lettera, altrimenti creo un insieme di tutte le sotto parole che si ottengono levando una lettera e chiamo ricorsivamente su ogni parola, ampliando l'insieme con il risultato e controllando sempre se la parola su cui chiamo la funzione non sia già presente nell'insieme di parole controllate (che è diverso da quello delle sottoparole)
a
alessio.palma (1480 points)
0 34 56
commented Jan 28, 2019 by alessio.palma (1,480 points)
per aggiornare l'insieme usi .update()? se ho capito bene quindi la chiamata ricorsiva va messa dentro l'update, una cosa del genere insieme.update(es5(nuovaparola)), e il controllo su cosa lo fai? su questa 'nuovaparola' che non deve essere nell'insieme risultante finale ? P.S: nuovaparola sarebbe una delle parole che si ottiene levando una lettera dalla parola precedente
_andrea_ (45670 points)
2 40 297
commented Jan 28, 2019 by _andrea_ (45,670 points)
Intanto come parametro ho anche l'insieme dee parole su cui ho chiamato già la ricorsione, inizialmente vuoto. Ogni volta che chiamo la ricorsione ci aggiungo la parola su cui l'ho chiamata. Per aggiornarlo faccio insieme|=ricorsione
a
alessio.palma (1480 points)
0 34 56
commented Jan 28, 2019 by alessio.palma (1,480 points)
perfetto grazie