Discussione HW7 e ricorsione

g
giac (2790 points)
7 14 27
asked Dec 6, 2021 in HW7 opzionale by giac (2,790 points)
Salve, volevo proporre un po di discussione condivisa sull'HW7 opzionale per aiutare chi, come me, è completamente in alto mare. Non certo soluzioni, ma qualche aiuto, consiglio, suggerimento, spiegazione, qualsiasi cosa possa illuminare un po il ragionamento sull'hw in particolare e sulla ricorsione in generale.

Insomma, pietà per me che scrivo e disegno cose fantasiose da un paio di giorni.
208 views

3 Answers

Ivanettoss (6040 points)
1 2 11
answered Dec 6, 2021 by Ivanettoss (6,040 points)
Ciao, ti direi di smanettare un pochino sulla lezione di oggi degli alberi da gioco che sono molto utili, può aiutarti ad intuire una soluzione ricorsiva, inoltre utilizza rtrace per visualizzare tutte le chiamate ricorsive in una modalità chiara e molto esplicativa
Exyss (21390 points)
1 2 79
answered Dec 6, 2021 by Exyss (21,390 points)
Innanzitutto devi identificare il caso base del problema, ossia la soluzione minima possibile dove non è necessario svolgere altre operazioni, che in questo caso sarebbe una sequenza in cui non ci sono doppioni, quindi tipo 1-2-3.

Una volta trovato il caso base, bisogna implementare un if che vada a controllare se l'attuale sequenza passata nella funzione siab un caso base o no. Se lo è, allora il risultato viene ritornato, altrimenti dovrai andare ad identificare qualsiasi coppia di doppioni. Una volta trovati tutti i doppioni dovrai richiamare ricorsivamente la funzione su tutte le sequenze ottenibili eliminando i doppioni stessi (attenzione che ad esempio una sequenza con 0-1-0-2-0 ha tre possibili sequenze ottenibili una volta eliminati i doppioni, ossia 1-2-0, 0-1-2, 1-0-2),

Ricorda che ogni caso base corrisponde ad una foglia dell'albero e che il programma prevede l'uso del Set, dunque ti consiglio di cercare bene la differenza tra set e lista (ovviamente sempre se non la conoscessi già) per capire come possa essere implementata la gestione delle foglie all'interno dei nodi padre.

Se ancora ti sfugge come funziona la ricorsione ti consiglio di riguardare le prime due lezioni sulla ricorsione fatte dal prof (inclusa la lezione dove viene usato il modulo Turtle, ottimo per capire graficamente come viene sfruttata la ricorsione).

Una volta trovato l'alogoritmo dovrai ottimizzarlo al massimo per passare gli ultimi 4 test, dunque ti do due suggerimenti: memoization/cache (trovi la spiegazione sempre nelle lezioni del prof) e la soluzione proposta già su q2a nella pagina originale dell'HW7
S
S3b4stian82 (2250 points)
3 6 27
answered Dec 6, 2021 by S3b4stian82 (2,250 points)
Buonasera, io quando ho iniziato l'HW ero un pò a diguno di ricorsione, la prima cosa che ho fatto è stata quella di cercare di ottenere un algoritmo iterativo che mi permettesse di passare dalla sequenza di esempio, alle sequenze intermedie presenti nel PDF di esempio.

Una volta ottenuto ciò non ho fatto nient'altro che inserire il codice in una funzione che richiama se stessa nello stesso punto in cui avevo il print di debug.

Il caso da verificare per interrompere la ricorsione è stato quello di avere una sequenza senza doppioni, qualcuno ha parlato di liste e set, io faccio il cast della lista passata come argomento alla funzione a set e se set e lista hanno lo stesso numero di elementi allora la ricorsione può cessare.