再帰によって配列の最大値を見つける

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 

この疑似コードで何が起こっているのか分かりにくいです。

各行で何が起こっているか説明できる人がいます。質問に答える前にこのコードを理解する必要があります。

私は関数findMaxがヘルパー関数findMaxHelperを呼び出し、findMaxHelperが再帰を使用することを知っています。それ以外は、私は本当にそれを理解していない。

Answer 1

Divide and Conquerアルゴリズムを使用して、配列から最大要素を検索しています。まず、配列を個々の要素に分割し（除算）、要素を比較します（征服）。再帰的にfindMaxHelperを呼び出して配列を分割しています。

分割統治の一般的な考え方を図に示します。

例：

ここmaxは二つの引数を使用してfindMaxHelper関数と同じですleft IEとright。

thisの例をチェックして、概念の深い理解を深めてください。

Answer 2

findMaxHelperが半分のたびに配列を分割し、左に最大を見つけ、右：

例えばあなたが、配列A = [1, 3, 5, 8]を持って、findMax(A)呼び出し - >findMaxHelper(A, 0, A.length)を：

 max1 | max2 
    1 3 | 5 8 

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

Answer 3

ジャガーは概念を入れています非常にきれいで、Paulは正確かつ詳細な説明を提供しています。 これに追加するには、コードがどのように が実行されるのかを示す簡単なCコードを共有したいと思います。ここでジャガーを使用したのと同じ入力を持つコードは次のとおりです。

#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はウルLinuxマシン上のコードをコピー＆ペーストすることができます...多分すべてのprintfの 後（5）睡眠を入れて、再帰が実際にどのように動作するかを見ます...！ 希望これは私もここに私のシステムからの出力を共有する ...助け：

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

基本的にはそれが必要とされていないとして、アレイ内の最大値は、再帰によって推奨されていません見つけます。 分割アルゴリズムと征服アルゴリズム（再帰的）は、時間がかかります。 しかし、あなたがそれを使いたいのであれば、私の下のアルゴリズムを使うことができます。基本的には、第1の位置に配列の最大要素をもたらし、ほぼ直線走行時間を持っている（このアルゴはしかしちょうど再帰錯覚です！）：。

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