[C++] Esercizio albero binario
L' esercizio è il seguente:
/*Abbiamo un albero binario r un valore intero y e k>=0 e vogliamo sapere se in r c'è un cammino
che si estende dalla radice fino ad una foglia che contiene esattamente k nodi con campo info
uguale a y. Nel seguito i cammini su un albero binario saranno rappresentati con una sequenza di
0/1 terminante con -1 a indicare appunto la fine del cammino. Quindi il cammino -1 è il cammino
vuoto che coincide con la radice. Per risolvere il problema appena descritto, si chiede di realizzare una funzione ricorsiva:
bool cerca_cam(nodo*r, int k, int y, int*C) che soddisfa la seguente pre- e post-condizione:
PRE=(albero(r) è ben formato e non vuoto, k>=0 e y valore qualsiasi, C ha almeno tanti elementi
quanta è l'altezza di albero(r))
POST= (restituisce true sse in albero(r) esiste un cammino da r ad una foglia con esattamente k
nodi con campo info=y e false altrimenti) &&(in caso restituisca true, C contiene una sequenza
(anche vuota) di 0/1 seguita da -1 e che individua il cammino più a sinistra in albero(r) con
esattamente k nodi con campo info=y).*/
Tutte le funzioni ausiliarie di costruzione dell'albero, stampa dell'albero e del cammino qualora trovato le ho già riportate sul C++. Ho qualche problema sulla risoluzione di questa funzione bool cerca_cam. Grazie
/*Abbiamo un albero binario r un valore intero y e k>=0 e vogliamo sapere se in r c'è un cammino
che si estende dalla radice fino ad una foglia che contiene esattamente k nodi con campo info
uguale a y. Nel seguito i cammini su un albero binario saranno rappresentati con una sequenza di
0/1 terminante con -1 a indicare appunto la fine del cammino. Quindi il cammino -1 è il cammino
vuoto che coincide con la radice. Per risolvere il problema appena descritto, si chiede di realizzare una funzione ricorsiva:
bool cerca_cam(nodo*r, int k, int y, int*C) che soddisfa la seguente pre- e post-condizione:
PRE=(albero(r) è ben formato e non vuoto, k>=0 e y valore qualsiasi, C ha almeno tanti elementi
quanta è l'altezza di albero(r))
POST= (restituisce true sse in albero(r) esiste un cammino da r ad una foglia con esattamente k
nodi con campo info=y e false altrimenti) &&(in caso restituisca true, C contiene una sequenza
(anche vuota) di 0/1 seguita da -1 e che individua il cammino più a sinistra in albero(r) con
esattamente k nodi con campo info=y).*/
Tutte le funzioni ausiliarie di costruzione dell'albero, stampa dell'albero e del cammino qualora trovato le ho già riportate sul C++. Ho qualche problema sulla risoluzione di questa funzione bool cerca_cam. Grazie
Risposte
Nessuna idea su come svilupparla?
Si ho un'idea ma se mi date la risoluzione la metto a confronto con la mia idea per capire l'errore
Risolvere questo tipo di problemi richiede tempo. Comunque faccio qualche considerazione:
Sia \(n\) un nodo, il percorso \(r\to n\) è ben determinato/univoco e contiene \(s\) elementi uguali a \(y\). Se \(s > k\) allora non ha senso andare avanti. Se \(s \le k\) allora la risposta non è altro che [inline]cerca_cam( n, k-s, y, C+L)[/inline] dove \(\displaystyle L \) è la lunghezza del tuo percorso. Puoi scrivere il cammino mentre percorri l'albero se ti fermi non appena ne trovi uno.
Sia \(n\) un nodo, il percorso \(r\to n\) è ben determinato/univoco e contiene \(s\) elementi uguali a \(y\). Se \(s > k\) allora non ha senso andare avanti. Se \(s \le k\) allora la risposta non è altro che [inline]cerca_cam( n, k-s, y, C+L)[/inline] dove \(\displaystyle L \) è la lunghezza del tuo percorso. Puoi scrivere il cammino mentre percorri l'albero se ti fermi non appena ne trovi uno.
In questo forum non si forniscono soluzioni a problemi senza che ci sia un tentativo da parte del creatore della discussione. Ed è comunque sempre preferibile aiutare ad arrivare alla soluzione piuttosto che fornirla in ogni caso.
Se hai un'idea di come risolvere questo problema allora puoi provare ad esporla e a raccontarci quali difficoltà tu abbia incontrato. Probabilmente possiamo aiutarti a capire dove stai sbagliando.
Se hai un'idea di come risolvere questo problema allora puoi provare ad esporla e a raccontarci quali difficoltà tu abbia incontrato. Probabilmente possiamo aiutarti a capire dove stai sbagliando.
"Nikk2000":
Si ho un'idea ma se mi date la risoluzione la metto a confronto con la mia idea per capire l'errore
Iniziamo con la tua...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo