Aiutino di C...

marcus81 · 04-02-2002, 19:24

Dunque devo implementare in C una procedura così definita:

void MinMaxPath(Tree *ptr, int *max, int *min)

questa funzione dato un albero binario deve calcolare la lunghezza minima e massima tra tutti i possibili percorsi radice-foglie e deve restituire i valori trovati...
Help me...thank you...

marcus81 · 04-02-2002, 20:45

nessuno??

cionci · 04-02-2002, 20:58

Bella questa roba ricorsiva !!!!
Premetto che lo scriverò in C++, anche se probabilmente non dovrai fare nulla per adattarlo...

void MinMaxPath(Tree *t, int *min, int *max)
{
int minDx, minSx, maxDx, maxSx;
minDx = minSx = maxDx = maxSx = 0;
if(!t) {
*max = 0;
*min = 0;
return;
}
if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx);
if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx);
*min = (minDx < minSx) ? minDx : minSx;
*max = (maxDx > maxSx) ? maxDx : maxSx;
++(*min);
++(*max);
}

Non l'ho provato, ma dovrebbe andare bene...

marcus81 · 04-02-2002, 21:20

Non è che potresti mettere qualche commentino...soprattutto quella condizione (!t)...grazie

cionci · 05-02-2002, 11:18

!t significa che ti hanno passato un albero vuoto (il puntatore vuoto è NULL cioè 0), quindi !t significa se l'albero è vuoto...

Stessa cosa per if(t->dx) e if(t->sx) esegue quella chiamato solo i puntatori ai figli di sinistra e di destra contengono un elemento...

Quegli if potrebero essere omessi, anzi nella forma canonica della ricorsione andrebbero omessi perchè la condizione d'arresto è if(!t) iniziale... Ce l'ho messi perchè, visto che in ogni chiamata si spreca heap, risparmiare un po' di risorse ed essere + veloci...

Infatti se omettevo i due if avrebbe pensato la condizione di arresto a ritornare valori comunque validi per la nostra ricorsione...

In questo modo la condizione di arresto non può comunque essere omessa perchè se ti passano un albero vuoto dobbiamo comunque ritornare 0 e 0...

Ti insegno il trucco per le ricorsione...non pensare a come deve funzionare il problema globalmente altirmenti non riuscirai mai a scrivere la ricorsione.

Inizia con la condizione di arresto che in tutti i casi deve essere presente (solitamente si controlla se il puntatore passato è vuoto)...

Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli...

A questo punto hai già finito...

Fai una prova con due elementi per le liste e con un albero assimmetrico con due elemnti per gli alberi binari (una radice con un solo figlio)...ed ecco finito tutto !!!

marcus81 · 05-02-2002, 17:27

Scusa ma ke vuol dire questo:
"Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli..."
Non capisco cosa vuol dir "...l'elemento che riceve i risultati dagli elementi nulli"...
Potresti spiegarti un pò meglio??Grazie mille.

cionci · 05-02-2002, 19:34

Una volta scritta la condizione di arresto...passi a scrivere quello che deve fare la funzione nel caso più semplice...ovvero quello di un solo elemento...e richiamando la funzione sul successivo elemento (o sui successivi nel caso di una labero) anche se sai che è nullo... Questo ti può essere utile anche per stabilire i valori precisi che ti deve ritornaer la condizione di arresto...

Verifichi che il codice da te scritto si comporti nel modo giusto....e poi passi ad un caso più generale in cui non conosci i valori che ti ritornano le ricorsioni...e controlli che la funzione si comporti sempre nel modo giusto...

Comunque non pensare mai in modo GLOBALE...pensa solo ad un elemento nullo, un solo elemento...oppure ad un elemento generico...

Se epnsi in modo GLOBALE al problema è difficilissimo risucire a trovare il codice giusto...

cionci · 05-02-2002, 20:37

Avevo fatto un errore di confusione sul secondo post...

!t significa se l'albero è vuoto (non "non è vuoto" come avevo scritto prima)...

marcus81 · 06-02-2002, 19:23

Cionci: la funziona l'ho provata in un programma completo...ha un problema: praticamente restituisce sia l'altezza minima ke quella massima maggiorate di uno...cosa dovrei aggiungere??Grazie.

cionci · 06-02-2002, 19:31

Sì ? Mmmhh strano... Io non l'ho provata...magari ci faccio qualche prova...

cionci · 06-02-2002, 19:45

Quote:

Originariamente inviato da marcus81
[b]Cionci: la funziona l'ho provata in un programma completo...ha un problema: praticamente restituisce sia l'altezza minima ke quella massima maggiorate di uno...cosa dovrei aggiungere??Grazie.

Fammi un esempio...con un nodo solo...quanto mi deve ritornare la funzione ? 1 o 0 ?

marcus81 · 06-02-2002, 19:58

con un nodo solo, cioè con la sola radice deve restituire 0...

marcus81 · 06-02-2002, 20:00

Se vuoi ti allego il programma completo e gli dai un occhiata...

cionci · 06-02-2002, 20:07

Nono....l'ho già fatto...

Io avevo capito che dovevo calcolare la profondità minima e massima dell'albero...comunque basta poco per modificarlo...

Prova così se ti torna...

void MinMaxPath(Tree *t, int *min, int *max)
{
int minDx, minSx, maxDx, maxSx;
minDx = minSx = maxDx = maxSx = 0;
if(!t||(!t->dx && !t->sx)) { //ho modificato qui
*max = 0;
*min = 0;
return;
}
if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx);
if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx);
*min = (minDx < minSx) ? minDx : minSx;
*max = (maxDx > maxSx) ? maxDx : maxSx;
++(*min);
++(*max);
}

cionci · 06-02-2002, 20:09

In pratica ne conta uno in meno perchè non conta le foglie

Questi esercizi erano la mia passione !!! Si vede ?

marcus81 · 06-02-2002, 20:36

ti ringrazio molto...adesso lo provo...ma tu che fai nella vita??

cionci · 06-02-2002, 20:40

Studio (poco) ingegneria informatica...quindi sono ovviamente progammatore...

Poi sono anche webmaster e faccio siti web...

marcus81 · 06-02-2002, 20:42

Io faccio informatica e questo è il mio primo linguaggio di programmazione...

cionci · 06-02-2002, 20:47

Che ti sembra ? Bello il C, vero ? E il C++ è anche più bello !!!

cionci · 06-02-2002, 20:48

Ci vediamo...vado a pappare...

04-02-2002, 19:24	#1
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Aiutino di C... Dunque devo implementare in C una procedura così definita: void MinMaxPath(Tree ptr, int max, int min) questa funzione dato un albero binario deve calcolare la lunghezza minima e massima tra tutti i possibili percorsi radice-foglie e deve restituire i valori trovati... Help me...thank you... __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

04-02-2002, 20:45	#2
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	nessuno?? __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

04-02-2002, 21:20	#4
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Non è che potresti mettere qualche commentino...soprattutto quella condizione (!t)...grazie __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

05-02-2002, 17:27	#6
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Scusa ma ke vuol dire questo: "Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli..." Non capisco cosa vuol dir "...l'elemento che riceve i risultati dagli elementi nulli"... Potresti spiegarti un pò meglio??Grazie mille. __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

06-02-2002, 19:23	#9
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Cionci: la funziona l'ho provata in un programma completo...ha un problema: praticamente restituisce sia l'altezza minima ke quella massima maggiorate di uno...cosa dovrei aggiungere??Grazie. __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

04-02-2002, 20:58	#3
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Bella questa roba ricorsiva !!!! Premetto che lo scriverò in C++, anche se probabilmente non dovrai fare nulla per adattarlo... void MinMaxPath(Tree t, int min, int max) { int minDx, minSx, maxDx, maxSx; minDx = minSx = maxDx = maxSx = 0; if(!t) { max = 0; min = 0; return; } if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx); if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx); min = (minDx < minSx) ? minDx : minSx; max = (maxDx > maxSx) ? maxDx : maxSx; ++(min); ++(*max); } Non l'ho provato, ma dovrebbe andare bene...

05-02-2002, 11:18	#5
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	!t significa che ti hanno passato un albero vuoto (il puntatore vuoto è NULL cioè 0), quindi !t significa se l'albero è vuoto... Stessa cosa per if(t->dx) e if(t->sx) esegue quella chiamato solo i puntatori ai figli di sinistra e di destra contengono un elemento... Quegli if potrebero essere omessi, anzi nella forma canonica della ricorsione andrebbero omessi perchè la condizione d'arresto è if(!t) iniziale... Ce l'ho messi perchè, visto che in ogni chiamata si spreca heap, risparmiare un po' di risorse ed essere + veloci... Infatti se omettevo i due if avrebbe pensato la condizione di arresto a ritornare valori comunque validi per la nostra ricorsione... In questo modo la condizione di arresto non può comunque essere omessa perchè se ti passano un albero vuoto dobbiamo comunque ritornare 0 e 0... Ti insegno il trucco per le ricorsione...non pensare a come deve funzionare il problema globalmente altirmenti non riuscirai mai a scrivere la ricorsione. Inizia con la condizione di arresto che in tutti i casi deve essere presente (solitamente si controlla se il puntatore passato è vuoto)... Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli... A questo punto hai già finito... Fai una prova con due elementi per le liste e con un albero assimmetrico con due elemnti per gli alberi binari (una radice con un solo figlio)...ed ecco finito tutto !!!

05-02-2002, 19:34	#7
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Una volta scritta la condizione di arresto...passi a scrivere quello che deve fare la funzione nel caso più semplice...ovvero quello di un solo elemento...e richiamando la funzione sul successivo elemento (o sui successivi nel caso di una labero) anche se sai che è nullo... Questo ti può essere utile anche per stabilire i valori precisi che ti deve ritornaer la condizione di arresto... Verifichi che il codice da te scritto si comporti nel modo giusto....e poi passi ad un caso più generale in cui non conosci i valori che ti ritornano le ricorsioni...e controlli che la funzione si comporti sempre nel modo giusto... Comunque non pensare mai in modo GLOBALE...pensa solo ad un elemento nullo, un solo elemento...oppure ad un elemento generico... Se epnsi in modo GLOBALE al problema è difficilissimo risucire a trovare il codice giusto...

05-02-2002, 20:37	#8
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Avevo fatto un errore di confusione sul secondo post... !t significa se l'albero è vuoto (non "non è vuoto" come avevo scritto prima)...

06-02-2002, 19:31	#10
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Sì ? Mmmhh strano... Io non l'ho provata...magari ci faccio qualche prova...

06-02-2002, 19:58	#12
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	con un nodo solo, cioè con la sola radice deve restituire 0... __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

06-02-2002, 20:00	#13
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Se vuoi ti allego il programma completo e gli dai un occhiata... __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

06-02-2002, 20:07	#14
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Nono....l'ho già fatto... Io avevo capito che dovevo calcolare la profondità minima e massima dell'albero...comunque basta poco per modificarlo... Prova così se ti torna... void MinMaxPath(Tree t, int min, int max) { int minDx, minSx, maxDx, maxSx; minDx = minSx = maxDx = maxSx = 0; if(!t\|\|(!t->dx && !t->sx)) { //ho modificato qui max = 0; min = 0; return; } if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx); if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx); min = (minDx < minSx) ? minDx : minSx; max = (maxDx > maxSx) ? maxDx : maxSx; ++(min); ++(*max); }

06-02-2002, 20:09	#15
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	In pratica ne conta uno in meno perchè non conta le foglie Questi esercizi erano la mia passione !!! Si vede ?

06-02-2002, 20:36	#16
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	ti ringrazio molto...adesso lo provo...ma tu che fai nella vita?? __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

06-02-2002, 20:40	#17
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Studio (poco) ingegneria informatica...quindi sono ovviamente progammatore... Poi sono anche webmaster e faccio siti web...

06-02-2002, 20:42	#18
marcus81 Senior Member Iscritto dal: Dec 2001 Città: Partinico(PA)-Torino Messaggi: 2885	Io faccio informatica e questo è il mio primo linguaggio di programmazione... __________________ Main: Barton 2500@3200+ Asus A7N8X-dlx 2*512 DDRPowercolor 9800Pro Maxtor 80GB sATA + Seagate 160GB pATA LCD Acer AL1721 Epson C62 Antec T.P. 430w Tin.it ADSL Muletto: Pentium4 1800 Notebook: Idea Progress P4 Auto e moto d'epoca

06-02-2002, 20:47	#19
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Che ti sembra ? Bello il C, vero ? E il C++ è anche più bello !!!

06-02-2002, 20:48	#20
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	Ci vediamo...vado a pappare...

Strumenti
Mostra una versione stampabile Invia questa pagina per email