ricorsione se Condizione

Question

Quello che segue è un'implementazione del problema da 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; 
} 

Perché la condizione di se contengono n < 49999?

Answer 1

senza aver esaminato ciascuna possibilità, tranne il primo 20+ valori e massimo e minimo di valori:

mia aspettativa è

i primi 12 voci nella arr [] sono pre-calcolate per aiutare ridurre la profondità di una ricorsione, tuttavia il valore in dollari non è lo stesso del valore calcolato per le prime 12 voci.

per valori monete < = 49999, verificare se il valore è già calcolato, in caso contrario, quindi rompere la moneta nei valori/2/3/4 e recedere ciascuno di quei valori risultanti.

Questo valore limite (49999) potrebbe essere esteso a 100000 poiché è la dimensione disponibile dell'array arr [].

la preimpostazione e il salvataggio nell'array arr [] servono a ridurre il tempo di esecuzione e la profondità della ricorsione.

l'utilizzo dell'array è tale che qualsiasi valore precedentemente calcolato (nel codice postato, fino a 49999) può essere immediatamente restituito dalla funzione max(), senza ulteriore ricorsione.

vorrei modificare il codice un po 'per una migliore documentazione e la robustezza e l'esecuzione più veloce come segue:

#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

Per quanto ho capito che,

La persona che scrivere il codice, in qualche modo ha scoperto che (manualmente) se la moneta meno di 12 poi risultato sarà se stessa. così che usa 12.
(cercare la spiegazione della moneta ingresso = 2)

E sulla funzione ricorsione

come sappiamo non possiamo dichiarare array con 1000000000 dimensioni così prova a usa un altro valore (49999 qui) in quale dimensione può creare l'array e poi prendere il risultato per la moneta in array come arr [12] = 13 (dove 12 è moneta e 13 è il risultato) in modo che può ottenere il risultato senza generare per il valore usando quella matrice con arr [12] (solo) per moneta 12.

Spero che tu capisca.