<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>Ho risolto in questo modo, non sarà molto “pythonico” ma verifica con il programma di test:</div><div><br></div><span lang="IT"><div> def path(self,w):<br> pathname=self.nomeNodo<br> lst=set()<br> if self.nomeNodo==w: <br> lst.append(tuple(pathname))<br> self._path(self,w,pathname,lst)<br> return lst</div><div><br></div><div> def _path(self,inNodo,w,pathname,lst):<br> ret=pathname<br> for nodo in inNodo.sottoNodi:<br> pathname = ret + "\\"+ nodo.nomeNodo<br> if len(nodo.sottoNodi)>0:<br> self._path(nodo,w,pathname,lst)<br> if nodo.nomeNodo==w: <br> lst.add(tuple(item for item in pathname.split("\\") if item.strip()))</div><p>Prima che vi scandaliziate per il sistema usato, l’esercizio prevedeva che venisse restituito un insieme di tuple, per ogni path tovato dovevo quindi creare una tupla con tutti gli elementi del percorso. Grazie per le dritte che mi avete dato </p></span><br><div data-signatureblock="true"><div><br></div><div>Inviata da Windows Mail</div><div><br></div></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:farolfo@hotmail.com" target="_parent">De Santis Luca</a><br><b>Data invio:</b> domenica 8 dicembre 2013 20:42<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="ltr">
<div>Ho provato a seguire il tuo suggerimento, solo ce ho un comportamento strano, cioè che non capisco io, ho implementato la funzione path in questo modo:</div><div><br></div><div> def path(self,w):<br> ret=[]<br> ret.append(self.nomeNodo)<br> self._path(self,w,ret)<br> return ret<br> <br> def _path(self,root, w,lista):<br> print "sono in _path"<br> if root.nomeNodo==w:<br> #print root.nomeNodo<br> lista.append(root.nomeNodo)<br> #return lista<br> else:<br> for nodo in root.sottoNodi:<br> #print root.nomeNodo<br> lst=nodo._path(nodo,w,lista)<br> if lst is list:<br> for i in lst:<br> print "Sono nel for"<br> lista.append(i.nomeNodo)<br> #return lista<br></div><div data-signatureblock="true"><div><br></div><div>La funzione così com’è non mi entra mai nel ciclo for, dove c’è la stampa:</div><div><br></div><div> for i in lst:<br> print "Sono nel for"<br> lista.append(i.nomeNodo)</div><div><br></div><div>e mi restituisce una lista con solo la root e il nodo finale che sto cercando, ce però aggiunge 2 volte. Se invece decommento i return la funzione mi rimane in loop ferma e non mi restituisce mai la lista.</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></div>
</body>
</html>