LINGUAGGIO C - funzione che ricerca max nodo dell'albero

[Shanik]

devo fare una funzione che cerca il massimo di tutti i nodi (il contenuto dei nodi) in un albero binario NON ORDINATO..
l'ho fatta ricorsiva..
non funziona.. dice sempre che il max è in testa!!
è sicuramente un errore concettuale...
chi mi aiuta...???
questa è la funzione scritta da me..


Tnode* ricerca_max_punteggio(Ttree tree){

Tnode* max=tree;
if ((tree->left==NULL)&&(tree->right==NULL))
return max;
else
{
ricerca_max_punteggio(tree->left);
if (tree->contest.vincitore.punteggio>max->contest.vincitore.punteggio)
{
max=tree;
return max;
}
else return max;
ricerca_max_punteggio(tree->right);



}

[Travis Landon Barker]

il tree passato all'inizio suppongo sia il puntatore al primo elemento dell'albero, vero?

[Travis Landon Barker]

Ma scusa eh, premetto che gli alberi non li ho studiati, ma ho una vaga idea di come funzionino, ma quando fai:

devo fare una funzione che cerca il massimo di tutti i nodi (il contenuto dei nodi) in un albero binario NON ORDINATO..
l'ho fatta ricorsiva..
non funziona.. dice sempre che il max è in testa!!
è sicuramente un errore concettuale...
chi mi aiuta...???
questa è la funzione scritta da me..


Tnode* ricerca_max_punteggio(Ttree tree){

Tnode* max=tree;
if ((tree->left==NULL)&&(tree->right==NULL))
return max;
else
{
ricerca_max_punteggio(tree->left);
if (tree->contest.vincitore.punteggio>max->contest.vincitore.punteggio)
{

il ricerca_max_punteggio(tree->left); ti ritorna il massimo, non dovresti copiarlo in una variabile?

[Barattolo]

allora...


1) indeeeentaaaaaaaahhh il codiceeeeeeee!!!! (usa pastebin o simile, alla peggio)
2) non fare fanta-tipi ... se Ttree e' sempre un Tnode*, usa solo il Tnode*!! altrimenti alla seconda riga manca il cast
3) la riga numero 3 e' rischiosa perche' potresti avere solo uno dei due a null
4) io sconsiglio l'else se gia' hai messo il return, evita indentature facilmente evitabili che rendono il codice poco leggibile
5) la funzione torna un valore, ma non lo usi mai! dovresti fare "pippo = ricerca_max_punteggio(tree->left);"
6) "max=tree; return max;" anche qui puoi condensare tutto in "return tree;" e basta
7) il secondo "ricerca_max_punteggio(tree->right);" non viene mai chiamato perche' entrambi i branch dell'if precedente finiscono con un return

intanto rifletti su questo mentre penso a come correggerla

[Barattolo]

Dunque...

praticamente tu stai facendo una ricerca su un albero di una cosa che non sai dove stia, che, in parole povere, vuol dire: devi rovistare tutto l'albero!

dal basso del mio perverso amore per il codice ricorsivo, ho imparato che una funzione ricorsiva e' fatta almeno di questi pezzi: uno che controlla se mi devo fermare, uno che mette da qualche parte il risultato della ricerca, e uno che prosegue la ricerca.
Insomma, piu' facile a farsi che dirsi ma avere una vaga idea di quello che stai per andare a fare non fa male, specialmente col codice ricorsivo visto che stai usando una cosa che ancora devi scrivere, non e' che puoi partire dal fondo del programma e poi arrivare verso l'inizio o viceversa, insomma vabbè.

Codice: Seleziona tutto

/**
 *   Per chiarirsi le idee:
 *    Questa funzione cerca da "root" in giù, e ritorna il Tnode* che
 *    ha punteggio massimo (ma solo da root in giù appunto).
 *    In questo modo, chiamandola con la radice dell'albero alla fine
 *    avro' il Tnode* con il punteggio massimo.
 */
Tnode* ricerca_max_punteggio(Tnode* root) {

   /* Alloca due posticini per i valori che dovremo confrontare.
    * Inizializzarli al valore minimo per un intero e' una cosa
    * apprezzabile, ma non ricordo come si chiama la costante...
    */
   int valore1 = 0, valore2 = 0;
   /* Altri due spazietti per i pointer */
   Tnode* tmp1, tmp2;

   /* Questa e' un sanity check che ho messo praticamente solo
    * per farti notare che se avessi messo un else poi avrei
    * dovuto indentare tutto il resto :P
    */
   if(root == NULL) {
      return NULL;
   }

   /* Questa e' la parte che prosegue la ricerca solo se non sono
    * arrivato al fondo. Incidentalmente comprende anche il
    * controllo se mi devo fermare.
    */
   if(root->left != NULL) {
      tmp1 = ricerca_max_punteggio(root->left);
      valore1 = tmp1->contest.vincitore.punteggio;
   }
   if(root->right != NULL) {
      tmp2 = ricerca_max_punteggio(root->right);
      valore2 = tmp2->contest.vincitore.punteggio;
   }

   /*   E qui smanazzo i dati che ho trovato: */
   if(valore1 >= valore2) {
      return tmp1;
   } else {
      return tmp2;      
   }
}


vedi se ti sconquifera...

[Marco Aquila]

Ragazzi non ho la più pallida di quali informazioni vi stiate scambiando ma ho paura

[Travis Landon Barker]

5) la funzione torna un valore, ma non lo usi mai! dovresti fare "pippo = ricerca_max_punteggio(tree->left);"

Infatti mi sembrava così! e inoltre, in fondo


if (tree->contest.vincitore.punteggio>max->contest.vincitore.punteggio)
{
max=tree;
return max;
}
else return max;
ricerca_max_punteggio(tree->right);
}

non viene mai neanche chiamato visto che la funzione ritorna valore max nell'if-else precedente

[Travis Landon Barker]

:o Ragazzi non ho la più pallida di quali informazioni vi stiate scambiando ma ho paura

In realtà è un codice per conquistare il mondo!

PS: scusate il doppio post

[Mattiadrummer]

:o Ragazzi non ho la più pallida di quali informazioni vi stiate scambiando ma ho paura

...mi sento una capra ...

[Barattolo]

Peraltro, ho fatto una stupidata... i puntatori vanno naturalmente dichiarati così:

Tnode *tmp1, *tmp2;

con due *



comunque, Marco e Matttia, un po' vi invidio il non aver mai visto il C...

[Mattiadrummer]

...beh cavolo..quante cose ci sarebbero da sapere...io ne so proprio poche ...

[mickytaylor]

scusate l'OT ma cn il c è possibile creare un numero random come in java???

[Barattolo]

@Mattiadrummer:
Io programmo computer da 16 anni, alla fine e' diventato il mio lavoro. In effetti si, mi sento un po' Neo di Matrix alle volte, ma ho visto personaggi anche peggiori. In compenso non so fare un one handed roll piu' seriamente, il C ha un aspetto orrendo, ci sono un po' di concetti complicati (tipo i puntatori maledetti) che continuano a dare cazzi a programmatori di tutti i livelli, ma alla fine il suo fondamento e' che deve tutto funzionare in modo logico e meccanico, voglio dire, se scrivi "print" ti stampa una scritta, se scrivi "pippo = 3" e poi "print pippo" ti stampera' 3, e cosi' via

@mickytaylor
Certo che si, mi pare che le funzioni in questione siano la srand() e rand(), la prima inizializza il generatore di numeri casuali e il secondo ne genera uno. La prima prende un parametro (il "seed"), ti conviene passargli l'ora, o i nanosecondi dell'ora attuale, o una roba del genere; se gli passi un numero costante ti generera' sempre la stessa sequenza di numeri. Comunque google e' amico

[Travis Landon Barker]

scusate l'OT ma cn il c è possibile creare un numero random come in java???

Assolutamente sì.. Però per la funzione credo dipenda dal compilatore che usi..
Mi ricordo che quando usato il borland quello con la schermata blu-shocking usavo la funzione randomize(); ma mi pare che ad esempio compilando con gcc non funzionasse. Non sono sicuro però..

Cmq, come dice Barattolo, Google è amico

[Shanik]

ciao a tutti... grazie per le risposte... chiedo scusa ma ho avuto problemi di connessione e non sono riuscito a leggere in tempo... cmq avevo risolto da solo facendo così....

Tnode* ricerca_max_punteggio(Tnode* node) {

// Base: il nodo è una foglia.

if ((node->left == NULL) && (node->right == NULL))
return node;

// Induzione: controllo se ci sono nodi con punteggio maggiore di "node".

Tnode* max = node;

if (node->left != NULL) {

// Cerco il nodo con il punteggio maggiore nel sottoalbero sinistro.

Tnode* left = ricerca_max_punteggio(node->left);

if (left->contest.vincitore.punteggio > max->contest.vincitore.punteggio)
max = left;

}

if (node->right != NULL) {

// Cerco il nodo con il punteggio maggiore nel sottoalbero destro.

Tnode* right = ricerca_max_punteggio(node->right);

if (right->contest.vincitore.punteggio > max->contest.vincitore.punteggio)
max = right;

}

return max;

}

[Shanik]

@barottolo.. hai avuto ragione in tutto per l'indentatura giuro che l'ho fatta... solo il forum mi porta tutto a sinistra... non so perchè...

[kom]

minchiamminchia io ho appena cominciato con i puntatori!
taylor per il numero casuale:
srand() imposta il seme,se come parametro usi time(NULL) usa non so quale parte dell'ora corrente. devi usare #include "time.h".
rand() genera il numero casuale compreso tra 0 e RAND_MAX,costante che puoi definire all'inizio se non vado errando,di default è un numero di merda che non ricordo. srand() va chiamata prima di rand().

[Marco Aquila]

:o Ragazzi non ho la più pallida di quali informazioni vi stiate scambiando ma ho paura

...mi sento una capra ...

Siamo al pascolo insieme.

[talismano]

ehehe io invece vi giuro che ho avuto una nostalgia assurda rileggendo questo topic...
ormai di "programmazione" nuda e cruda non fare poco o niente....

che bella che è la programmazione...

[Fippo1992]

Bah, io che ho comniciato stamani con gli algoritmi ricorsivi non c'ho capito nulla
Comunque, in c++, per i numeri casuali:

int NumeroCasuale() //Genera un numero casuale da 1 a 10
{
int a;
srand((unsigned)time(NULL));
return a=rand()%9+1;
}

Perdonate l'indentazione, ma non me la fa...

Edit: @kom: sei sicuro che ci voglia la libreria time.h? a me funziona anche senza la libreria... e nel file in cui ho inserito srand() e rand() ho solo le librerie iostream e winbgim.h...

[John Doe]

Ragazzi ma che errori state commettendo!!

Lo scappellamento è a destra..non a sinistra!!

[kom]

mmm non conosco quelle che hai incluso tu,probabilmente una delle due comprende anche time.h

[Barattolo]

rand() genera il numero casuale compreso tra 0 e RAND_MAX,costante che puoi definire all'inizio se non vado errando

non penso proprio, a meno che non la un-definisci ... e comunque credo che valga 2^15-1, ovvero 32767, che in certi compilatori e' anche il valore massimo che puo' assumere un int

@Fippo1992:
usando quella funzione ti giochi la riproducibilita' della sequenza casuale, non ti conviene fare srand() prima di ogni rand().
riguardo le funzioni ricorsive, beh, si, sono una brutta faccenda, tanto piu' che non si usano quasi mai ... pero' sono istruttive, e poi per me hanno un non so che di affascinante

[francesco-]

avete provato con il cinese? forse e` piu facile...

[Fippo1992]

@barattolo: so che il mio codice non era fatto granchè bene, era solo per spiegare come funzionava in un contesto... semi-serio.
Comunque mi ci sono emsso un po' oggi pomeriggio e ci sto capendo qualcosa... sono mooolto carine... per esercizio dovrei scrivere la successione di fibonacci con la ricorsione... ma a malapena scrivo la media aritmetica XD