[C] Ricorsione occorrenze

[slashino]

Ho iniziato oggi con la ricorsione quindi non " prendetemi a calci "
Ho scritto una funzione che conti le occorrenze di un certo int in un vettore di int. Gli indici first e last indicano la parte del vettore che va controllata.
La funzione funziona con vettori che contengono un numero dispari di elementi, mentre invece non va bene con i numeri pari, oppure se non faccio coincidere first con l'inizio del vettore letto ( mi restituisce un numero di occorrenze maggiore ).
nb: ho scritto la stessa funzione ricorsiva dividendo il vettore in testa e in coda e va tutto bene, quindi sono interessato a implementarla dividendo il vettore a metà con pivot=(first+last)/2.

int conta(int *vett,int first,int last,int elemento)
{
    int parziale1,parziale2;
    int pivot;
    if(first>last)
    return 0;
    if(first==last)
    {
        if(*(vett+first)==elemento)
        return 1;
        else
        return 0;

    }
    pivot=(first+last)/2;
    parziale1=conta(vett,first,pivot,elemento);
    parziale2=conta(vett,pivot+1,last,elemento);
    if(*(vett+first)==elemento)
    {
        return parziale1+parziale2 +1;
    }
    else
    {
        return parziale1+parziale2 ;
    }
}

[ramy89]

Secondo me è l' approccio che è sbagliato.
Scegli un pivot ma il controllo avviene solo in un senso: dalla metà dell' array in poi.
E fai due chiamate ricorsive che potrebbero contare due volte gli stessi elementi.
Oltre al fatto che dopo le chiamate ricorsive conti ancora gli elementi.
Ti propongo un algoritmo migliore.
Questo è il prototipo:

int conta(int* v,int i, int j);
// chiamata nel main:
conta(v,0,N-1); // se l' array ha dimensione N

Algoritmo:

1)Se i<=j:
....Controllo v[i] e v[j], incrementando il risultato ad ogni valore che combacia con quello cercato;
2)Aggiungo al risultato conta(v,i+1,j-1);
3)Ritorno il risultato finale.

PS: Nel caso speciale in cui i==j, devi fare solo un controllo.

[Ifrit]

Allora, presupponento che è solo un esercizio, la funzione è ok ( a meno di una cavolata che ti scrivo in fondo)

Se segui mentalmente cosa accade quando chiami la funzione ti accorgi ogni valore viene scansionato dal tuo secondo IF, ovvero:

    if(first==last)
    {
        if(*(vett+first)==elemento)
        return 1;
        else
        return 0;

    }

Indi l'ultimo controllo e' inutile/dannoso, ovvero conti due volte lo stesso elemento.
Detto in altri termini, devi eliminare questa parte:

    if(*(vett+first)==elemento)
    {
        return parziale1+parziale2 +1;
    }
    else
    {
        return parziale1+parziale2 ;
    }

e sostituirla con:

      return parziale1 + parziale2;

tutto qua =)

per quanto riguarda quella cavolata a cui alludevo inizialmente, i primi due controlli non fanno uso delle variabili locali, indi e' inutile istanziare queste ultime prima =)
in altre parole:

      if(first==last)
         {
            if(*(vett+first)==elemento)
               return 1;
            else
               return 0;
         }
      if(first>last)
         return 0;

      int parziale1,parziale2;
      int pivot;

occupa meno memoria =)

Buon proseguimento di studio ^^

[slashino]

Grazie a tutti e due...illuminanti in modi diversi

[goatboy]

Sto provando a fare lo stesso esercizio e per evitare di aprire un'altra discussione, scrivo qui. Ho preso spunto dalla funzione suggerita da ramy89, ma non riesco a capire come farla ricorsiva... ho scritto così:

int conta(int *v, int i, int j, int elem){
    int occorrenze=0;
    if(i==j){
        printf("L'array ha un solo elemento: %d\n", *v);
    }
    for(i=0; i<=j; i++){
        if(v[i]==elem){
            occorrenze=occorrenze+1;
        }
    }
    return occorrenze;
}

e questo è il main:

int main(){
    int *p, dim, i, n, x;

    printf("Inserisci la dimensione del vettore: ");
    scanf("%d", &dim);

    if(dim==0 || dim<0){
        printf("Dimensione non valida!\n");
        return 0;
    }

    p=(int *)malloc(dim*sizeof(int));

    printf("Inserisci gli elementi del vettore:\n");
    for(i=0; i<dim; i++){
        scanf("%d", (p+i));
    }

    printf("\nInserisci l'elemento da cercare: ");
    scanf("%d", &x);

    n=conta(p, 0, dim-1, x);

    printf("Il numero %d e' presente %d volte\n\n", x, n);
    system("PAUSE");
}

Come posso renderla ricorsiva?
Ogni volta che devo pensare ad una funzione ricorsiva, sono in difficoltà perchè il ragionamento è abbastanza contorto (il dover richiamare la funzione all'interno della funzione stessa) , o forse sono io che sono cretino
Suggerimenti ?

[ramy89]

int conta(int *v, int i, int j, int elem){
    int occorrenze=0;
    if(i==j){
        printf("L'array ha un solo elemento: %d\n", *v);  
    // controlla se v[i] è uguale a elem e se si, incrementa il risultato
    }
    else if(i<j)
    {
        // controlli sia v[i] che v[j]
        //Chiamate ricorsive
    }
    return occorrenze;
}

La funzione ha come scopo quello di ritornare un valore.La stampa la puoi fare ler il debug, ma non confondere le cose.Le stai mischiando.
La parte "contorta" sta nell' effettuare le chiamate ricorsive.
Nel tuo caso ti basta chiamare la stessa funzione, ma passandogli come parametri i+1 e j-1.La chiamata va fatta esattamente come la fai nel main,ma con parametri diversi.
Quindi ad esempio:

occorrenze+=conta(v,i+1,j-1,elem);

Le chiavi per capire la ricorsione sono capire:
-Quando fermarsi;
-Con che parametri effettuare la (o le) chiamata ricorsiva;

[goatboy]

Grazie ramy
Ora già mi è più chiara la ricorsione, proverò con altri esercizi sicuramente. Grazie mille davvero!

Ho fatto come mi hai detto e la funzione va che è una meraviglia , anche nei casi particolari.

Solo non ho capito quando hai parlato della stampa. Non va bene se inserisco una stampa? So che nelle funzioni che hanno come scopo il ritornare un valore di solito è preferibile non mettere printf, però se le metto è proprio così sbagliato?

[ramy89]

Dipende molto dalla circostanze, in genere si mettono durante la fase di debugging e poi si tolgono.A meno che non siano stampe di errori come "Dimensione non valida", da far vedere all' utente.

[goatboy]

Originariamente inviato da ramy89
Dipende molto dalla circostanze, in genere si mettono durante la fase di debugging e poi si tolgono.A meno che non siano stampe di errori come "Dimensione non valida", da far vedere all' utente.

Capito, grazie come sempre!