Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Esercizio 5 seconda simulazione d'esame

a
alessio.palma (1480 points)
9 36 56
in Info sul corso e sugli esami by (1.5k points)
edited by

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? 

784 views

1 Answer

_andrea_ (45670 points)
11 42 297
by (45.7k 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
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Ah e ovviamente alla fine rimuovi tutte le sottoparole che non sono crescenti
a
alessio.palma (1480 points)
9 36 56
by (1.5k points)
edited by
puoi farmi un esempio con una parola corta? per capire come funziona l'algoritmo, grazie mille! l'ho implementato, funziona per il primo test (parola 'fondamenti') ma per gli altri due ci mette troppo tempo e non riesco a vederne il risultato
_andrea_ (45670 points)
11 42 297
by (45.7k points)
parola="ciao"
Per ogni lettera, la togli e crei una sottoparola
"iao" "cao" "cio" "cia". Le metti tutte nell'insieme
{"iao","cao","cio","cia"}. Per ogni sottoparola chiami la ricorsione, aggiungendo il risultato all'insieme. Otterrai quindi
sottoparole("iao") che dentro ti trova {"ao", "io", "ia"}, e chiama la ricorsiome su queste 3. Lo stesso per sottoparole("cao") eccetera. Alla fine ottieni tutte le sottoparole, e levi quelle non crescenti
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Strano. A me ci metteva poco per zanzara ma tanto per le altre. Comunque se aggiungi il controllo che la sottoparola non stia nell'insieme dovrebbe funzionare. Oppure fai che le aggiungi all'insieme solo se sono già crescenti, però la ricorsione la devi chiamare comunque su tutte
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Il mio ci mette un secondo per la parola più lunga
andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
Mi sa che l'abbiamo fatto nell'ultima lezione

guarda su twiki
a
alessio.palma (1480 points)
9 36 56
by (1.5k points)
ora controllo, grazie prof
a
alessio.palma (1480 points)
9 36 56
by (1.5k points)
edited by
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)
11 42 297
by (45.7k 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)
9 36 56
by (1.5k 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)
11 42 297
by (45.7k 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)
9 36 56
by (1.5k points)
perfetto grazie