Rekursion, wenn Bedingung

Question

Das Folgende ist eine Implementierung des Problems von 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; 
} 

Warum ist die, wenn die Bedingung enthält n < 49999?

Answer 1

ohne jede Möglichkeit untersucht zu haben, die nicht die ersten 20+ Werten und die maximalen und minimalen Werte:

MY Erwartung ist

die ersten 12 Einträge in dem arr [] sind vorausberechneten zu helfen Verringern Sie die Tiefe einer Rekursion, jedoch ist der Dollarwert nicht der gleiche wie der berechnete Wert für diese ersten 12 Einträge.

für Münzwerte < = 49999, überprüfen, ob bereits berechneten Wert, wenn nicht, dann die Münze in die brechen/2/3/4 Werten und jeden dieser resultierenden Werte Rekursion.

Dieser Grenzwert (49999) könnte auf 100000 erweitert werden, da dies die verfügbare Größe des Arrays arr [] ist.

Die Voreinstellung und das Speichern im Array arr [] helfen, die Ausführungszeit und die Tiefe der Rekursion zu reduzieren.

Die Verwendung des Arrays ist so, dass alle zuvor berechneten Werte (im gebuchten Code, bis zu 49999) sofort von der max() Funktion zurückgegeben werden können, ohne weitere Rekursion.

würde ich den Code leicht für eine bessere Dokumentation und Robustheit und eine schnellere Ausführung wie folgt ändern:

#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

Soweit ich verstehe, dass,

Die Person, die den Code schreiben, irgendwie fand er heraus, dass (manuell), wenn die Münze weniger als 12 ergeben sich dann selbst sein wird. so dass er 12
(überprüfen Sie die Erklärung der Eingangs Münze = 2) verwenden

Und über die Rekursion Funktion

, wie wir wissen, dass wir nicht Array mit 1000000000 Größe erklären kann, damit er versuchen Sie verwenden Sie einen anderen Wert (49999 hier) in der Größe kann er Array erstellen und später das Ergebnis für die Münze in Array wie Arr [12] = 13 (wo 12 ist Münze und 13 ist das Ergebnis), so dass Er kann das Ergebnis ohne generate für den Wert erhalten, indem er das Array mit arr [12] (nur)verwendetfür Münze 12.

Ich hoffe, Sie verstehen.