[C]Ricorsione

[ilario991]

Salve a tutti. Devo fare un programma in C che trova il massimo tra i valori in un array in modo ricorsivo.Ci sto su da un'ora, ma nn ne vengo fuori, sapete come fare?

[marx1]

Devi usare il divide et impera. Praticamente dividi il tuo array a metà e per ogni metà ti calcoli il max chiamandolo ricorsivamente fino ad ottenere un array di due elementi di cui è ovvio trovare il max alla fine il max totale sarà quello ottenuto confrontando il max delle due metà.

[ilario991]

Ho, cpt. Ma materialmente non riesco a mettere su il programma. Potresti aiutarmi? Io programmo in C, cioè passo ad una funzione max il vettore e la dimensione e poi divido il dim finchè non è uguale a 2???????

[marx1]

si esatto la base della ricorsione sarà se la dim del vettore è uguale a 2 il max sarà il massimo tra i due elementi altrimenti richiami la funzione sulla prima metà e sulla seconda metà memorizzando i max parziali in due variabili ausiliarie M1 e M2 alla fine scegli come massimo il massimo tra i due

[ilario991]

Alla fine ho fatto un programma che usa una base diversa, non so se sia ottimale, ma funzia lo stesso:

#include <stdio.h>
#include <conio.h>

int main(){
     int vettore[10]={1,3,6,9,8,5,0,14,12,36};
     printf("MAX: %d",max(vettore,0,9));
     getch();
}

int max(int *vett,int inf,int sup){
     int centro=0,m1,m2;
     if(inf==sup) return vett[inf];
     centro=(inf+sup)/2;
     m1=max(vett,inf,centro);
     m2=max(vett,centro+1,sup);
     if(m1>m2) return m1;
     return m2;
}

[apatriarca]

Puoi usare i puntatori invece che gli indici per determinare la partenza dell'array:

#include <assert.h>
#include <stdio.h>

int max(int *array, unsigned size) 
{
    assert(0 != size);

    if (1 == size) {
        return *array;
    } else {
        int pivot = size/2;
        int m1 = max(array, pivot);
        int m2 = max(array + pivot, size - pivot)
        
        if (m1 < m2) {
            return m2;
        } else {
            return m1;
        }
    }
}

int main()
{
    int array[10] = {1, 3, 6, 9, 8, 5, 0, 14, 12, 36};
    
    printf("MAX: %d\n\n", max(array, 10));    

    return 0;
}