Recursion स्थिति

Question

यदि निम्न Spoj से समस्या का एक कार्यान्वयन है: - http://www.spoj.com/problems/COINS/

#include <stdio.h> 

#define ll long long 

ll arr[100000]; 

ll max(ll n) 
{ 
    if(n < 49999)// Doubt 
    { 
     if(!arr[n]) 
      return arr[n] = max(n/2) + max(n/3) + max(n/4); 
     else 
      return arr[n]; 
    } 
    else 
     return max(n/2) + max(n/4) + max(n/3); 
} 


int main() 
{ 
    ll n, c = 0, i; 

    for(i = 0; i < 12; i++) // Also why 12 when the input can be <12 
    { 
     arr[i] = i; 
    } 

    while(scanf("%lld", &n) != EOF) 
    { 
     printf("%lld\n", max(n)); 

    } 

    return 0; 
} 

क्यों अगर हालत n < 49,999 में क्या है?

Answer 1

प्रत्येक संभावना है, पहली 20+ मूल्यों और अधिकतम और न्यूनतम मूल्यों के अलावा अन्य जांच की बिना

एक रिकर्सन की गहराई को कम करें हालांकि डॉलर मूल्य उन पहली 12 प्रविष्टियों के लिए गणना मूल्य के समान नहीं है।

सिक्का मूल्यों के लिए < = 49 999, यह देखने के लिए जांचें कि क्या मूल्य पहले ही गणना की गई है, यदि नहीं तो सिक्का को/2/3/4 मानों में तोड़ दें और उन परिणामी मूल्यों में से प्रत्येक को दोबारा शुरू करें।

यह सीमा मान (4 99 99 9) 100000 तक बढ़ाया जा सकता है क्योंकि यह arr [] सरणी का उपलब्ध आकार है।

प्रीसेटिंग और एआर [] सरणी में बचत, निष्पादन समय को कम करने और रिकर्सन की गहराई को कम करने में मदद करने के लिए है।

सरणी का उपयोग किसी भी पहले गणना किए गए मान (पोस्ट कोड में, 4 9 999 तक) को तुरंत max() फ़ंक्शन द्वारा तुरंत रिकर्सन के बिना वापस किया जा सकता है। मूल्य के

#include <stdio.h> 
#include <stdint.h> 

#define MAX_ARRAY_LEN (100000) 

uint32_t arr[ MAX_ARRAY_LEN ] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; 

uint32_t max(uint32_t n) 
{ 
    if(n < MAX_ARRAY_LEN) 
    { // value of 'n' within the range of the learning array arr[] 

     if(!arr[n] && n) 
     { // then learning array arr[] not yet set 
      return arr[n] = max(n/2) + max(n/3) + max(n/4); 
     } 

     else 
     { // else learning array arr[] already set for 'this' value of 'n' 
      return arr[n]; 
     } 
    } 

    else 
    { // value of 'n' is greater than the learning array arr[] 
     return max(n/2) + max(n/4) + max(n/3); 
    } 
} // end function: max 


int main(void) 
{ 
    uint32_t n; 

    int status; 
    while((status = scanf("%u", &n)) == 1 && EOF != status) 
    { 
     if(1000000000 >= n) 
     { 
      printf("%u\n", max(n)); 
     } 

     else 
     { 
      printf(" invalid value entered, must be in the range 0...1 000 000 000\n"); 
     } // end if 
    } // end while 

    return 0; 
} // end function: main 

Answer 2

जहाँ तक मैं समझता हूँ कि,

व्यक्ति जो कोड लिखने, किसी भी तरह वह पता चला कि (स्वयं) यदि सिक्का कम से कम 12 तो परिणाम ही हो जाएगा। इतना है कि वह 12
का उपयोग

और प्रत्यावर्तन समारोह के बारे में (इनपुट सिक्का = 2 की व्याख्या की जाँच)

के रूप में हम जानते हैं कि हम 1,000,000,000 आकार के साथ सरणी की घोषणा नहीं कर सकते हैं तो वह का प्रयास करने के लिए कुछ अन्य मान (4 99 999) का उपयोग करें जिसमें आकार वह बना सकता है और बाद में एआर [12] = 13 (जहां 12 सिक्का है और 13 परिणाम है) जैसे सिक्का में परिणाम लेते हैं। वह परिणाम प्राप्त कर सकता है बिना सरणी के साथ उस सरणी का उपयोग करके मूल्य [12] (केवल)सिक्का के लिए12.

आशा है कि आप समझें।

मेरी उम्मीद

है आगमन [] में पहले 12 प्रविष्टियों में मदद करने के पूर्व गणना कर रहे हैं: