Visualizzazione dei risultati da 1 a 9 su 9
  1. #1
    Utente di HTML.it
    Registrato dal
    Oct 2011
    Messaggi
    156

    Ricorsione occorrenze

    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.
    codice:
    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 ;
        }
    }

  2. #2
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    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:

    codice:
    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.

  3. #3
    Utente di HTML.it L'avatar di Ifrit
    Registrato dal
    Oct 2005
    Messaggi
    116
    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:
    codice:
        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:
    codice:
        if(*(vett+first)==elemento)
        {
            return parziale1+parziale2 +1;
        }
        else
        {
            return parziale1+parziale2 ;
        }
    e sostituirla con:
    codice:
          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:
    codice:
          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 ^^
    codice:
     $(".canaglia").show()

  4. #4
    Utente di HTML.it
    Registrato dal
    Oct 2011
    Messaggi
    156
    Grazie a tutti e due...illuminanti in modi diversi

  5. #5
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408
    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ì:

    codice:
    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:

    codice:
    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 ?

  6. #6
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    codice:
    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:

    codice:
    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;

  7. #7
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408
    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?

  8. #8
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    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.

  9. #9
    Utente di HTML.it L'avatar di goatboy
    Registrato dal
    Mar 2011
    residenza
    Salerno
    Messaggi
    408
    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!

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.