[C++] Esercizio: determinare picchi ravvicinati con funzione ricorsiva

[mistergks]

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 l’array è 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]

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]

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]

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]

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]

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]

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]

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]

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]

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.