Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Lunedì quiz - serie 2012 #1

Dato un albero binario (vedasi esempio figura)

image

si implementi la funzione:

TrovaAntenatoComune(node root, node first, node second)

che restituisce l’antenato comune più “vicino” ai due nodi o sollevi un’eccezione se uno dei due nodi non è raggiungibile dalla radice.

Esempio:

TrovaAntenatoComune(A, D, I) = B
TrovaAntenatoComune(A, P, F) = E

-quack

Potrebbero interessarti anche:
Commenti (18):
1. Simo
martedì 7 febbraio 2012 alle 5:00 PM - safari 534.52.7 OS X 10.7.2
   

La cosa più ovvia ma che ovviamente mi pare poco efficiente è quella di scendere l'albero con una funzione ricorsiva che cerchi il padre dei nodi passati come parametro e che se è lo stesso ritorni il tutto fino a risalire lo stack di chiamate... Vediamo un po'!

   
2. AlPa
mercoledì 8 febbraio 2012 alle 1:37 PM - IE 9.0 Windows 7
   

Credo che questo funzioni, ma non ho fatto test

si definisce la classe "Trovato" con due campi booleani "primo" "secondo" booleani e un campo "nodo" si definisce la funzione "InRamo" nel modo seguente:

bool InRamo(node root, node cercato){
  if(root==null){return False;}
  return (root==cercato) || InRamo(root.destro,cercato) || InRamo(root.sinistro,cercato); }

si definisce la funzione "Trova" (che restituisce un oggetto "Trovato") nel modo seguente:

Trovato Trova(node root,node first,node second){
  if(root==null){return new Trovato(false,false,null);}
  if(root==first){
    if(InRamo(nodo,second)){return new Trovato(true,true,root);}
    else {return new Trovato(true,false,null);}
  }
  if(root==second){
    if(InRamo(nodo,first)){return new Trovato(true,true,root);}
    else {return new Trovato(false,true,null);}
  }
  Trovato antenato=Trova(root.destro,first,second);
  if(antenato.primo) {
    if(antenato.secondo){return antenato;}
    if(InRamo(root.sinistro,second){return new Trovato(true,true,root);}
    else{return antenato;}
  }
  else if (antenato.secondo){
    if(InRamo(root.sinistro,first){return new Trovato(true,true,root);}
    else{return antenato;}
  }
  else {return Trova(root.sinistro,first,second;}
}

ovviamente è

TrovaAntenatoComune(node root,node first,node second){ Trova(root,first,second).nodo; }

Alcune casi particolari che dovrebbero essere gestiti (da mettere nei test):

  • può essere root==destro==sinistro: restituisco root
  • può essere root==destro con sinistro in uno dei discendenti; restituisco root

Se è richiesta una buona efficienza, non dovrebbe essere difficile trasformarlo in una procedura iterattiva

   
3. Paperino
mercoledì 8 febbraio 2012 alle 5:57 PM - chrome 16.0.912.77 Windows 7
   

Buone soluzioni, ma si può fare di meglio, sempre ricorsivamente....

   
4. zakk
giovedì 9 febbraio 2012 alle 1:09 AM - safari 534.52.7 OS X 10.6.8
   
Non credo sia la soluzione più efficiente, alcune parti dell'albero vengo scansionate due volte, a occhio.

bool inChildren(node a,node b){ node left,right; left=getLeftChildren(a); right=getRightChildren(b);  if((!left)&&(!right)) //il node che stiamo analizzando non ha figli return false;  if((left==b)||(right==b)) return true;  return inChildren(left,b)||inChildren(right,b);}
node TrovaAntenatoComune(node root, node first, node second){ for(node currentNode=first;(currentNode!=root)&&(currentNode!=error);currentNode=GetParent(currentNode)) if(inChildren(currentNode,second)) return currentNode;

if(currenNode==error)
return ErrorFirstNodeUnreachableFromRoot;  if(inChildren(root,second)) return root; return ErrorSecondNodeUnreachableFromRoot;}
 
   
5. zakk
giovedì 9 febbraio 2012 alle 1:10 AM - safari 534.52.7 OS X 10.6.8
   

Oooops, se n'è andata la formattazione

   
6. Paperino
giovedì 9 febbraio 2012 alle 2:40 AM - chrome 16.0.912.77 Windows 8
   

Ho dimenticato di suggerire di pubblicare le soluzioni su pastebin

   
7. Beppe
giovedì 9 febbraio 2012 alle 1:36 PM - IE 9.0 Windows 7
   

Va bene questa come soluzione?

http://pastebin.com/R7txJUfq

   
8. Beppe
giovedì 9 febbraio 2012 alle 1:40 PM - IE 9.0 Windows 7
   

Ops, non solleva l'eccezione se uno dei due nodi non è raggiungibile, anzi da un risultato errato!

   
9. crossbower
giovedì 9 febbraio 2012 alle 4:43 PM - Opera 11.51 Linux
   

Salve a tutti,

sono un "unixiano" convinto, ma leggo con piacere questo blog. Solitamente non partecipo a questi test, ma ho voluto provare oggi.

Non avevo c# sotto mano, e quindi ho usato common lisp, che al momento sto studiando. So che non rispetto le regole ma é just for fun...

http://pastebin.com/eAaUabCn

Saluti!

   
10. il nonno
giovedì 9 febbraio 2012 alle 5:11 PM - IE 9.0 Windows 7
   

beh adesso qualcuno deve replicare con la soluzione in F#!!!

   
11. crossbower
giovedì 9 febbraio 2012 alle 5:51 PM - Opera 11.51 Linux
   

Hehe, sarei interessato se qualcuno lo facesse, cosi' vedrei se f# mi piace

   
12. Paperino
giovedì 9 febbraio 2012 alle 6:26 PM - chrome 16.0.912.77 Windows 8
   

So che non rispetto le regole ma é just for fun...

La regola numero 0 di lunedì quiz è che non ci sono regole. Certo il mio LISP è arruginito ma la soluzione - se non sbaglio - ricade nell'algoritmo generale di "genero la lista di antenati di entrambi i nodi e poi le scorro".

Si può fare di meglio, la soluzione a breve.

   
13. Paperino
giovedì 9 febbraio 2012 alle 6:27 PM - chrome 16.0.912.77 Windows 8
   

@crossbower: occhio che qui di unixiani convinti c'è bisogno come il pane, eh!

   
14. crossbower
giovedì 9 febbraio 2012 alle 7:16 PM - Opera 11.51 Linux
   

Grazie.

Si, in sostanza l'algoritmo che ho usato genera la lista di antenati e prende l'antenato in comune piu' vicino.

Sono curioso di vedere la soluzione

   
15. Paperino
giovedì 9 febbraio 2012 alle 7:20 PM - chrome 16.0.912.77 Windows 8
   

La mia soluzione: http://pastebin.com/N61MTZ09

Non sono riuscito a definire una funzione in F# che prenda Node come parametri e restituisca un Node. Preferisco darmi all'ippica.

   
16. crossbower
giovedì 9 febbraio 2012 alle 7:37 PM - Opera 11.51 Linux
   

Appena letta la soluzione

Carino il trucco

 if ((comp1 * comp2) < 0) ...

 if (comp1 > 0) ...

else

Mi ricorda qualche teorema di analisi matematica Se non ti dispiace prendero' spunto.

Non avevo considerato l'albero come "ordinato" nel mio algoritmo,  comunque non penso avrei fatto di meglio

Vedremo il prossibo lunedi' (magari provo a mettere su mono, per scrivere un programmino compatibile a livello di sorgente)... 

   
17. Paperino
giovedì 9 febbraio 2012 alle 11:30 PM - chrome 16.0.912.77 Windows 8
   

 Se non ti dispiace prendero' spunto.

interesting, per cosa?

   
18. crossbower
giovedì 9 febbraio 2012 alle 11:45 PM - Opera 11.51 Linux
   

Semplicemente mi piaceva come hai controllato se i due nodi fossero su rami diversi:

 (comp1 * comp2) < 0 

Si, lo so, e' un piccolo frammento di codice, ma e' simpatico da applicare agli alberi binari.

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)