<html>
<head>
<meta name="generator" content="Windows Mail 17.5.9600.20315">
<style><!--
.EmailQuote {
margin-left:1pt;
padding-left:4pt;
border-left:#800000 2px solid;
}
--></style><style data-externalstyle="true"><!--
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph {
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
}
p.MsoNormal, li.MsoNormal, div.MsoNormal {
margin:0in;
margin-bottom:.0001pt;
}
p.MsoListParagraphCxSpFirst, li.MsoListParagraphCxSpFirst, div.MsoListParagraphCxSpFirst,
p.MsoListParagraphCxSpMiddle, li.MsoListParagraphCxSpMiddle, div.MsoListParagraphCxSpMiddle,
p.MsoListParagraphCxSpLast, li.MsoListParagraphCxSpLast, div.MsoListParagraphCxSpLast {
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
line-height:115%;
}
--></style></head>
<body dir="ltr">
<div data-externalstyle="false" dir="ltr" style="font-family: 'Calibri', 'Segoe UI', 'Meiryo', 'Microsoft YaHei UI', 'Microsoft JhengHei UI', 'Malgun Gothic', 'sans-serif';font-size:12pt;"><div> é chiaro come funziona, ora provo a implementarlo poi vi faccio sapere</div><div><br></div><div>Grazie mille</div><div><br></div><div style="padding-top: 5px; border-top-color: rgb(229, 229, 229); border-top-width: 1px; border-top-style: solid;"><div><font face=" 'Calibri', 'Segoe UI', 'Meiryo', 'Microsoft YaHei UI', 'Microsoft JhengHei UI', 'Malgun Gothic', 'sans-serif'" style='line-height: 15pt; letter-spacing: 0.02em; font-family: "Calibri", "Segoe UI", "Meiryo", "Microsoft YaHei UI", "Microsoft JhengHei UI", "Malgun Gothic", "sans-serif"; font-size: 12pt;'><b>Da:</b> <a href="mailto:piro@develer.com" target="_parent">Daniele Varrazzo</a><br><b>Data invio:</b> venerdì 6 dicembre 2013 23:19<br><b>A:</b> <a href="mailto:python@lists.python.it" target="_parent">Mailing List Python</a></font></div></div><div><br></div><div dir="">
<div class="PlainText">On 2013-12-06 17:35, De Santis Luca wrote:<br>
<br>
Ciao Luca,<br>
<br>
> Vi ammorbo ancora con gli alberi. Devo fare una funzione per trovare<br>
> il path di una qualsiasi foglia di un albero.<br>
><br>
><br>
> Per fare ciò ho pensato di inserire nella classe che definisce<br>
> l’albero un campo nodoGenitore, così, facendo la ricerca di un nodo<br>
> per nome, quando trovo il nodo che mi interessa, vedo chi è il nodo<br>
> padre e vado a ritroso fino alla radice e trovo il path completo <br>
> della<br>
> foglia.<br>
<br>
Questo di solito non è necessario negli algoritmi ricorsivi. Tra <br>
l'altro in Python hai anche un problema: se hai due oggetti che si <br>
riferiscono l'uno all'altro tipo (a.figli contiene b e b.genitore punta <br>
ad a) hai un ciclo di riferimenti. Poiché Python distrugge gli oggetti <br>
quando il refcount scende a zero questi due oggetti si tengono in vita <br>
l'uno con l'altro e potresti avere un memory leak. Questo è molto <br>
semplificato: il GC di Python è abbastanza intelligente di accorgersi di <br>
molti casi in cui un ciclo di oggetti non ha riferimenti esterni e alla <br>
fine riesce a reclamarlo, ma non sempre e così (quando non sia possibile <br>
è un po' complesso, ma ben documentato). Per farla corta, meno cicli hai <br>
nel codice, meglio è (e sempre a volerla dire tutta weakref è un modo <br>
fatto apposta per avere cicli "rompibili", ma anche di questo non ne hai <br>
bisogno per ora: la butto là in caso ti vada di approfondire).<br>
<br>
Tornando a bomba: secondo me il puntatore del genitore non ti serve: il <br>
tornare a ritroso te lo dà lo srotolamento dello stack quando la <br>
soluzione viene trovata: io farei una funzione che interroga i figli e, <br>
se uno di loro è positivo, aggiunge sé stesso al valore di ritorno (se <br>
uno dei miei figli è la soluzione, anche io sono la soluzione!)<br>
<br>
Quando un nodo è la soluzione? quando w == nomeNodo. Non ti serve <br>
chiederlo ai figli, giusto? Penso ti sia infilato in un vicolo cieco <br>
mentale facendo:<br>
<br>
> def _path(self,root,w):<br>
> for node in root.sottoNodi:<br>
> if(node.nomeNodo==w):<br>
<br>
non serve chiederlo ai figli, e hai anche il problema che se root è la <br>
soluzione, non la troverai, giusto?<br>
<br>
Questa funzione deve restituire una lista di nodi: direi che se c'è una <br>
soluzione sarebbe una lista che ha prima la radice, poi il suo figlio <br>
che porta alla soluzione... fino alla soluzione. Essendo l'algoritmo <br>
ricorsivo, puoi scriverlo in maniera che, gira gira, troverai un albero <br>
la cui radice è la soluzione (che poi sia la radice complessiva o solo <br>
un sotto-sotto-nodo non serve saperlo a lui: serve saperlo al <br>
chiamante). Quindi qualcosa come:<br>
<br>
def path(self, w):<br>
# sono io la soluzione?<br>
# sì: fico: restituisci una lista che contiene solo me stesso<br>
# no? peccato, ma:<br>
# per ognuno dei miei figli<br>
# dammi il path per w<br>
# è una lista? fico allora<br>
# aggiungo me stesso all'inizio della lista<br>
# e restituisco la lista a chi mi ha chiamato<br>
<br>
questo l'ho scritto in pseudocodice, ma l'ho implementato anche in <br>
python. Ti dò una possibilità di farlo da te se vuoi: letteralmente ogni <br>
riga che ho scritto si trasforma in un'instruzione Python, ma così credo <br>
sia ancora più chiaro l'algoritmo. Se vuoi la soluzione completa te la <br>
passo (o te la passa qualcun altro).<br>
<br>
Nota che se la parola non viene trovata in nessuno dei figli il flusso <br>
di esecuzione esce alla fine della funzione senza incontrare un return. <br>
Questo equivale a "return None", ed è il risultato alternativo di "è una <br>
lista? fico". In pratica nodo.path(w) restituisce una lista se la <br>
soluzione viene trovata, altrimenti None.<br>
<br>
In bocca al lupo!<br>
<br>
<br>
-- Daniele<br>
<br>
_______________________________________________<br>
Python mailing list<br>
Python@lists.python.it<br>
<a href="http://lists.python.it/mailman/listinfo/python" target="_parent">http://lists.python.it/mailman/listinfo/python</a><br>
</div>
</div></div>
</body>
</html>