Trova il valore massimo in una matrice per ricorsione

Question

// Find a maximum element in the array. 
findMax(A) 
    findMaxHelper(A, 0, A.length) 

findMaxHelper(A, left, right) 
    if (left == right - 1) 
     return A[left] 
    else 
     max1 = findMaxHelper(A, left, (right + left)/2) 
     max2 = findMaxHelper(A, (right + left)/2, right) 

     if (max1 > max2) 
     return max1 
     else 
     return max2 

Ho difficoltà a capire cosa sta succedendo in questo pseudo-codice.

Qualcuno può aiutare a spiegare cosa sta succedendo in ogni riga. Devo capire questo codice prima di poter rispondere alle domande.

So che la funzione findMax chiama la funzione di supporto findMaxHelper, quindi findMaxHelper utilizza la ricorsione. Oltre a questo, davvero non lo capisco.

Answer 1

Si sta utilizzando l'algoritmo Divide and Conquer per trovare l'elemento massimo dall'array. Per prima cosa si divide l'array in elementi individuali (divide), quindi si confrontano gli elementi (conquista). Si sta dividendo l'array usando chiamando findMaxHelper in modo ricorsivo.

L'idea generale di divide et impera è mostrato in figura:

Esempio:

Qui max è stessa la funzione findMaxHelper con due argomenti cioè left e right.

Controllare l'esempio this per una comprensione più approfondita del concetto.

Answer 2

findMaxHelper divide l'array in mezzo ogni volta, e trovare il massimo di sinistra, a destra:

ad esempio, si hanno serie A = [1, 3, 5, 8], chiamano findMax(A) ->findMaxHelper(A, 0, A.length):

 max1 | max2 
    1 3 | 5 8 

max1|max2 | max1|max2 
1 |3 | 5 |8 

Answer 3

Jaguar ha messo il concetto abbastanza bene e Paul ha fornito una spiegazione corretta e dettagliata. Per aggiungere a questo, mi piacerebbe condividere un semplice codice C che ti dà un'idea di come il codice ottiene eseguito. Ecco il codice con lo stesso ingresso Jaguar usata:

#include<stdio.h> 
int findMaxHelper(int A[], int left, int right){ 
    int max1,max2; 
    int static tabcount; 
    int loop; 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    tabcount++; 
    printf(" Entering: findMaxHelper(A, left = %d ,right = %d)\n\n",left,right); 
    if (left == right - 1){ 
     for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
     printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning %d\n\n",left,right , A[left]); 
     tabcount--; 
     return A[left]; 
    } 
    else 
    { 
     max1 = findMaxHelper(A, left, (right + left)/2); 
     max2 = findMaxHelper(A, (right + left)/2, right); 

     if (max1 > max2){ 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d) | returning max1=%d\n\n",left,right,max1); 
    tabcount--; 
    return max1; 
    } 
     else { 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning max2=%d\n\n",left,right,max2); 
    tabcount--; 
    return max2; 
    } 

    } 
} 

int main(){ 
    int A[] = { 34,3,47,91,32,0 }; 
    int Ans =findMaxHelper(A,0,7); 
    printf("And The Answer Is = %d \n",Ans); 
} 

U può copiare incollare il codice ur macchina Linux ... Forse mettere sleep (5) dopo ogni printf e vedere come funziona realmente la ricorsione ...! Spero che questo aiuti ... voglio anche condividere l'uscita dal mio sistema qui:

Entering: findMaxHelper(A, left = 0 ,right = 7) 

    Entering: findMaxHelper(A, left = 0 ,right = 3) 

     Entering: findMaxHelper(A, left = 0 ,right = 1) 

     Leaving: findMaxHelper(A, left = 0 ,right = 1)| returning 34 

     Entering: findMaxHelper(A, left = 1 ,right = 3) 

      Entering: findMaxHelper(A, left = 1 ,right = 2) 

      Leaving: findMaxHelper(A, left = 1 ,right = 2)| returning 3 

      Entering: findMaxHelper(A, left = 2 ,right = 3) 

      Leaving: findMaxHelper(A, left = 2 ,right = 3)| returning 47 

     Leaving: findMaxHelper(A, left = 1 ,right = 3)| returning max2=47 

    Leaving: findMaxHelper(A, left = 0 ,right = 3)| returning max2=47 

    Entering: findMaxHelper(A, left = 3 ,right = 7) 

     Entering: findMaxHelper(A, left = 3 ,right = 5) 

      Entering: findMaxHelper(A, left = 3 ,right = 4) 

      Leaving: findMaxHelper(A, left = 3 ,right = 4)| returning 91 

      Entering: findMaxHelper(A, left = 4 ,right = 5) 

      Leaving: findMaxHelper(A, left = 4 ,right = 5)| returning 32 

     Leaving: findMaxHelper(A, left = 3 ,right = 5) | returning max1=91 

     Entering: findMaxHelper(A, left = 5 ,right = 7) 

      Entering: findMaxHelper(A, left = 5 ,right = 6) 

      Leaving: findMaxHelper(A, left = 5 ,right = 6)| returning 0 

      Entering: findMaxHelper(A, left = 6 ,right = 7) 

      Leaving: findMaxHelper(A, left = 6 ,right = 7)| returning 0 

     Leaving: findMaxHelper(A, left = 5 ,right = 7)| returning max2=0 

    Leaving: findMaxHelper(A, left = 3 ,right = 7) | returning max1=91 

Leaving: findMaxHelper(A, left = 0 ,right = 7)| returning max2=91 

And The Answer Is = 91 

Answer 4

Fondamentalmente trovare max di matrice non è raccomandato dalla ricorsione in quanto non è richiesto. Gli algoritmi di dividi e conquisti (ricorsivi) sono più costosi. Ma anche se si desidera utilizzarlo, è possibile utilizzare il mio algoritmo di seguito. Fondamentalmente, si porta il più grande elemento dell'array in prima posizione e ha tempo di esecuzione quasi lineare (Questo algo è solo un ricorsiva-illusione però!):.

 int getRecursiveMax(int arr[], int size){ 
      if(size==1){ 
         return arr[0]; 
      }else{ 
       if(arr[0]< arr[size-1]){ 
             arr[0]=arr[size-1]; 
        } 
       return(getRecursiveMax(arr,size-1)); 
      } 

      } 

Answer 5

#include<stdio.h> 
#include<stdlib.h> 

int high,*a,i=0,n,h; 
int max(int *); 

int main() 
{ 

    printf("Size of array: "); 
    scanf("%d",&n); 

    a=(int *)malloc(n*sizeof(int));   //dynamic allocation 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",(a+i)); 
    } 
     i=0; 
    high=*a; 
    h=max(a); 
    printf("The highest element is %d\n",h); 
} 

int max(int *a) 
{ 

    if(i<n) 
    { 
     if(*(a+i)>high) 
     {high=*(a+i);} 
    i++; 
    max(a);      //recursive call 
    } 

    return high; 
}