[C] Funzione di verifica ricorsiva

[floriano94]

Si vuole scrivere una funzione ricorsiva che controlli che in un array di interi ogni occorrenza di un intero $i$ sia preceduta (non per forza immediatamente) da un intero $j$ e che restituisca $true$ se la proprietà risulta verificata e $false$ altrimenti.

Per chiarezza è stato definito il tipo

typedef enum{false,true} boolean;

Ho provato a procedere in diversi modi ma le mie soluzioni sono state sempre parziali,ossia in casi specifici (seppur particolari) non erano più valide...chi mi darebbe una mano per capire più o meno il procedimento da seguire?

[onlyReferee]

Ciao floriano94
Suggerimento mio: inizia intanto con l'individuare i casi base (fai conto inizialmente di avere un vettore vuoto oppure con un solo elemento). Oltre ai parametri che sicuramente avrai individuato ti servirà passare alla funzione anche un altro flag. Ragionando capirai perché (in realtà a riguardo è come se ti fossi già risposto da solo poiché se hai ragionato determinando solo casi parziali finora penso sia dovuto essenzialmente a questo)...

[vict85]

Non capisco tre cose:
[list=1][*:2hx8njyv] Se basta che ci sia un \(j\) prima di ogni \(i\) non ti basta controllare che il primo \(j\) sia prima del primo \(i\). Insomma ogni altri \(\displaystyle i \) è dopo il primo e se vale per il primo \(\displaystyle i \) allora vale per tutti.[/*:m:2hx8njyv]
[*:2hx8njyv] Per quale ragione vuoi farlo ricorsivo?[/*:m:2hx8njyv]
[*:2hx8njyv] Perché non include semplicemente stdbool oppure usa _Bool dato che sono state introdotte nel c99 ? [/*:m:2hx8njyv][/list:o:2hx8njyv]

Comunque penso che il professore pensava a qualcosa tipo questo:

bool func(int const a[], unsigned const n, int const i, int const j);

int main()
{
    int const a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int const i = 2;
    int const j = 1;

    bool const res = func(a, 10, i, j);

    if(res == true)
        puts("true");
    else
        puts("false");

    return 0;
}

bool func(int const a[], unsigned const n, int const i, int const j)
{
    static bool r = true;

    if(n == 0)
        return r;

    int t = a[n-1];
    if(t == i)
        r = false;
    else if(t == j)
        r = true;

    return func(a, n-1, i, j);
}

Il trucchetto che ho usato usa una variabile static ma usando una seconda funzione che fa materialmente la ricorsione si può aggirare il suo uso.

[floriano94]

Grazie per le risposte

onlyReferee , mi suggerisci di aggiungere un nuovo parametro formale alla funzione? A dire la verità molto spesso mi è capitato di risolvere aggiungendo un parametro in più quando invece si poteva risolvere anche senza..
la soluzione (seguendo quanto detto da vict85 nel punto 1) dovrebbe essere la seguente:

boolean check(int v[],int dim,int i,int j,boolean verifica){
                                if(dim!=0){
                                           if(v[dim-1]==i) verifica=false;
                                           else if(v[dim-1]==j) verifica=true;
                                           check(v,dim-1,i,j,verifica);}
                                else return verifica;}

vict85 rispondo subito alla domanda 2) il testo dell'esercizio richiede una soluzione ricorsiva. 3) nella traccia dell'esercizio è specificato di utilizzare un tipo booleano definito come sopra.
Detto questo riguardo la domanda 1 in realtà la traccia dell'esercizio non è molto chiara...naturalmente il caso da te considerato è più semplice di quello in cui ci deve essere prima di ciascun "i" un j diverso compreso tra una occorrenza di i e la successiva (non so se mi sono spiegato bene ). Per questo mi chiedevo in questo secondo caso come si potrebbe fare..
Purtroppo non si possono usare nemmeno delle costanti(questo viene specificato sempre dalla traccia dell'esercizio). Grazie!

p.s.vict85 grazie per il codice che hai postato è un'ottima idea, ora devo eliminare quella costante.

[vict85]

Mi sono accorto che usare una static crea problemi se devi chiamare la funzione più di una volta. Insomma la funzione è sbagliata.

Beh, per eliminare quella variabile devi per forza usare due funzioni (insomma ci sono due stati ben distinti, quindi devi memorizzare lo stato da qualche parte).

Queste sono varie opzioni (la 1 e la 2 sono quelle che non usano memorizzazione, la 3 e la 4 evitano una static ma non una variabile). La 1 e la 2 risolvono problemi diversi (insomma i due casi).

#include <stdbool.h>
#include <stdio.h>

bool func(int const a[], unsigned const n, int const i, int const j);
bool func_bis(int const a[], unsigned const n, int const i, int const j);

bool func2(int const a[], unsigned const n, int const i, int const j);
bool func_bis2(int const a[], unsigned const n, int const i, int const j);

bool func3(int const a[], unsigned const n, int const i, int const j);
bool func_bis3(int const a[], unsigned const n, int const i, int const j, bool b);

bool func4(int const a[], unsigned const n, int const i, int const j);
bool func_bis4(int const a[], unsigned const n, int const i, int const j, bool b);

int main()
{
    int const a[10] = { 0, 1, 2, 3, 4, 2, 6, 7, 8, 9 };
    int const i = 2;
    int const j = 1;

    bool res = func(a, 10, i, j);

    if(res == true)
        puts("true");
    else
        puts("false");

    res = func2(a, 10, i, j);

    if(res == true)
        puts("true");
    else
        puts("false");

    res = func3(a, 10, i, j);

    if(res == true)
        puts("true");
    else
        puts("false");

    res = func4(a, 10, i, j);

    if(res == true)
        puts("true");
    else
        puts("false");

    return 0;
}


/*
*   CASO 1: non ci sono due occorrenza consecutive di i
*/
bool func(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return true;

    int const t = a[n-1];
    if(t == i)
        return func_bis(a, n-1, i, j);

    return func(a, n-1, i, j);
}

bool func_bis(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return false;

    int const t = a[n-1];
    if(t == i)
        return false;
    else if(t == j)
        return func(a, n-1, i, j);

    return func_bis(a, n-1, i, j);
}


/*
*   CASO 2: basta che ci sia un j prima di ogni occorrenza di i
*/
bool func2(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return true;

    int const t = a[n-1];
    if(t == i)
        return func_bis2(a, n-1, i, j);

    return func2(a, n-1, i, j);
}

bool func_bis2(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return false;

    int const t = a[n-1];
    if(t == j)
        return func2(a, n-1, i, j);

    return func_bis2(a, n-1, i, j);
}


/*
*   CASO 1 con metodo diverso
*/
bool func3(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return true;

    int const t = a[n-1];
    if(t == i)
        return func_bis3(a, n-1, i, j, false);

    return func_bis3(a, n-1, i, j, true);
}

bool func_bis3(int const a[], unsigned const n, int const i, int const j, bool b)
{
    if(n == 0)
        return b;

    int const t = a[n-1];
    bool const b2 = !(t == i);
    bool const b3 = (t == j);
    b = b2 && ( b || b3 );
    if(b && b2)
        return false;

    return func_bis3(a, n-1, i, j, b);
}

/*
*   CASO 2 con metodo diverso
*/
bool func4(int const a[], unsigned const n, int const i, int const j)
{
    if(n == 0)
        return true;

    int const t = a[n-1];
    if(t == i)
        return func_bis3(a, n-1, i, j, false);

    return func_bis4(a, n-1, i, j, true);
}

bool func_bis4(int const a[], unsigned const n, int const i, int const j, bool b)
{
    if(n == 0)
        return b;

    int const t = a[n-1];
    bool const b2 = !(t == i);
    bool const b3 = (t == j);
    b = b2 && ( b || b3 );

    return func_bis4(a, n-1, i, j, b);
}

[floriano94]

Grazie vict85, la tua risposta mi è stata molto d'aiuto. La costruzione della doppia funzione nel caso1 risolvono il problema in un modo interessante. Grazie ancora!