PDA

Visualizza la versione completa : [C++] Esercizio: determinare picchi ravvicinati con funzione ricorsiva


mistergks
19-03-2011, 19:28
Ho provato a fare questo esercizio:

Si scriva in C++ una funzione ricorsiva che riceva un array di numeri interi e la sua dimensione (che si suppone essere dispari) e restituisca TRUE se larray costituito da una serie di picchi ravvicinati. Un picco un gruppo di tre elementi consecutivi in cui quello centrale maggiore dei due esterni e due picchi si dicono ravvicinati se il terzo elemento di un picco il primo elemento del picco successivo.
Esempio: la funzione invocata su un array contenente la sequenza di interi 1 3 2 4 -3 7 -5 8 4 dovr restituire TRUE. Infatti la sequenza contiene i 4 picchi {1, 3 , 2}, {2, 4, -3}, {-3, 7, -5}, {-5, 8, 4} e sono ravvicinati ( ad esempio, i picchi {1, 3 , 2}e {2, 4, -3}condividono il numero 2, e cos via).
Specificare quale deve essere la prima invocazione per la funzione.

La mia prova di soluzione questa... Ditemi cosa sbaglio?? :



bool picchi(int M[], int dim, int i1, int i, int i2){
if(dim%2==0) //caso base
return false;
if(M[i]>M[i1] && M[i]>M[i2])
return true;

return picchi(M, dim, i1+2, i+2, i2+2);
}

VincenzoTheBest
19-03-2011, 19:51
Originariamente inviato da mistergks
La mia prova di soluzione questa... Ditemi cosa sbaglio?? :



bool picchi(int M[], int dim, int i1, int i, int i2){
if(dim%2==0) //caso base
return false;
if(M[i]>M[i1] && M[i]>M[i2])
return true;

return picchi(M, dim, i1+2, i+2, i2+2);
}

Prima di tutto ti basta un solo indice per la scansione, io ne vedo 2 di troppo.
Poi devi sistemare il passo base: la funzione deve terminare quando l'indice di scansione pari a dim;
infine devi restituire false se gli elementi ai lati del "picco" non sono minori di esso.

menphisx
19-03-2011, 20:56
bool picchi(int M[], int middle){

if(middle == 0)
middle++;

if(dim % 2 == 0) //caso base
return false;

if(middle == dim)
return true;

if(M[middle] > M[middle - 1] && M[middle] > M[middle + 1])
return true;

return picchi(M, dim, middle + 2);

}



Penso possa andare bene, molto pi semplice.

menphisx
19-03-2011, 20:59
Ma non dovrebbe essere cos ?



bool picchi(int M[], int middle){

if(middle == 0)
middle++;

if(dim % 2 == 0) //caso base
return false;

if(middle == dim)
return true;

if(M[middle] > M[middle - 1] && M[middle] > M[middle + 1])
return picchi(M, dim, middle + 2);

}

VincenzoTheBest
19-03-2011, 21:49
Originariamente inviato da menphisx
Ma non dovrebbe essere cos ?



bool picchi(int M[], int middle){

if(middle == 0)
middle++;

if(dim % 2 == 0) //caso base
return false;

if(middle == dim)
return true;

if(M[middle] > M[middle - 1] && M[middle] > M[middle + 1])
return picchi(M, dim, middle + 2);

}


Non va proprio bene, per i seguenti motivi:
- la segnatura del metodo ha un parametro in meno, quindi la chiamata ricorsiva risulterebbe essere errata;
- il controllo sulla variabile middle inutile, in quanto si deve assumere che questa parta da 1;
- il controllo su dim non il passo base (questo controllo meglio farlo prima della chiamata della funzione oppure compattarlo opportunamente con altri controlli), il passo base rappresentato dall'istruzione successiva;
- il passo ricorsivo inconsistente anche con il passo base.

menphisx
19-03-2011, 21:56
Originariamente inviato da VincenzoTheBest
Non va proprio bene, per i seguenti motivi:
- la segnatura del metodo ha un parametro in meno, quindi la chiamata ricorsiva risulterebbe essere errata;
- il controllo sulla variabile middle inutile, in quanto si deve assumere che questa parta da 1;
- il controllo su dim non il passo base (questo controllo meglio farlo prima della chiamata della funzione oppure compattarlo opportunamente con altri controlli), il passo base rappresentato dall'istruzione successiva;
- il passo ricorsivo inconsistente anche con il passo base.

Si ho sbagliato, ma stato un errore di distrazione la funzione sarebbe:


bool picchi(int M[], int dim, int middle){

if(middle == 0) //Meglio non assumere che parta da uno :) Semmai il controllo si pu spostare fuori dalla funzione :)
middle++;

if(dim % 2 == 0) //caso base
return false;

if(middle == dim)
return true;

if(M[middle] > M[middle - 1] && M[middle] > M[middle + 1])
return picchi(M, dim, middle + 2);

}

VincenzoTheBest
19-03-2011, 23:01
Originariamente inviato da menphisx
Si ho sbagliato, ma stato un errore di distrazione la funzione sarebbe:

Non me ne volere ma non va bene.
Una soluzione corretta questa:


bool picchiRavvicinati(int i, int A[], int length){
if( i == length )
return true;

if( length%2 == 0 || A[i - 1] >= A[i] || A[i + 1] >= A[i] )
return false;
return picchiRavvicinati(i+2, A, length);
}

mistergks
20-03-2011, 01:30
Ok ho capito! grazie mille! quindi il mio errore principale era quello di usare tre indici inutili! Eh purtroppo non avevo pensato che all'interno dell'if potessi controllare l'array con un solo indice facendo -1 e +1!
Vabb sbagliando si impara :-D e io sto imparando davvero tanto grazie a questo forum!

mistergks
20-03-2011, 02:07
Ho provato a fare un main e a compilare il tutto, ma mi restituisce uno 0! E' normale?!?!?


#include <iostream>
using namespace std;

bool picchiRavvicinati(int i, int A[], int length);

int main(){
int A[]={1,3,2,4,-3,7,-5,8,4};
int length=9, i=0;
cout<<"prova: "<<picchiRavvicinati(i, A, length);

system("pause");
return 0;
}

bool picchiRavvicinati(int i, int A[], int length){

if( i == length )
return true;

if( length%2 == 0 || A[i - 1] >= A[i] || A[i + 1] >= A[i] )
return false;
return picchiRavvicinati(i+2, A, length);
}

VincenzoTheBest
20-03-2011, 12:18
Originariamente inviato da mistergks


...
int main(){
int A[]={1,3,2,4,-3,7,-5,8,4};
int length=9, i=0;
cout<<"prova: "<<picchiRavvicinati(i, A, length);

system("pause");
return 0;
}
...

Come ho gi detto l'indice deve partire da 1.

Loading