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

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

配列から最大要素を見つけるために分割統治アルゴリズムを使用しています。まず、配列を個々の要素に分割し (分割)、次に要素を比較します (征服)。findMaxHelper再帰呼び出しを使用して配列を分割しています。

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

例：

これは、と の 2 つの引数を持つ関数と同じmaxです。findMaxHelperleftright

概念をより深く理解するには、この例を確認してください。

Answer 2

Jaguar はコンセプトを非常にうまく表現しており、Paul は正確で詳細な説明を提供してくれました。これに追加するために、コードがどのように実行されるかを示す簡単な C コードを共有したいと思います。Jaguar が使用したのと同じ入力を使用したコードを次に示します。

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

Linuxマシンにコードをコピーして貼り付けることができます...おそらく、すべてのprintfの後にsleep(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 3

findMaxHelper毎回配列を半分に分割し、左、右の最大値を見つけます。

たとえば、 array A = [1, 3, 5, 8]、 call findMax(A)->がありfindMaxHelper(A, 0, A.length)ます:

     max1 | max2
     1 3  | 5 8

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

Answer 4

基本的に、配列内で max を見つけることは、必要ないため、再帰では推奨されません。分割統治アルゴリズム (再帰的) は、より時間がかかります。ただし、使用したい場合でも、以下のアルゴリズムを使用できます。基本的に、配列の最大要素を最初の位置に配置し、実行時間はほぼ線形です (ただし、このアルゴは単なる再帰的な錯覚です!):

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

          }