Znajdź maksymalną wartość w tablicy przez rekursję

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 

Trudno mi zrozumieć, co dzieje się w tym pseudokodzie.

Czy ktoś może pomóc wyjaśnić, co dzieje się w każdym wierszu. Muszę zrozumieć ten kod, zanim będę mógł odpowiedzieć na pytania.

Wiem, że funkcja findMax wywołuje funkcję pomocnika findMaxHelper, a następnie findMaxHelper używa rekursji. Poza tym, naprawdę tego nie rozumiem.

Answer 1

Używasz algorytmu Divide and Conquer do znajdowania maksymalnego elementu z tablicy. Najpierw dzielisz tablicę na poszczególne elementy (dzielenie), następnie porównujesz elementy (podbijaj). Dzielicie tablicę, używając rekursywnie wywołując findMaxHelper.

Ogólna idea dziel i rządź jest pokazany na rysunku:

Przykład:

Tutaj max jest taka sama jak twoja funkcja findMaxHelper z dwoma argumentami tj left i right.

Sprawdź przykład this, aby lepiej zrozumieć pojęcie.

Answer 2

findMaxHelper dzieli tablicę na pół każdym czasie i znaleźć max w lewo, w prawo:

np masz tablica A = [1, 3, 5, 8], zadzwonić findMax(A) ->findMaxHelper(A, 0, A.length):

 max1 | max2 
    1 3 | 5 8 

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

Answer 3

Jaguar wprowadził pojęcie całkiem ładnie i Paweł przedstawił poprawne i szczegółowe wyjaśnienie. Aby dodać do tego, chciałbym udostępnić prosty kod C, który daje pojęcie, jak kod zostanie wykonany wykonany. Oto kod z tego samego wejścia Jaguar używane:

#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 można skopiować wkleić kod ur maszynie linux ... Może położyć spać (5) Po każdym printf i zobaczyć, jak rekurencja faktycznie działa ...! Nadzieja to pomaga ... będę również dzielić wyjście z mojego systemu tutaj:

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

Zasadniczo znalezienie max w tablicy nie jest zalecane przez rekurencję, gdyż nie jest to wymagane. Algorytmy dzielenia i zdobywania (rekurencyjne) są bardziej kosztowne. Ale nawet jeśli chcesz go użyć, możesz użyć mojego poniższego algorytmu. Zasadniczo, to przynosi największy element tablicy na pierwszej pozycji i ma prawie liniowy czas pracy (to algo jest tylko rekurencyjne-iluzja jednak!).

 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; 
}