रिकर्सन

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 

द्वारा किसी सरणी में अधिकतम मान पाएं मुझे इस छद्म कोड में क्या हो रहा है यह समझने में कठिनाई हो रही है।

कोई भी प्रत्येक पंक्ति में क्या हो रहा है यह समझाने में सहायता कर सकता है। इससे पहले कि मैं सवालों का जवाब दे सकूं, मुझे इस कोड को समझने की जरूरत है।

मुझे पता है कि फ़ंक्शन ढूंढें मैक्स हेल्पर फ़ंक्शन को मैक्सहेल्पर ढूंढता है, फिर ढूंढें मैक्सहेल्पर रिकर्सन का उपयोग करता है। इसके अलावा, मैं वास्तव में इसे समझ में नहीं आता।

Answer 1

आप सरणी से अधिकतम तत्व खोजने के लिए Divide and Conquer एल्गोरिदम का उपयोग कर रहे हैं। सबसे पहले आप सरणी को अलग-अलग तत्वों (विभाजन) में विभाजित कर रहे हैं, तो आप तत्वों (विजय) की तुलना कर रहे हैं। आप findMaxHelper को दोबारा कॉल करके सरणी को विभाजित कर रहे हैं।

फूट डालो और जीत के सामान्य विचार चित्र में दिखाया गया है:

उदाहरण:

यहाँ max ही है दो तर्क के साथ अपने findMaxHelper समारोह यानी के रूप में left और 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

जगुआर अवधारणा डाल दिया काफी अच्छी तरह से और पॉल ने सही और विस्तृत स्पष्टीकरण प्रदान किया है। इसमें जोड़ने के लिए, मैं एक साधारण सी कोड साझा करना चाहता हूं जो आपको एक विचार देता है कि कोड निष्पादित कैसे होता है। यहाँ एक ही इनपुट जगुआर इस्तेमाल किया साथ कोड है:

#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 के बाद नींद (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

मूल रूप से खोजने सरणी में अधिकतम प्रत्यावर्तन द्वारा अनुशंसित नहीं है के रूप में यह आवश्यक नहीं है। एल्गोरिदम को विभाजित और जीतें (रिकर्सिव) अधिक समय महंगा है। लेकिन भले ही आप इसका उपयोग करना चाहते हैं, आप मेरे नीचे एल्गोरिदम का उपयोग कर सकते हैं। असल में, यह पहले की स्थिति में सरणी के सबसे बड़े तत्व लाता है और लगभग रैखिक चल रहा समय है (यह algo हालांकि सिर्फ एक पुनरावर्ती-भ्रम है!):।

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