Lunedì quiz - 3

Mi porto un po’ avanti con un quiz molto facile rispetto ai soliti. La difficoltà più grossa è descrivere un tale algoritmo per telefono.

Dato un albero binario di nodi contenenti due valori per ogni nodo (X, Y) e ordinato per X, trovare e stampare tutti i nodi che hanno entrambi i valori più grandi di un nodo di riferimento.

In poche parole, implementare: PrintNodes(node root, node referenceNode)

-quack

(*)ordinato per X: tutti i nodi a sx di un determinato nodo K hanno X <= X(K)

Potrebbero interessarti anche:
Commenti (31): [ Pagina 1 di 2  - più vecchi ]
2. il nonno
domenica 24 ottobre 2010 alle 10:50 PM - chrome 7.0.517.41 Windows 7
   

Si puo' usare un pettine?

   
3. Giuseppe
lunedì 25 ottobre 2010 alle 7:51 AM - IE 9.0 Windows 7
   

struct node {
 int x,y;
 node* left;
 node* right;
};

void PrintNodes(node* root, node referenceNode) {
 if (!root) return;
 else {
  if (root->x > referenceNode.x && root->y >referenceNode.y) {
   cout << "Nodo Trovato; Valori (x,y) = (" << root->x << "," << root->y << ")" << endl;
  }
  PrintNodes(root->left);
  PrintNodes(root->right);
 }

Buona cara vecchia visita anticipata (o posticipata, non ricordo mai quale delle due) modificata accuratamente.

   
4. Frank
lunedì 25 ottobre 2010 alle 12:37 PM - chrome 7.0.517.41 Windows 7
   

 

void PrintNodes(node* root, node referenceNode)

...

if (root->x > referenceNode.x && root->y >referenceNode.y) 

Perché root è passato (giustamente) per puntatore invece referenceNode usando la deep-copy?

 

PrintNodes(root->left);
PrintNodes(root->right);

PrintNodes avrebbe bisogno di un secondo parametro...

 

   
5. wac
lunedì 25 ottobre 2010 alle 2:59 PM - firefox 3.6.10 Windows 7
   

Giuseppe è la visita infissa

struct node {
 int x,y;
 node* left;
 node* right;
};

void PrintNodes(node* root, node* referenceNode) {
 if (!root) return;

PrintNodes(root->left,referenceNode);


  if (root->x > referenceNode.x && root->y >referenceNode.y)

{
   cout << "Nodo Trovato; Valori (x,y) = (" << root->x << "," << root->y << ")" << endl;
}
 
  PrintNodes(root->right, referenceNode);
 }

dovrebbe andare

   
6. wac
lunedì 25 ottobre 2010 alle 3:03 PM - firefox 3.6.10 Windows 7
   

Giuseppe la mia è la infissa, la tua è la prefissa(dannato netbook )

   
7. Giuseppe
lunedì 25 ottobre 2010 alle 5:57 PM - chrome 7.0.517.41 Windows 7
   

@Frank

1) Perché un node in deep-copy occupa 16 byte quindi non me ne può importare di meno di passarlo per riferimento/puntatore... 

2)diretta conseguenza delle 7:51 del mattino in cui ho scritto il codice

Riscrivo i passaggi da te evidenziati aggiustando il codice:

void PrintNodes(node* root, node* referenceNode) { 

[...]

if(root->x>referenceNode->x && root-> y>referenceNode->y

[...]

PrintNodes(root->left,referenceNode);  

PrintNodes(root->right,referenceNode);

 

   
8. paperino
lunedì 25 ottobre 2010 alle 6:33 PM - chrome 533.1 Android 2.2.1
   

Aaargh!! Dettaglino importante l'albero è ordinato per X

   
9. Giuseppe
lunedì 25 ottobre 2010 alle 6:37 PM - IE 9.0 Windows 7
   

in che modo esattamente? Heap? Binario di Ricerca?

 

   
10. Paperino
lunedì 25 ottobre 2010 alle 7:18 PM - chrome 7.0.517.41 Windows 7
   

@Giuseppe: vedi nota nel post.

   
11. Giuseppe
lunedì 25 ottobre 2010 alle 8:19 PM - chrome 7.0.517.41 Windows 7
   

struct node { int x,y; node* left; node* right;};

void PrintNodes(node* root, node* referenceNode) { 

  if (!root) return; 

  if (root->x <= referenceNode->x ) PrintNodes(root->right); 

  else {  

    if (root->y > referenceNode->y) {  

       cout << "Nodo Trovato ..." << endl;  

    }

    PrintNodes(root->left);  

    PrintNodes(root->right); 

  }

}

sono abbastanza in confusione ora... probabilmente non funge...

   
12. Paperino
lunedì 25 ottobre 2010 alle 9:13 PM - chrome 7.0.517.41 Windows 7
   

probabilmente non funge

infatti

   
13. Blackstorm
martedì 26 ottobre 2010 alle 1:42 AM - firefox 3.6.11 Windows 7
   

Uhm... domanda, magari idiota, ma se il nodo è noto, allora non basta prendere K.Y e verificare i valori Y dell'albero destro del nodo K? Voglio dire, io prendo il sottoalbero con radice K->dx, e so che tutti e soli gli X in quell'albero hanno i valori maggiori del nodo di riferimento, radice compresa. A quel punto basta fare una qualsiasi visita completa e confrontare i valori Y del sottoalbero con il valore Y del nodo di riferimento.

   
14. Daniele
martedì 26 ottobre 2010 alle 9:59 AM - firefox 4.0 Windows 7
   

Ecco perchè odiavo gli alberi a ingegneria...

   
15. Giuseppe
martedì 26 ottobre 2010 alle 10:52 AM - Opera 10.54 Windows CE/Mobile/Embedded
   

bozza:
if(root->x > ref->x){
checkY(ref->y);
deepVisit(root->right);
myself(root->left);
}
else{
myself(root->right);
}

assomoglia a qualcsa di lontanamente esatto?

   
16. Paperino
martedì 26 ottobre 2010 alle 6:05 PM - chrome 7.0.517.41 Windows 7
   

Mmmm. Risposta.

   
17. wac
martedì 26 ottobre 2010 alle 7:43 PM - firefox 3.6.11 Windows 7
   

Papero hai inserito più dettagli, non è giusto però, c'ero quasi arrivato per primo

   
18. Nicola
martedì 26 ottobre 2010 alle 10:34 PM - chrome 7.0.517.41 Windows 7
   

Ops Paperino sento puzza di spam!

   
19. Paperino
martedì 26 ottobre 2010 alle 10:57 PM - chrome 7.0.517.41 Windows 7
   

Spammer blacklistato.

   
20. Il Razziatore
martedì 26 ottobre 2010 alle 11:33 PM - chrome 8.0.552.11 Windows 7
   

Papero, lo spammer fa sul serio.

   
21. Paperino
martedì 26 ottobre 2010 alle 11:45 PM - chrome 7.0.517.41 Windows 7
   

Direi proprio: 3 indirizzi IP diversi, uno in Cina, uno in Polonia, uno in USA. Che palle....

   
22. Paperino
mercoledì 27 ottobre 2010 alle 12:08 AM - chrome 7.0.517.41 Windows 7
   

A mali estremi.... ho creato al volo una euristica. Col cappero che la bloccano....

   
23. Il Razziatore
mercoledì 27 ottobre 2010 alle 12:16 AM - chrome 8.0.552.11 Windows 7
   

Questa però direi non sia il caso di inserirla nel prossimo Lunedì Quiz...

   
24. Paperino
mercoledì 27 ottobre 2010 alle 1:58 AM - chrome 7.0.517.41 Windows 7
   

Ne è appena passato un altro. L'euristica ha tenuto.

   
25. 0verture
giovedì 28 ottobre 2010 alle 7:41 PM - firefox 3.6.11 Windows 7
   

Papero, fallo sparire in fretta questo. Sta usando delle keyword abbastanza pericolose.

   
26. Paperino
giovedì 28 ottobre 2010 alle 7:51 PM - chrome 7.0.517.41 Windows 7
   

S'era salvato a causa di un baco. 'tacci sua.

   
27. 0verture
sabato 30 ottobre 2010 alle 11:16 PM - firefox 3.6.12 Windows 7
   

Mittticò è tornato

 

   
28. Paperino
domenica 31 ottobre 2010 alle 6:00 AM - chrome 7.0.517.41 Windows 7
   

Non so però se hai notato che 

1) ha cominciato ad essere più umano e anche spiritoso
2) ha smesso di spammare link

Il mio obiettivo dichiarato è questo. Qualcosa mi dice che sono sulla buona strada.

   
29. 0verture
domenica 31 ottobre 2010 alle 10:44 AM - firefox 3.6.12 Windows 7
   

   
30. Nicola
domenica 31 ottobre 2010 alle 9:37 PM - chrome 5.0.375.99 Linux
   

tutto risolto ora o questi cinesi rompono le scatole ancora?

   
31. Paperino
lunedì 1 novembre 2010 alle 6:16 AM - chrome 7.0.517.41 Windows 7
   

IL cinesE. Era uno solo

   
[ Pagina 1 di 2  - più vecchi ]
I commenti sono disabilitati per questo post. Grazie!