HW4BIS esercizio 2 sono bloccato

DRDLCN (8070 points)
3 67 104
asked Mar 13, 2019 in HW4bis by DRDLCN (8,070 points)
recategorized Mar 13, 2019 by andrea.sterbini

leggendo su q2a ho visto che una strada per risolvere l'es è creare liste di questo genere...['  80  ',' _|_  ','|   | ','70  90']

ma non ho ben capito come, come le metto le foglie dello stesso padre sullo stesso elemento della lista?

io avevo pensato a mettere tutto quello che ha uguale lunghezza dalla radice in un unico elemento ma non so se posso aggiungere metodi nel file albero.py 

486 views

1 Answer

_andrea_ (45670 points)
2 40 297
answered Mar 13, 2019 by _andrea_ (45,670 points)
Le metti dando per scontato che la ricorsione tu ritorni l'albero giusto, e unendoli insieme. Per capire come, usa alberi di prova prima con un solo figlio, poi due figli foglie, poi due figli che hanno uno o due figli ciascuno. Quando hai capito i casi facili, la ricorsione fa il resto
DRDLCN (8070 points)
3 67 104
commented Mar 13, 2019 by DRDLCN (8,070 points)
quindi se il nodo non ha figli, quindi è una foglia viene aggiunta ad una stringa, poi trova un altra foglia dello stesso nodo ( la ricorsione funziona cosi no? ) e va aggiunto alla stessa stringa, aggiungo la stringa alla lista, resetto la stringa e la ricorsione dovrebbe passare ad altri nodi no?
_andrea_ (45670 points)
2 40 297
commented Mar 13, 2019 by _andrea_ (45,670 points)
se è una foglia ritorni la stringa che corrisponde a quella foglia (o la lista di stringhe, dipende da come ti trovi meglio tu a lavorarci. io ho fatto lista di stringhe), se invece è un nodo con figli, generi prima le stringhe di quei figli, con la ricorsione, e se hai fatto tutto bene puoi dare per scontato che siano corretti, quindi puoi unirli tra loro come dice nel testo
DRDLCN (8070 points)
3 67 104
commented Mar 13, 2019 by DRDLCN (8,070 points)
io non riesco a capire come se trovo una foglia ritorno la lista delle foglie di quel padre , uso due liste diverse tra i padri e le foglie? e poi le unisco?
_andrea_ (45670 points)
2 40 297
commented Mar 13, 2019 by _andrea_ (45,670 points)
prima di programmare fatti una specie di schema mentale per capire come strutturare la funzione ricorsiva. nel particolare cosa vuoi che ritorni. questo perché essendo ricorsiva significa che tutte le chiamate tornano lo stesso tipo di dato quindi dei lavorare con quello. se decidi di lavorare con stringhe o liste di stringhe è uguale, basta che ti adegui. perché quando lanci la ricorsione su un figlio, quello ti ritorna una risultato su cui devi lavorare, e a tua volta tornare un risultato di quel tipo per poterci lavorare ad eventuali livelli superiori. dopo aver deciso come rappresentare un albero inizia a pensare proprio a come si costruisce, a partire dai figli e poi unendoli a creare l'albero attuale, che poi ritornerai per lavorarci a livelli superiori. io ti consiglio di usare una lista di stringhe dove ogni stringa è una riga completa di spazi, e le righe sono teoricamente separate da \n, che però non metti in quanto sono elementi diversi
E
Emanuelebev (720 points)
1 17 24
commented Mar 20, 2019 by Emanuelebev (720 points)
ad esempio, posso riuscire a risolvere l'esercizio manipolando solamente la lista di partenza?
_andrea_ (45670 points)
2 40 297
commented Mar 20, 2019 by _andrea_ (45,670 points)
In che senso? Quale lista?
E
Emanuelebev (720 points)
1 17 24
commented Mar 20, 2019 by Emanuelebev (720 points)
nel senso se posso crearmi una rappresentazione dell'albero in formato liste di liste.

ad esempio l'albero

        50

        _|_

     20      30

diventa [50, [20],[30]]
_andrea_ (45670 points)
2 40 297
commented Mar 20, 2019 by _andrea_ (45,670 points)
Si ma devi restituire una stringa, meglio se inizi direttamente con le stringhe, tanto dopo in qualche modo devi unirle quelle liste e farle diventare una stringa sola
E
Emanuelebev (720 points)
1 17 24
commented Mar 20, 2019 by Emanuelebev (720 points)
nel senso che deve diventare ['50',['20'],['30']] ?
_andrea_ (45670 points)
2 40 297
commented Mar 20, 2019 by _andrea_ (45,670 points)
No deve diventare una stringa che ora non ho voglia di scrivere ma deve avere i numeri, gli spazi, i collegamenti e gli accapo nel posto giusto, come negli esempi nel testo
E
Emanuelebev (720 points)
1 17 24
commented Mar 20, 2019 by Emanuelebev (720 points)
non posso manipolare questa stringa in modo che risulti giusta?
_andrea_ (45670 points)
2 40 297
commented Mar 20, 2019 by _andrea_ (45,670 points)
Ma tu parti da un albero e devi trovarti la stringa che lo rappresenta. La stringa devi crearla da 0 ma piuttosto che farti una lista di liste di stringhe e poi trasformarle nel risultato fatti direttamente il risultato
D
Deacoon (9100 points)
3 33 53
commented Jul 25, 2019 by Deacoon (9,100 points)

['  80  ',' _|_  ','|   | ','70  90']

come si fa questa lista se i figli sono piu di due?

andrea.sterbini (172780 points)
514 935 1789
commented Jul 26, 2019 by andrea.sterbini (172,780 points)
edited Jul 26, 2019 by andrea.sterbini

Cerca di ragionare come se tu fossi un editor di testo (per esempio Notepad++) e dovessi incollare due alberi uno a fianco all'altro aggiungendo le righe sopra e gli spazi in mezzo:

  • devi fare in modo che i due alberi abbiano la stessa altezza aggiungendo righe fatte di soli spazi in fondo al più corto
  • devi concatenare le righe dei due alberi aggiungendo gli spazi in mezzo
  • devi aggiungere le righe superiori che formano il disegno del nodo padre

E questo va fatto ricorsivamente su tutto l'albero