[Java] Alberi semplici e ricorsione
Salve a tutti!
So che è una scemenza quella che sto per chiedervi ma non riesco proprio a trovare una via d'uscita..! trattasi di alberi binari semplici (SimpBTree).
questo è l'esercizio:
dato un SimpBTree di interi t trovare tutte le occorrenze di x in t
fin qui tutto facile, se non per il fatto che non posso usare variabili esterne al metodo (che è definito ricorsivo)
ho provato varie soluzioni, vi posto quella che si avvicina piu alla soluzione, secondo me:
il problema è che mi restituisce un valore fittizio.. per esempio il mio albero ha 4 ricorrenze di x=15 e quando vado ad eseguire mi restituisce 1!!
Facendo dei controlli con dei System.out.println si vede il valore che si incrementa correttamente, ma poi alla "ricomposizione" della funzione ricorsiva il valore si decrementa!!! cioè, io sono nel pallone perchè non trovo piu una soluzione valida! ho provato a implementarlo in mille modi diversi!!
Vi ringrazio anticipatamente!
So che è una scemenza quella che sto per chiedervi ma non riesco proprio a trovare una via d'uscita..! trattasi di alberi binari semplici (SimpBTree).
questo è l'esercizio:
dato un SimpBTree di interi t trovare tutte le occorrenze di x in t
fin qui tutto facile, se non per il fatto che non posso usare variabili esterne al metodo (che è definito ricorsivo)
ho provato varie soluzioni, vi posto quella che si avvicina piu alla soluzione, secondo me:
public static int occo(SimpBTree <Integer> t, int x)
{
if (t.empty()) return 0;
else if (t.root()==x) return 1+(occo(t.left(),x) & occo(t.right(),x));
else return occo(t.left(),x) | occo(t.right(),x);
}
il problema è che mi restituisce un valore fittizio.. per esempio il mio albero ha 4 ricorrenze di x=15 e quando vado ad eseguire mi restituisce 1!!
Facendo dei controlli con dei System.out.println si vede il valore che si incrementa correttamente, ma poi alla "ricomposizione" della funzione ricorsiva il valore si decrementa!!! cioè, io sono nel pallone perchè non trovo piu una soluzione valida! ho provato a implementarlo in mille modi diversi!!
Vi ringrazio anticipatamente!
Risposte
ciao,
mmm te sbagli nei rami dell'if. Perchè prima controlli che la chiave sia l'occorrenza, se lo è incrementi correttamente, ma poi vai in ricorsione e mettendo l'& vuoi dire all'algoritmo, se il numero di occorenze a destre e a sinitra sono uguali allora incrementi.
Se la chiave non è uguale fai una ricorsione e metti un'OR? e perchè mai?
è molto più facile di quello che pensi, qua puoi usare una tecnica detta "tail recursion", a top level l'operatore di tail recursione è la somma, l'incremento di un valore. Ma te ne metti due una somma e un'operatore booleano.
Per risolvere l'operatore in coda deve essere solo una somma, a te risolvere.
L'algoritmo non è che sia efficentissimo fatto così, ma è il più facile che tu possa creare con il codice che hai già scritto.
mmm te sbagli nei rami dell'if. Perchè prima controlli che la chiave sia l'occorrenza, se lo è incrementi correttamente, ma poi vai in ricorsione e mettendo l'& vuoi dire all'algoritmo, se il numero di occorenze a destre e a sinitra sono uguali allora incrementi.
Se la chiave non è uguale fai una ricorsione e metti un'OR? e perchè mai?
è molto più facile di quello che pensi, qua puoi usare una tecnica detta "tail recursion", a top level l'operatore di tail recursione è la somma, l'incremento di un valore. Ma te ne metti due una somma e un'operatore booleano.
Per risolvere l'operatore in coda deve essere solo una somma, a te risolvere.
L'algoritmo non è che sia efficentissimo fatto così, ma è il più facile che tu possa creare con il codice che hai già scritto.
si scusa nelle varie prove non l'ho corretto.. pero considera che mettevo solamente l'OR ( | ) in ogni controllo..
ora provo con la tail recursion!
ma per somma io metterei:
oppure forse è la cosa migliore fare:
??
ora provo con la tail recursion!
ma per somma io metterei:
return 1+(occo(t.left(),x) | occo(t.right(),x));
oppure forse è la cosa migliore fare:
return 1+occo(t.left(),x)+occo(t.right(),x);
??
secondo caso, rispondi però, perchè è corretto il secondo caso e non il primo?
ovviamente perche va a calcolae ogni sotto albero!
comunque l'ho modificato cosi
ma non funziona comunque... mi ritorna 1...
ti posto la parte del main per sicurezza:
comunque l'ho modificato cosi
public static int occo(SimpBTree <Integer> t, int x)
{
if (t.empty()) return 0;
else if (t.root()==x) return 1+(occo(t.left(),x) + occo(t.right(),x));
else return occo(t.left(),x) & occo(t.right(),x);
}
ma non funziona comunque... mi ritorna 1...
ti posto la parte del main per sicurezza:
SimpBTree <Integer> ab= new SimpBTree <Integer> (15, SimpBTree.EMPTYBTREE, SimpBTree.EMPTYBTREE);
SimpBTree <Integer> a4= new SimpBTree <Integer> (15, ab, ab);
SimpBTree <Integer> a31=new SimpBTree <Integer> (15, SimpBTree.EMPTYBTREE, SimpBTree.EMPTYBTREE);
SimpBTree <Integer> a3= new SimpBTree <Integer> (2,a4,a31);
SimpBTree <Integer> a2= new SimpBTree <Integer> (-10,a3,SimpBTree.EMPTYBTREE);
SimpBTree <Integer> a1= new SimpBTree <Integer> (15,a2,SimpBTree.EMPTYBTREE);
System.out.println("quante occorrenze esistono di 15?"+SimpBTree.occo(a1,15));
Supposto che SimpleBTree disponga di un metodo getInfo() per ricavare l'informazione incapsulata nel nodo (in questo caso si tratta di un intero), allora credo che l'algoritmo dovrebbe essere questo:
Dovrebbe fuzionare, prova e fammi sapere..
public int contaOccorrenze(SimpleBTree<Integer> t, int x){
int occorrenze = 0;
if( t != null ){
if( t.getInfo() == x ){
occorrenze = 1 + contaOccorrenze(t.left(), x) + contaOccorrenze(t.right(), x);
}else{
occorrenze = occorrenze + contaOccorrenze(t.left(), x) + contaOccorrenze(t.right(), x);
}
}
return occorrenze;
}
Dovrebbe fuzionare, prova e fammi sapere..
Ancora non ci siamo capiti, la tail recursion deve essere fatta su ogni ramo dell'if:
@xls: il principio del tuo codice è simile alla "tail recursion", te la simuli con una variabile, adesso non ricordo bene, ma mi sembra sia più efficente la mia versione, o forse è il contrario perchè allocchi sempre una nuova varibile locale e questo non è molto efficente, ma parliamo di complessità minime
public static int occo(SimpBTree <Integer> t, int x)
{
if (t.empty()) return 0;
else if (t.root()==x) return 1+(occo(t.left(),x) + occo(t.right(),x));
else return occo(t.left(),x) + occo(t.right(),x));
}
@xls: il principio del tuo codice è simile alla "tail recursion", te la simuli con una variabile, adesso non ricordo bene, ma mi sembra sia più efficente la mia versione, o forse è il contrario perchè allocchi sempre una nuova varibile locale e questo non è molto efficente, ma parliamo di complessità minime
oooooo!!!! finalmente!!!!!!
ecco dove sbagliavo!!! grazie mille!!!
@xls: facendo come hai detto tu a ogni chiamata ricorsiva (tralasciando il discorso della complessità) la variabile viene sempre reinizializzata a 0, giusto?
quindi non fa!!
grazie mille cmq!!!! finalmente ho risolto!
ecco dove sbagliavo!!! grazie mille!!!
@xls: facendo come hai detto tu a ogni chiamata ricorsiva (tralasciando il discorso della complessità) la variabile viene sempre reinizializzata a 0, giusto?
quindi non fa!!
grazie mille cmq!!!! finalmente ho risolto!
"m3c4":
@xls: facendo come hai detto tu a ogni chiamata ricorsiva (tralasciando il discorso della complessità) la variabile viene sempre reinizializzata a 0, giusto?
quindi non fa!!
Ma l'hai provato almeno?
@ham_burst: credo sia più performante il tuo
però in questo caso non ha molta importanza.
"xsl":
[quote="m3c4"]
@xls: facendo come hai detto tu a ogni chiamata ricorsiva (tralasciando il discorso della complessità) la variabile viene sempre reinizializzata a 0, giusto?
quindi non fa!!
Ma l'hai provato almeno?
@ham_burst: credo sia più performante il tuo
però in questo caso non ha molta importanza.[/quote]si xk il primo che avevo fatto era pari pari al tuo..!
mmm per risolvere il problema del codice di xls, che non ho provato. Penso che abbia messo insieme due tecniche. Si dovrebbe passare "occorrenze" per valore, utilizzando la tecnica "ricorsione con accumulatore".
E chiamare la funzione con questo parametro da un'altra funzione con tipo occo(t,x,0).
E chiamare la funzione con questo parametro da un'altra funzione con tipo occo(t,x,0).
"ham_burst":
Si dovrebbe passare "occorrenze" per valore, utilizzando la tecnica "ricorsione con accumulatore".
E chiamare la funzione con questo parametro da un'altra funzione con tipo occo(t,x,0).
Si esatto.
anche, ho provato prima a fare cosi, ma ho preferito l'ultima soluzione per una buona abitudine nella gestione delle variabili..
non è ora il problema dato che si lavora su poche righe di codice, piu che altro il problema sorge quando implementi diverse variabili su un programma grosso.. li penso davvero che la troppa presenza di variabili possa appesantire la memoria e il corretto funzionamento del programma..
non è ora il problema dato che si lavora su poche righe di codice, piu che altro il problema sorge quando implementi diverse variabili su un programma grosso.. li penso davvero che la troppa presenza di variabili possa appesantire la memoria e il corretto funzionamento del programma..
Non vorrei farti confondere. La tecnica tail recursion è più "performante" nei linguaggi funzionali, dove il concetto di memoria non esiste, c'è l'ambiente, è un altro mondo.
Ti ho consigliato quel modo, perchè più facile da vedere, con il codice che avevi scritto.
Invece la tecnica di xls se scritta bene o la tecnica con passaggio per valore (con accumulatore) o funzione con valore di ritorno è un metodo standard, che per i linguaggi OO vai sempre via liscio.
Se tu facessi un'analisi dell'algoritmo capiresti che si è più "veloce" (passami il termine), ma dove pensi vengano salvate le variabili e l'alloccazione? Nello stack della memoria, e ti faccio immaginare cosa succeda con troppe chiamate ricorsive. Forse in a Java è ancora diverso da codice scritto in altri linguaggi, ma è simile.
Sunto: se sei in OO cerca di andare sempre con pattern standard.
Ti ho consigliato quel modo, perchè più facile da vedere, con il codice che avevi scritto.
Invece la tecnica di xls se scritta bene o la tecnica con passaggio per valore (con accumulatore) o funzione con valore di ritorno è un metodo standard, che per i linguaggi OO vai sempre via liscio.
Se tu facessi un'analisi dell'algoritmo capiresti che si è più "veloce" (passami il termine), ma dove pensi vengano salvate le variabili e l'alloccazione? Nello stack della memoria, e ti faccio immaginare cosa succeda con troppe chiamate ricorsive. Forse in a Java è ancora diverso da codice scritto in altri linguaggi, ma è simile.
Sunto: se sei in OO cerca di andare sempre con pattern standard.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo