Problema soluzione HW4bis es3

M
MatteoDante (620 points)
0 3 5
asked May 8, 2019 in HW4bis by MatteoDante (620 points)
Buonasera,

Ho un problema con la risoluzione del test es3_tricky.png, non mi spiego il perchè data la traccia dell'esercizio "trovare i due punti più distanti tra di loro" per il test es3_tricky.png mi restituisce la seguente immagine

https://images2.imgbox.com/1f/2a/fAoJABE2_o.png

A destra c'è la mia soluzione mentre a sinistra si può vedere la soluzione del test

Non capisco perchè dati i due punti, la soluzione fa vedere che bisogna passare anche per il tratto della radice e poi quindi tornare indietro. se potessi ritornare indietro allora colorerei tutti i pixel bianchi di blu in quanto quello sarebbe il percorso più lungo per arrivare da un nodo ad un altro (ovvero arrivare a toccare tutti i nodi per poi tornare indietro)

Mi scuso se non sono stato abbastanza chiaro

Vi ringrazio in anticipo
320 views

2 Answers

Best answer
_andrea_ (45670 points)
2 39 297
answered May 8, 2019 by _andrea_ (45,670 points)
selected May 9, 2019 by MatteoDante
devi colorare anche i pixel che portano alla radice perché se tu stessi percorrendo il cammino che da una foglia ti porta ad un'altra, dovresti per forza passare da un padre che hanno in comune. in questo caso le due foglie hanno come padre in comune la radice, quindi ci devono passare anche se nell'immagine esiste quel percorso alternativo
M
MatteoDante (620 points)
0 3 5
commented May 9, 2019 by MatteoDante (620 points)
Vi ringrazio per la risposta.

Mi spiego meglio Andrea, io per calcolarmi il massimo percorso ho assunto che ogni nodo rosso, uno alla volta, diventasse verde, mi calcolo allora per ogni nodo il nodo più lontano, una volta che li ho trovati tutti mi trovo il massimo tra i percorsi più lontani, e questo esce fuori... nel mio schema il verde non è padre anzi è una foglia...
_andrea_ (45670 points)
2 39 297
commented May 9, 2019 by _andrea_ (45,670 points)
È un modo interessante di calcolare il diametro ma non puoi dimenticarti che quello è comunque un albero. Immagina che la radice sia una piazza e i nodi delle piazzette, e che i pixel bianchi siano strade che le collegano. Io ti chiedo: trova il percorso più lungo da una piazzetta ad un'altra piazzetta, però devi passare sempre per la piazza che le collega. In questo caso il nodo in alto a sinistra e quello subito sotto a destra della radice sono i più lontani, ma comunque quello a sinistra è figlio della radice, quindi per arrivare all'altro devi passarci, per poi tornare indietro e cambiare strada, andando verso quel figlio che sto sotto la radice e da lì verso l'altro nodo che è da collegare. Ti stai comunque muovendo in un albero, non un'immagine normale
M
MatteoDante (620 points)
0 3 5
commented May 9, 2019 by MatteoDante (620 points)
Grazie Andrea,

Il mio focus infatti era sul tornare il percorso matematico più lungo dell'immagine e non dell'albero che si va a creare...

Cosa mi suggerisci di fare allora... io ho lavorato con gli oggetti quindi ho la radice con il suo attributo percorso che per la radice è vuoto e con l'attributo figli che è una lista di altre istanze dello stesso oggetto che a loro volta hanno il percorso del padre per arrivare fino a loro, le coordinate e i loro figli. Per calcolarmi il diametro che chiede l'esercizio posso ispirarmi a qualche documentazione o esercizio? Altrimenti sarei bloccato, non mi viene in mente un metodo per trovare il nodo più lontano da un altro nello stesso albero..
_andrea_ (45670 points)
2 39 297
commented May 10, 2019 by _andrea_ (45,670 points)
È come calcolare l'altezza ma devi calcolare le due più grandi e sommarle, e poi confrontarle con quella che già hai. Quello è il diametro
andrea.sterbini (172680 points)
511 927 1776
commented May 10, 2019 by andrea.sterbini (172,680 points)
L'abbiamo fatto a lezione ... molto simile
M
MatteoDante (620 points)
0 3 5
commented May 10, 2019 by MatteoDante (620 points)
Professore intende la lezione 17 "Ricorsione ed Alberi"?

Comunque ho risolto ed ora consegno, grazie a entrambi.
andrea.sterbini (172680 points)
511 927 1776
answered May 8, 2019 by andrea.sterbini (172,680 points)
L'esercizio chiede di contare tutti i punti bianchi se necessario passandoci due volte come in questo caso.
Il percorso più lungo infatti in questo caso passa per la radice per cui bisogna colorare anche quei pixel.
(e se colori di blu tutti i punti bianchi della figura ottieni che il percorso non è più lineare ma un albero che si dirama, quindi non è più "il percorso più lungo che collega due nodi dell'albero")

Spero di essermi spiegato decentemente