[C] - Elemento Minimo Ricorsivo

di il
21 risposte

[C] - Elemento Minimo Ricorsivo

Salve a tutti, vorrei un parere sul seguente esercizio:

ES: (Trovare il valore minimo in un vettore) 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. La funzione dovrà terminare la propria elaborazione e restituire il controllo a quella chiamante, quando avrà ricevuto un vettore che contenga un solo elemento.

Io l'ho svolto così:
#include <stdio.h>
#define DIM 10

int minimo_ricorsivo(int vett[], int i);

int main()
{
	int vettore[DIM] = {7, 1, 10, 2, 15, 4, 9, 20, 13, 6};
    
	printf("\nil minimo del vettore e' : %d\n\n", minimo_ricorsivo(vettore, DIM));
	return 0;
}

int minimo_ricorsivo(int vett[], int i)
{
    if(i == 0)
	return vett[i];
    if(vett[i - 1] < vett[i - 2])
    {
	vett[i - 2] = vett[i - 1];
    }
    return minimo_ricorsivo(vett, i - 1);
}
Il codice dovrebbe essere corretto e funziona, avete qualche consiglio per migliorarlo o va bene così?

Grazie

21 Risposte

  • Re: [C] - Elemento Minimo Ricorsivo

    RIVEDI tutto il ragionamento, perche' quello che hai scritto non e' ragionevole.

    0) in qualche modo popoli il vettore con dei numeri A CASO. Come si fa questo, vabbe' te lo devi scoprire da solo.
    L'unica cosa che potresti decidere di volta in volta e' il NUMERO DI ELEMENTI/lunghezza del vettore, NON il suo contenuto.

    Una volta che il vettore e' stato preparato, devi tenere traccia di QUATTRO informazioni:

    a.1) il puntatore al VETTORE, se vuoi, al PRIMO elemento del vettore
    a.2) la lunghezza TOTALE del vettore
    a.3) l'indice CURRENTE dell'elemento del vettore che vuoi considerare
    a.4) il valore MINIMO ritrivato fino a quel momento

    1) il vettore VA SSOOLLOO LETTO, AASSOOLLUUTTAAMMEENNTTEE NON MODIFICATO!!!!!!!!

    2) DEVI tenere in considerazione i seguenti casi

    2.1) puntatore NULL al vettore. Questo dovrebbe essere un ERRORE e quindi segnalato come tale
    2.1) vettore DI LUNGHEZZA ZERO. Un vettore di lunghezza ZERO E' un vettore valido!!!
    2.2) vettore di lunghezza UNO. E' un vettore cortino, ma ancora valido
    2.3) vettore di lunghezza 2 o PIU' elementi
    2.4) vettore di 10, 100, 1000, 10_000, 100_000, 1_000_000 elementi, giusto per vedere che effetto che fa, ed i tempi di esecuzione
  • Re: [C] - Elemento Minimo Ricorsivo

    Funziona però ti modifica il vettore.

    Edit:
    @migliorabile giuste molte cose che hai detto, ma non vedo modi per ammortizzare il tempo di ricerca del minimo in un vettore non ordinato.
  • Re: [C] - Elemento Minimo Ricorsivo

    migliorabile ha scritto:


    In parole semplici:


    ""MA SEI PAZZO!!!!!""""



    RIVEDI tutto il ragionamento, perche' quello che hai scritto NON HA MINIMAMENTE SENSO.

    Il fatto che per te funzioni NON E' ASSOLUTAMENTE SIGNIFICATIVO, perche' ci sono altri N-MILA casi in cui non funziona di sicuro!

    Quindi, ricomincia nel seguente modo:

    0) in qualche modo popoli il vettore con dei numeri A CASO. Come si fa questo, vabbe' te lo devi scoprire da solo.
    Quello che hai usato e' un modo, MA dovresti farlo PIU' GENERALE.
    L'unica cosa che potresti decidere di volta in volta e' il NUMERO DI ELEMENTI/lunghezza del vettore, NON il suo contenuto.

    Una volta che il vettore e' stato preparato, devi tenere traccia di QUATTRO informazioni:

    a.1) il puntatore al VETTORE, se vuoi, al PRIMO elemento del vettore
    a.2) la lunghezza TOTALE del vettore
    a.3) l'indice CURRENTE dell'elemento del vettore che vuoi considerare
    a.4) il valore MINIMO ritrivato fino a quel momento

    1) il vettore VA SSOOLLOO LETTO, AASSOOLLUUTTAAMMEENNTTEE NON MODIFICATO!!!!!!!!

    2) DEVI tenere in considerazione i seguenti casi

    2.1) puntatore NULL al vettore. Questo dovrebbe essere un ERRORE e quindi segnalato come tale
    2.1) vettore DI LUNGHEZZA ZERO. Un vettore di lunghezza ZERO E' un vettore valido!!!
    2.2) vettore di lunghezza UNO. E' un vettore cortino, ma ancora valido
    2.3) vettore di lunghezza 2 o PIU' elementi
    2.4) vettore di 10, 100, 1000, 10_000, 100_000, 1_000_000 elementi, giusto per vedere che effetto che fa, ed i tempi di esecuzione
    Ok posso popolarlo in modo casuale ogni volta che lo eseguo (so come farlo) il problema è che questo esercizio si trova in un capitolo antecedente i puntatori, argomento che tra l'altro non ho ancora affrontato quindi devo (secondo l'odine del libro) svolgerlo senza l'utilizzo di questi.
  • Re: [C] - Elemento Minimo Ricorsivo

    Ho provato a risolverlo senza modificare il vettore, generando i suoi elementi in modo casuale in un range da 1 a 100 :
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define DIM 20
    
    int minimo_ricorsivo(const int vett[], int i);
    
    int main()
    {
        int vettore[DIM], y;
        
        srand(time(NULL));
        printf("\nVETTORE CASUALE : ");
    
        for(y = 0; y < DIM; y++)
        {
        	vettore[y] =  1 + rand() % 100;
        	printf("%d ", vettore[y]);
        }
    	printf("\n\nil minimo del vettore e' : %d\n\n", minimo_ricorsivo(vettore, DIM));
    	return 0;
    }
    
    int minimo_ricorsivo(const int vett[], int i)
    {
        int min;
        if(i == 0)
            return vett[i];
        min = minimo_ricorsivo(vett, i - 1);
        if(min < vett[i - 1])
        {
            return min;
        }
        return vett[i - 1];
    }
    Senza l'utilizzo dei puntatori potrebbe andare come soluzione?
  • Re: [C] - Elemento Minimo Ricorsivo

    Nella funzione ricorsiva devi sostituire i due
    vett[i - 1]
    con
    vett[i]
    altrimenti se il minimo si trova in ultima posizione non te lo rileva.

    Poi volendo essere più concisi:
    #include <stdio.h>
    
    #define N 5
    
    int minimo_ricorsivo(int v[], unsigned int i)
    {
        int temp;
        return(!i || v[i] < (temp = minimo_ricorsivo(v, i - 1)) ? v[i] : temp);
    }
    
    int main()
    {
        int v[N] = {1, 5, 3, 0, 8};
        printf("MINIMO = %d\n", minimo_ricorsivo(v, N - 1));
        return 0;
    }
  • Re: [C] - Elemento Minimo Ricorsivo

    Nippolo sempre efficientissimo
  • Re: [C] - Elemento Minimo Ricorsivo

    Grazie nippolo, ho modificato il mio codice con il tuo suggerimento e ho eliminato la generazione casuale per renderlo più conciso, ecco qua:
    #include <stdio.h>
    #define DIM 10
    
    int minimo_ricorsivo(const int vett[], int i);
    
    int main()
    {
    	int vettore[DIM] = {2, 13, 16, 1, 8, 11, 6, 17, 15, 18};
    	printf("\nMINIMO DEL VETTORE : %d\n\n", minimo_ricorsivo(vettore, DIM - 1));
    	return 0;
    }
    
    int minimo_ricorsivo(const int vett[], int i)
    {
    	int min;
    	if(i == 0) 
    		return vett[i];
    	min = minimo_ricorsivo(vett, i - 1);
            if(min < vett[i])
    		return min;
    	return vett[i]; 
    }
    ps: purtroppo non ho ancora l'esperienza necessaria a scrivere codice in modo così conciso
    return(!i || v[i] < (temp = minimo_ricorsivo(v, i - 1)) ? v[i] : temp);
  • Re: [C] - Elemento Minimo Ricorsivo

    g@lil3o ha scritto:


    ps: purtroppo non ho ancora l'esperienza necessaria a scrivere codice in modo così conciso
    return(!i || v[i] < (temp = minimo_ricorsivo(v, i - 1)) ? v[i] : temp);
    Gli operatori ternari la prima volta fanno questo effetto, ma poi ti rendi conto che non sono difficili, anzi semplificano:

    https://riptutorial.com/it/c/example/2158/operatore-condizionale---operatore-ternario
    https://www.yocker.com/1687
  • Re: [C] - Elemento Minimo Ricorsivo

    @nippolo, ti "contesto" la soluzione proposta.

    1) hai fornito la soluzione "non s' ha da fare ne ora ne mai" (di Manzoniana memoria )
    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"
    3) la sintassi strampalata del C per chi non sa programmare (operatore ? : e quel. !i) "non s' ha da usare ne ora ne mai"

    Per il resto, hai fatto contento l'autore che comunque dubito abbia capito il concetto di 'funzione ricorsiva'
  • Re: [C] - Elemento Minimo Ricorsivo

    @galil3o: il codice "conciso" non serve a NULLA.
    Il compilatore sa fare molto meglio.

    Tu CONCENTRATI a scrivere codice CHIARO E PULITO.
  • Re: [C] - Elemento Minimo Ricorsivo

    @migliorabile

    migliorabile ha scritto:


    @nippolo, ti "contesto" la soluzione proposta.

    1) hai fornito la soluzione "non s' ha da fare ne ora ne mai" (di Manzoniana memoria )
    mi sembra che g@lil3o, ha raccolto e fatto suo l'esempio e sicuramente ha migliorato la comprensione del C per principianti

    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"
    Questa affermazione senza postare una soluzione o una correzione costruttiva è inutile, e induce a pensare che stai scrivendo con astio.

    migliorabile ha scritto:


    3) la sintassi strampalata del C per chi non sa programmare (operatore ? : e quel. !i) "non s' ha da usare ne ora ne mai"

    Per il resto, hai fatto contento l'autore che comunque dubito abbia capito il concetto di 'funzione ricorsiva'
    Io sono alle prime armi, g@lil3o ancora meno, nippolo sembra che ne sappia più di me ma meno di te, noi "scarsi" ci diamo una mano a vicenda, se gli esperti ci correggono dicendoci cosa non va ma allo stesso tempo come si fa, siamo felicissimi, se ci insultano li mandiamo a quel paese.

    Questo per dire che mi piacerebbe molto ma veramente molto il tuo fattivo aiuto nel forum, perché devi considerare che i post sono letti da molte ma molte più persone rispetto a quelle che li scrivono, risposte non criptiche con rimandi anche concettuali sarebbero di aiuto per chi legge, mentre i post come il tuo e questo mio sono inutili.
    Pensiero chiuso qui, non risponderò ulteriormente.
  • Re: [C] - Elemento Minimo Ricorsivo

    migliorabile ha scritto:


    @nippolo, ti "contesto" la soluzione proposta.

    1) hai fornito la soluzione "non s' ha da fare ne ora ne mai" (di Manzoniana memoria )
    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"
    3) la sintassi strampalata del C per chi non sa programmare (operatore ? : e quel. !i) "non s' ha da usare ne ora ne mai"

    Per il resto, hai fatto contento l'autore che comunque dubito abbia capito il concetto di 'funzione ricorsiva'
    1) non ho mai chiesto la soluzione
    2) la mia soluzione da come leggo andava bene togliendo i "-1" dalla funzione ricorsiva (e ho capito il perchè)
    3) ho ben chiaro il concetto di ricorsione ma non sempre si arriva alla soluzione giusta, efficiente e corretta al primo colpo, anzi spesso sono proprio gli errori che ti fanno imparare, a maggior ragione per chi come me è nuovo nel campo.

    Ho modificato la mia prima soluzione (sbagliata) con quella attuale, rispettando la non modifica del vettore ed evitando l'uso dei puntatori che NON dovevo usare.

    @migliorabile tu dici che nippolo mi ha fornito la soluzione quando in realtà mi ha semplicemente suggerito una modifica a qualcosa che avevo già scritto. E ci tengo a precisare che non ho un esame imminente o consegne di progetti ecc ecc, sto imparando a programmare e sto cercando di farlo bene il che è ben diverso da non sbagliare mai, se non fosse così non vedo perchè dovrei chiedere consigli su un forum.

    PS: uso l'indentazione e scrivo il codice esplicitando tutto (senza usare forme concise) se neanche così va bene sinceramente non capisco cosa intendi per chiaro e pulito
  • Re: [C] - Elemento Minimo Ricorsivo

    migliorabile ha scritto:


    1) hai fornito la soluzione "non s' ha da fare ne ora ne mai" (di Manzoniana memoria )
    Se leggi bene il mio precedente intervento mi sono prima limitato a dirgli cosa non andasse nel suo codice e come correggerlo... e in ogni caso non penso che quello che ho postato possa essere interpretato come fornire la soluzione!

    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"
    Non ho capito, è sbagliata la funzione che ho scritto? E se sì, perché?
    Tu come l'avresti impostata la ricorsione?
  • Re: [C] - Elemento Minimo Ricorsivo

    Boh!
Devi accedere o registrarti per scrivere nel forum
21 risposte