[C]minimo in un vettore

[domenico88]

Ciao a tutti...
Allora ho un problemino con un esempio sulla ricorsione....

In pratica dovrei trovare il minimo nel vettore ricorsivamente, considerando l'elemento che occupa la prima posizione e i restanti elementi quindi first +1 - last.
Il funzionamento non lo riesco proprio a capire

Perdonatemi ma sono alle prime armi con la programmazione, soprattutto con la tecnica del divide et impera.....

Vi posto il codice della funzione

 

int min_search_rec( int v[], int first, int last)
{ 
 int ris;
 
 /*Caso base */

 if ( first == last)
  return (first);

 /*Divide et impera*/
 
 ris = min_search_rec( v, first +1, last);

 /*Combina */
 
 if ( v[ris] < v[first] )
   return ris;
 else 
   return first;
}

Grazie anticipatamente a tutti!

[clockover]

Guarda fai così...
--caso base --> se indice == ultimo indice ritorni il minimo
--passo 1--> se elemento corrente minore di minimo allora minimo elemento corrente
--passo 2 --> passo ricorsivo richiami la funzione incrmentando l'indice e passando come parametro il nuovo minimo

dopo un po che ci hai ragionato su ti posto la soluzione ma non ora ovviamente

[cionci]

Non ho capito cosa intendi per first e last. Mi immagino che sia l'intervallo di posizioni su cui andare a calcolare il minimo.

Condizione di arresto: va bene quella che hai scritto, però è errato il valore che ritorni. Non ha senso, anche nel resto della funzione, ritornare indietro indice e valori, o ritorni l'uno o ritorni l'altro. In questo caso deve sempre ritornare un valore del vettore.
Passo generico: se il valore corrente è minore di quello ritornato dal passo ricorsivo allora ritorni il valore corrente, altrimenti ritorni il valore del ritornato dal passo ricorsivo

[cionci]

Inoltre di pende anche da come ti hanno insegnato il divide et impera. In teoria va bene anche solo incrementare first, ma molti per divide et impera intendono la suddivisione in due sottoinsiemi di dimensione simile dell'intervallo di azione della funzione ricorsiva.
Quindi dovresti suddividere a metà l'intervallo di ricerca e richiamare due volte la funzione ricorsiva. In questo caso il passo generico sarebbe:

divido l'intervallo first - last a metà, ne passo metà ad una funzione ricorsiva e una metà ad un'altra. Confronto il valore ritornato delle funzioni e ritorno il valore minore.

[domenico88]

Grazie a tutti per le risp.....
Cmq raga quella funzione non l'ho scritta io, cioè l'ha scritta il mio prof sul mio libro di Asd.....

Ho capito poco e niente....scusate ma quando

ris = min_search(v, first +1, last); Cosa succede???

Non ho capito proprio come lavora la funzione

X clockover.....ci sto ragionando sarebbe una soluzione alternativa a quella del mio prof ma con una chiamata ricorsiva in coda giusto???

[clockover]

Allora quel codice che hai postato non funziona!
La chiamata ricorsiva che chiedi tu non fa altro che far avanzare l'indice first fino al caso base..

Comunque lascialo stare quello!
Fallo tu dal principio! Fattelo in due funzioni

1)

int minimo(int a[], int dimensione_vettore){
    int index = 0;
    int min = a[index];
    return minimo2(a, min, index, dimensione_vettore);
}

2)

int minimo2(.......){ fallo tu }

segui la traccia in linguaggio naturale che ti ho scritto nel primo post e cerca di capire che robaccia che fa

P.S.
ricorda che devi conoscere la dimensione del vettore

[domenico88]

Originariamente inviato da clockover

Allora quel codice che hai postato non funziona!
La chiamata ricorsiva che chiedi tu non fa altro che far avanzare l'indice first fino al caso base..

Comunque lascialo stare quello!
Fallo tu dal principio! Fattelo in due funzioni

1)

int minimo(int a[], int dimensione_vettore){
    int index = 0;
    int min = a[index];
    return minimo2(a, min, index, dimensione_vettore);
}

2)

int minimo2(.......){ fallo tu }

segui la traccia in linguaggio naturale che ti ho scritto nel primo post e cerca di capire che robaccia che fa

P.S.
ricorda che devi conoscere la dimensione del vettore

Graze clock.......ci provo.....

[cionci]

Avevo letto male la funzione, quella funzione va perfettamente. Mi sembrava che ritornasse l'elemento del vettore, invece ritornava l'indice del valore minimo.

La chiamata di quella funzione dovrà essere:

min_index = min_search_rec(v, 0, size-1);

Ti permette di trovare il minimo inserendo qualsiasi intervallo, ad esempio:

min_index = min_search_rec(v, size-1, size-1);

Entrerai nella condizione di arresto e ti ritornerà l'indice dell'ultimo elemento del vettore. Questo è normale perché l'indice dell'elemento di minimo valore è sicuramente quello visto che è l'unico elemento valutato nell'intervallo.

Quindi pensa di chiamarlo così:

min_index = min_search_rec(v, size-2, size-1);

Verrà valutato il minimo fra gli ultimi due elementi del vettore:
- la condizione di arresto è falsa, quindi viene valutata la ricorsione che, come sopra, ritorna l'ultimo elemento del vettore
- a questo punto viene fatto il confronto fra l'ultimo elemento del vettore ed il penultimo, viene ritornato l'indice dell'elemento minore

Ora con:

min_index = min_search_rec(v, size-3, size-1);

Anche questa segue lo stesso ragionamento e ritorna l'indice dell'elemento minore fra gli ultime tre, andando a valutare l'elemento da ritornare fra gli indici dell'elemento size-3 e l'indice dell'elemento ritornato dalla chiamata ricorsiva.

[cionci]

Originariamente inviato da clockover

int minimo(int a[], int dimensione_vettore){
    int index = 0;
    int min = a[index];
    return minimo2(a, min, index, dimensione_vettore);
}

Non è necessario passare il minimo e nemmeno l'indice volendo, vedi questa:

int indice_valore_minimo(int v[], int dim)
{
   int res;
   if(dim == 1)
      return 0;

   res = indice_valore_minimo(v, dim - 1);
   if(v[res] < v[dim - 1])
      return res;

   return dim -1;
}

[domenico88]

Sto confondendo un pò le idee .....

[cionci]

Originariamente inviato da domenico88

Sto confondendo un pò le idee .....

La funzione va, basta che tu la provi o che tu segua il mio ragionamento con dei valori.
La cosa che almeno a me ha confuso è che non ritorna il minimo, ma l'indice del vettore che contiene il valore minimo.

[clockover]

Originariamente inviato da cionci

La cosa che almeno a me ha confuso è che non ritorna il minimo, ma l'indice del vettore che contiene il valore minimo.

Infatti.. comunque io l'ho fatto in questo modo

int min(int a[], int size){
        int index = 0;
        int minimo = a[index];
        return min2(a, minimo, index+1, size);
}
int min2(int a[], int minimo, int i, int size){
        if(i == size)return minimo;
        if(a[i] < minimo)minimo = a[i];
        return min2(a, minimo, i+1, size);
}

poi ovviamente... se hai bisogno della posizione nel vettore è meglio usare quell'altro che hai postato, altrimenti se hai bisogno semplicemente del valore va bene anche il mio!

aivoglia in quanti modi si può fare

[domenico88]

grazie ragazzi siete stati davvero gentilissimi....

[cionci]

Originariamente inviato da domenico88

grazie ragazzi siete stati davvero gentilissimi....

Ma hai almeno capito come funziona quello del professore ?

[domenico88]

Originariamente inviato da cionci

Ma hai almeno capito come funziona quello del professore ?

Hai colpito in pieno..... non ho capito ancora come funziona!

non riesco a capire i passi che compie la funzione sull'array!

[cionci]

Originariamente inviato da domenico88

Hai colpito in pieno..... non ho capito ancora come funziona!

non riesco a capire i passi che compie la funzione sull'array!

Hai letto il mio ragionamento ? Cosa non ti torna, commentalo passo per passo.

[domenico88]

Originariamente inviato da cionci

Hai letto il mio ragionamento ? Cosa non ti torna, commentalo passo per passo.

allora

Il caso base:

if( first == ultimo)
return first;

ok qui il caso base controlla che il vettore abbia esaurito gli elementi da controllare....in caso positivo ritorna il primo indice
Correggimi se sbaglio....


ris = min_search_ris(v, first +1, last);

Qua è il problema.....allora viene invocata la funzione con first che avanza di un elemento...ma cosa assegna la funzione a "ris"????

[cionci]

E' spiegato nel mio messaggio sopra cosa ritrna ed in quale caso. Devi fare un ragionamento per induzione, altrimenti non ne esci.
Quota il mio messaggio, commenta ogni mio ragionamento e dimmi cosa non ti torna.

[domenico88]

non so veramente come fare per capire sta ricorsione

ma devo fare un ragionamento all'inverso?

ris = min_search(v, first +1, last);

dopo questa chiamata sul vettore cosa succede...sul libro c'è scritto che viene diviso considerando separatamente l'elemento che occupa la prima posizione (v[first] ) e il vettore v[first + 1....last] costituito dai rimanenti elementi....

l'ho riletto e strariletto il tuo ragionamento ma non riesco a capire!

[clockover]

Prova fare una cosa: prendi un foglio di carta e creati, sempre sulla carta un array con 3 o 4 elementi massimo! Ti separi anche il foglio in 3 o 4 parti! Segui il codice su carta! Il tuo algoritmo parte e cominci a scrivere in uno spazio! Quando arrivi alla chiamata ricorsiva semplicemente cambi spazio e ricominci! Così via fino alla fine!