[C] - Elemento Minimo Ricorsivo

di
g@lil3o
il
21 risposte

21 Risposte - Pagina 2

  • g@lil3o
    g@lil3o
    Pochi posts
    Iscritto da
    nov, 2019
    Messaggi:
    43

    Re: [C] - Elemento Minimo Ricorsivo

    E' evidente che il problema non è il codice ma l'italiano, la traccia dice espressamente:
    Scrivete una funzione ricorsiva minimo_ricorsivo che riceva come argomenti un vettore di interi e la sua dimensione e restituisca l'elemento più piccolo del vettore.
    @migliorabile hai usato una funzione ricorsiva con tre argomenti 
    int rmin(int V[], int i, int min_found)
    già questo, indipendentemente dal fatto che sia o meno il miglior codice del mondo è sufficiente ad andare fuori traccia = esercizio sbagliato.

    Continuo a sottolineare che NON devo usare i puntatori...
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6034

    Re: [C] - Elemento Minimo Ricorsivo

    Mah!
  • g@lil3o
    g@lil3o
    Pochi posts
    Iscritto da
    nov, 2019
    Messaggi:
    43

    Re: [C] - Elemento Minimo Ricorsivo

    @g@lil3o, sei ""ziovine"", come tale ""pensi"" di saperne una piu' del diavolo
    se mai l'esatto contrario, sto affrontando ora l'argomento, utilizzando gli strumenti che mi fornisce il libro, quindi so cosa sia la ricorsione in generale e come dovrebbe funzionare ma non ho mai detto "conosco ogni aspetto della ricorsione e tutte le sue possibili tecniche implementative".
    Questione puntatore: const int V[] E' EQUIVALENTE a const int* V e questo e' il modo in C di passare i vettori PER REFERENCE.
    L'alternativa e' passare il vettore per VALORE, il che vuol dire che ad ogni chiamata ricorsiva tu vai a copiare sullo stack l'INTERO VETTORE.
    Non so se ne comprendi le conseguenze, ma, fondamentalmente, "non si fa, ne ora ne mai"
    Si, so che i vettori (per intero) in C sono passati per riferimento mentre i suoi singoli elementi per valore e la conseguenza di passare un vettore per valore significa che ad esempio per vettori di grandi dimensioni, copiare sullo stack l'intero vettore ad ogni chiamata richiederebbe molto tempo e un suicidio in termini di memoria.

    Detto questo, non appena avrò più padronanza dell'argomento e affrontato i puntatori, guarderò volentieri il tuo codice che sicuramente ha dietro molta esperienza. Come ho detto c'è sempre da imparare dagli altri, grazie del contributo.
  • Rubik
    Rubik
    Utente Attivo
    Iscritto da
    ago, 2020
    Messaggi:
    440

    Re: [C] - Elemento Minimo Ricorsivo

    migliorabile ha scritto:

    @g@lil3o, sei ""ziovine"", come tale ""pensi"" di saperne una piu' del diavolo

    No ti piace con 3 parametri?
    Ok
    
#include<stdio.h>
#include<stdlib.h>

const int N = 80;
int V[N];

int rmin(const int V[], int i) {
    if (i < 0)
        return __INT_MAX__;
    else if (i == 0)
        return V[0];
    int fmin = rmin(V, i-1);
    if (fmin < V[i])
        return fmin;
    else
        return V[i];
}


int main(int argc, char** argv) {

    // Inizializzazione del generatore di numeri casuali
    // 'argv' ha un indirizzo sempre diverso
    // idea: usare l'indirizzo come un long da usare con srand()

    union {
        void* ptr;
        long ival;
    } init;
    init.ptr = argv;

    printf("init srand: %ld\n", init.ival);
    srand(init.ival);

    // inizializzazione di min con il PIU' ALTO valore per un intero
    int min = __INT_MAX__;

    // inizializzazione del vettore e identificazione del valore minimo
    for(int i=0;i<N; ++i) {
        V[i] = 1 + rand() % 1000;
        if (V[i] < min)
            min = V[i];
    }

    printf("  real min: %d\n", min);

    // 'rmin' minimo cercato in modo ricorsivo

    int min_found = rmin(V, N-1);

    // minimo trovato
    printf(" min found: %d\n", min_found);

   return 0;
}
    I due codici sono ""QUASI"" ESATTAMENTE equivalenti.

    Quel ""QUASI"" fa una differenza ENORME.

    RAGIONA, se ti va, nel CAPIRE a che cosa server il TERZO parametro, e nella funzione a DUE parametri CHE COSA e' cambiato.

    Suppongo tu non sappia che cosa sia la tail recursion.

    https://en.wikipedia.org/wiki/Tail_cal

    La precedente implementazione ne fa uso, e questo ha TUTTA una serie di conseguenze interessanti.

    La versione a DUE parametri NO, con TUTTA UN'ALTRA serie di conseguenze ""imbarazzanti""

    Questione puntatore: const int V[] E' EQUIVALENTE a const int* V e questo e' il modo in C di passare i vettori PER REFERENCE.
    L'alternativa e' passare il vettore per VALORE, il che vuol dire che ad ogni chiamata ricorsiva tu vai a copiare sullo stack l'INTERO VETTORE.

    Non so se ne comprendi le conseguenze, ma, fondamentalmente, "non si fa, ne ora ne mai"
    L'ho letto tutto d'un fiato, grazie per gli utili chiarimenti.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: [C] - Elemento Minimo Ricorsivo

    @migliorabile dal primo codice che hai postato mi sembra di capire che con

    migliorabile ha scritto:

    2) la soluzione non segue la filisofia di una funzione ricorsiva: quel 'temp' scritto in quel modo "non s' ha da usare ne ora ne mai"
    ti riferissi al fatto che disconosci ogni forma di ricorsione che non sia quella in coda!

    Che la tail recursion consenta un minor consumo di risorse (sempre che il compilatore supporti tale ottimizzazione) è fuori discussione, ma mi sembra che anche tu sia stato costretto ad usare una variabile "temporanea" ed una ricorsione non in coda volendo seguire la traccia ed utilizzando quindi solo due parametri!

    Inoltre mi spieghi a cosa serve utilizzare __INT_MAX__?
    - nella versione a due parametri è completamente inutile, in quanto la condizione 
    if (i < 0) return __INT_MAX__;
    non può mai verificarsi. Tolta questa parte la funzione diventa identica a quella postata da @g@lil3o, che inoltre ha anche evitato di mettere quell'inutile else finale;
    - nella versione a tre parametri la funzione ricorsiva può essere tranquillamente richiamata con 
    rmin(V, N-2, V[N-1]);

    migliorabile ha scritto:

    Questione puntatore: const int V[] E' EQUIVALENTE a const int* V e questo e' il modo in C di passare i vettori PER REFERENCE.
    L'alternativa e' passare il vettore per VALORE, il che vuol dire che ad ogni chiamata ricorsiva tu vai a copiare sullo stack l'INTERO VETTORE.
    Questa mi è nuova... come si fa a passare un array per valore?!
    In ogni caso volendo essere precisi va detto che in C esiste solo il passaggio per valore e che quello per riferimento viene simulato passando alla funzione l'indirizzo di memoria di una variabile attraverso un parametro di tipo puntatore, dereferenziando il quale è poi possibile leggere o scrivere la variabile effettiva. Questo pseudo passaggio per riferimento è quello che accade di default con gli array, in quanto il loro identificatore, tranne pochi casi particolari, decade sempre a puntatore al primo elemento.

    P.S.
    Quest'uso smodato di iperboli, virgolette, maiuscolo, non-detti ed emoticon risulta un po' macchiettistico!
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1241

    Re: [C] - Elemento Minimo Ricorsivo

    Noto che @migliorabile si è autocensurato!
  • Rubik
    Rubik
    Utente Attivo
    Iscritto da
    ago, 2020
    Messaggi:
    440

    Re: [C] - Elemento Minimo Ricorsivo

    Nippolo ha scritto:

    Noto che @migliorabile si è autocensurato!
    Si, ma comunque questa discussione è molto utile.
Devi accedere o registrarti per scrivere nel forum
21 risposte