TIMEOUT ES 1 HW 4 E ALTEZZA

D
Daniele (640 points)
2 14 18
asked Dec 26, 2018 in Es1 by Daniele (640 points)
Effettuando i test dell'es 1 dell'homework 4 mi passa solo i primi 2 test. Tutti i restanti mi segnala un problema relativo all'altezza. Nel mio programma l'altezza parte da 1 e viene incrementata ogni volta trovato un figlio della nodo(poi confronto le varie altezze e scelgo quella massima). Tuttavia ad eccezione dei test 1 e 2 le altezze dei miei risultati sono sempre minori di 1 del risultato effettivo.  Inoltre i test 6 e 7 non superano il timeout. Consigli su quale potrebbe essere il problema e come ottimizzare il programma?
126 views

1 Answer

_andrea_ (45670 points)
2 40 297
answered Dec 26, 2018 by _andrea_ (45,670 points)
Forse non consideri la radice quindi ti viene più corto
D
Daniele (640 points)
2 14 18
commented Dec 26, 2018 by Daniele (640 points)
No, la radice la considero all'inizio, quando inizializzo altezza a 1 e successivamente la incremento. Infatti i primi 2 test li supera.

Inoltre non riesco a trovare un modo per ottimizzare il programma in termini di efficienza.
_andrea_ (45670 points)
2 40 297
commented Dec 26, 2018 by _andrea_ (45,670 points)
Beh intanto pensa a farlo corretto, poi pensa al tempo. Cos'hanno di diverso gli altri test che il primo e il secondo non hanno?
D
Daniele (640 points)
2 14 18
commented Dec 26, 2018 by Daniele (640 points)
Ho capito il problema: in pratica col mio programma calcolo l'altezza di un ramo (cioè dalla radice alla foglia) e lo inserisce nella variabile altezza_massima se altezza>altezza_massima. Il problema è che una volta fatto ciò assegnavo alla variabile altezza il valore 1, perché pensavo che la successiva "biforcazione" era al livello della radice. In realtà non è così, perché le biforcazioni possono esserci, per esempio, anche a metà strada tra radice e foglia. Quindi non so cosa assegnare alla variabile altezza, una volta terminata una strada(ossia una volta arrivato ad una foglia).
_andrea_ (45670 points)
2 40 297
commented Dec 26, 2018 by _andrea_ (45,670 points)
Per trovare l'altezza fai così: se il nodo che stai controllando è una foglia torni 1, altrimenti inizializzi una variabile h = 1 e per ogni figlio controlli se l'altezza di quel figlio è maggiore di h, se lo è h diventa l'altezza di quel figlio. Così per ogni nodo hai il massimo delle altezze dei suoi figli. Alla fine ritorni h+1 perché devi aggiungere il nodo stesso da cui sei partito
D
Daniele (640 points)
2 14 18
commented Dec 27, 2018 by Daniele (640 points)
Quindi per ogni ricorsione ci sono due altezze distinte (una complessiva e una parziale) ?
_andrea_ (45670 points)
2 40 297
commented Dec 27, 2018 by _andrea_ (45,670 points)
Per ogni ricorsione trovi l'altezza massima tra le altezze dei figli