TIMEOUT ES 1 HW 4 E ALTEZZA

Question

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?

Answer 1

Forse non consideri la radice quindi ti viene più corto

Comments

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.

---

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?

---

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).

---

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

---

Quindi per ogni ricorsione ci sono due altezze distinte (una complessiva e una parziale) ?

---

Per ogni ricorsione trovi l'altezza massima tra le altezze dei figli