PDA

Visualizza la versione completa : [C] Problema funzione ricorsiva


paulinho
10-01-2013, 13:07
Non riesco a capire dove sta l'errore.
questa la funzione :
Ricerca il parlamentare di un dato partito che ha ricevuto il maggior numero di voti.
E RICHIESTA UNA IMPLEMENTAZIONE RICORSIVA SULLA BASE DEL DIVIDE ET IMPERA.






TNode* parlamentare_votato(TTree tree, char partito[]){
TTree sx, dx,curr;

if(tree == NULL)
return NULL;

if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
curr = tree;
else{

sx = parlamentare_votato(tree->left, partito);
dx = parlamentare_votato(tree->right, partito);
if((curr->info.satellite.voti >= sx->info.satellite.voti) && (sx->info.satellite.voti >= dx->info.satellite.voti))
return curr;
else if((sx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= dx->info.satellite.voti))
return sx;
else if((dx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= sx->info.satellite.voti))
return dx;
else
return NULL;
}
}

MegaAlchimista
11-01-2013, 11:10
Com' fatto l'albero?

Edit:
Ma scusa


if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
curr = tree;
else{
...
}
//qui non dovrebbe esserci un return *qualcosa* ?

Se entri in quell'if la funzione non torna niente

paulinho
11-01-2013, 16:59
Originariamente inviato da MegaAlchimista
Com' fatto l'albero?

Edit:
Ma scusa


if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
curr = tree;
else{
...
}
//qui non dovrebbe esserci un return *qualcosa* ?

Se entri in quell'if la funzione non torna niente

anche mettendo un return non va... quello un progetto e non so come farvelo vede ..

paulinho
11-01-2013, 17:00
l'albero un bst, ossia un albero binario di ricerca.

MegaAlchimista
11-01-2013, 18:52
Premetto che non so molto di alberi, comunque vediamo un attimo, ci sono delle cose che non mi sono chiare


TNode* parlamentare_votato(TTree tree, char partito[]){
TTree sx, dx,curr;

if(tree == NULL)
return NULL;

if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
curr = tree;
else{
sx = parlamentare_votato(tree->left, partito); //<-qui esci!!!
dx = parlamentare_votato(tree->right, partito);
if((curr->info.satellite.voti >= sx->info.satellite.voti) && (sx->info.satellite.voti >= dx->info.satellite.voti))
return curr;
else if((sx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= dx->info.satellite.voti))
return sx;
else if((dx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= sx->info.satellite.voti))
return dx;
else
return NULL;
}
return curr; //credo che qui ci debba stare questo, oppure potevi direttamente metterlo sotto l'if (meglio, non copi dati inutilmente)
}

se tu percaso entri nell'else vai subito nella parte che ho messo in grassetto, gi alla prima riga richiami questa funzione in modo ricorsivo, quindi l'esecuzione si ferma qui. Tutto quello che c' dopo

sx = parlamentare_votato(tree->left, partito);
non verr mai eseguito.
Cosa volevi fare con queste istruzioni?

Ah inoltre curr non inizializzato: quindi quando tu scrivi


if((curr->info.satellite.voti >= sx->info.satellite.voti) && (sx->info.satellite.voti >= dx->info.satellite.voti))
return curr;

stai comparando un albero costruito con il costruttore di default... ne sei consapevole e lo fai apposta?

E che cos' quell' "info.satellite"?

Poi c' anche un'altra cosa che non mi chiara, ma probabilmente dipende dalla mia ignoranza in fatto di alberi : tu hai una funzione che deve tornare un puntatore a nodo, invece ovunque in questo codice fai tornare un albero. Inoltre a quanto pare questo albero ha due metodi (left() e right() ) che tornano a loro volta un albero... che sarebbero? alberi che hanno come root un nodo in particolare?
A questo punto mi viene da pensare invece che TTree abbia un costruttore che prende un nodo e costruisce un albero che ha come root questo nodo, e che TTree::left() e TTree::right() invece restituiscano nodi, e che vengano costruiti gli alberi in modo implicito

paulinho
12-01-2013, 11:09
stai comparando un albero costruito con il costruttore di default... ne sei consapevole e lo fai apposta?

E che cos' quell' "info.satellite"?

Poi c' anche un'altra cosa che non mi chiara, ma probabilmente dipende dalla mia ignoranza in fatto di alberi : tu hai una funzione che deve tornare un puntatore a nodo, invece ovunque in questo codice fai tornare un albero. Inoltre a quanto pare questo albero ha due metodi (left() e right() ) che tornano a loro volta un albero... che sarebbero? alberi che hanno come root un nodo in particolare?
A questo punto mi viene da pensare invece che TTree abbia un costruttore che prende un nodo e costruisce un albero che ha come root questo nodo, e che TTree::left() e TTree::right() invece restituiscano nodi, e che vengano costruiti gli alberi in modo implicito [/QUOTE]

Innanzitutto grazie per l'attenzione datami; Dopodich premetto il seguente tipo costruito da me :


struct SNode {
TInfo info;
struct SNode *left;
struct SNode *right;
};
typedef struct SNode TNode;
typedef TNode* TTree;


struct SKey{
char tessera[8];
};
typedef struct SKey TKey;

struct SSat {
char cognome[16];
char nome[16];
char partito[6];
int voti;
};
typedef struct SSat TSat;

struct SInfo{
TKey key;
TSat satellite;
};

typedef struct SInfo TInfo;


Da questo codice si evince che in realt TTree un altro modo per indicare TNode*, le due notazioni sono la stessa cosa.
Poi tu stai parlando di costruttore e metodi, ma questo non riguarda la programmazione orientata agli oggetti, come il linguaggio java?

Comunque mi stai dando comunque degli spunti, ad esempio ora provo a inizializzare curr e a modificare la posizione delle chiamate ricorsive.

MegaAlchimista
12-01-2013, 12:16
Ah scusa non sono abituato a pnsare ai container in c, per qualche arcano motivo mi ero dimenticato del titolo di questo topic e pensavo stessi scrivendo in c++.
Detto questo: ancora peggio :D, se curr non inizializzato si becca i dati che trova in Ram quando viene creato, quindi devi inizializzarlo per forza.

E poi semplicemente ripensa a cosa sia una funzione ricorsiva: nel momento in cui tu chiami la funzione ricorsiva, quello un punto di uscita, quindi il codice successivo non verr eseguito.
Pensa prima ad una semplice funzione ricorsiva come quella del fattoriale (fattela per esercizio) e poi applica i principi a questa (che sicuramente pi complessa)

paulinho
12-01-2013, 14:05
Originariamente inviato da MegaAlchimista
Ah scusa non sono abituato a pnsare ai container in c, per qualche arcano motivo mi ero dimenticato del titolo di questo topic e pensavo stessi scrivendo in c++.
Detto questo: ancora peggio :D, se curr non inizializzato si becca i dati che trova in Ram quando viene creato, quindi devi inizializzarlo per forza.

E poi semplicemente ripensa a cosa sia una funzione ricorsiva: nel momento in cui tu chiami la funzione ricorsiva, quello un punto di uscita, quindi il codice successivo non verr eseguito.
Pensa prima ad una semplice funzione ricorsiva come quella del fattoriale (fattela per esercizio) e poi applica i principi a questa (che sicuramente pi complessa)

Grazie mille ancora per l'attenzione, non so chi tu sia, ma ti inizio a volere bene :zizi: , mi stai incoraggiando con i tuoi consigli. :) :) :)

Quindi una volta che faccio la chiamata ricorsiva tutto quello che segue non viene fatto? Giusto?
Dunque dovrei pensare alla condizione del "parlamentare pi votato" facendo in modo che risulti come caso base .. Giusto? e poi applicare le chiamate ricorsive? giusto ? alla fine ?

MegaAlchimista
12-01-2013, 15:35
Allora... Prendendone una semplice:


//queata funzione restituisce il fattoriale di n (=1*2*3*...n-1*n)
int fattoriale(int n)
{
If(n<=1)
return 1; //il mio vero punto di uscita
n *= fattoriale(n-1);
return n;
}


Allora entri nella funzione, con ingressi 0 o 1 la funzione torna 1 (perch cos definito il fattoriale), altrimenti copio n (vedi che non gli passo l'indirizzo, ma lo copio: importante) e lo moltiplico per il fattoriale del numero che lo precede... In questo modo questa stessa funzione viene richiamata n-1 volte.
ESEMPIO
Se la chiamo per n=3, lui entra ed esegue
n= 3* fattoriale(2) , per calcolare fattoriale di due esegue
n=2*fattoriale(1) , il fattoriale di 1 torna 1, quindi la prima chiamante in definitiva fa
N=1*2*3.
che quello che volevamo ottenere.
Allora cosa ha di particolare questa funzione?
In primis ha un punto di uscita (return 1) che dopo un certo numero di chiamate viene SEMPRE raggiunto!
Se cos non fosse la funzione continuerebbe a chiamare se stessa in modo infinito!
Dopo questo c' la vera ricorsione: la runzione richiama se stessa con differenti input.
Infine faccio ritornare il valore calcolato.

Ora pensaci bene ed applica questi concetti alla tua situazione

paulinho
15-01-2013, 09:59
Allora entri nella funzione, con ingressi 0 o 1 la funzione torna 1 (perch cos definito il fattoriale), altrimenti copio n (vedi che non gli passo l'indirizzo, ma lo copio: importante) e lo moltiplico per il fattoriale del numero che lo precede... In questo modo questa stessa funzione viene richiamata n-1 volte.
ESEMPIO
Se la chiamo per n=3, lui entra ed esegue
n= 3* fattoriale(2) , per calcolare fattoriale di due esegue
n=2*fattoriale(1) , il fattoriale di 1 torna 1, quindi la prima chiamante in definitiva fa
N=1*2*3.
che quello che volevamo ottenere.
Allora cosa ha di particolare questa funzione?
In primis ha un punto di uscita (return 1) che dopo un certo numero di chiamate viene SEMPRE raggiunto!
Se cos non fosse la funzione continuerebbe a chiamare se stessa in modo infinito!
Dopo questo c' la vera ricorsione: la runzione richiama se stessa con differenti input.
Infine faccio ritornare il valore calcolato.

Ora pensaci bene ed applica questi concetti alla tua situazione



ok grazie.Sembra di esserci riuscito.Un ultima domanda.. Quando alloco una struttura dati, che sia un albero o una lista o che si voglia, alla fine devo sempre deallocarla. giusto?

Loading