Accélérer une fonction avec la programmation dynamique

Question

J'ai ce programme

//h is our N 
    static int g=0; 
    int fun(int h){ 
     if(h<=0){ 
        g++; 
        return g; 
        } 
    return g+fun(h-1)+fun(h-4); 
    } 

Est-il possible de l'accélérer en utilisant la programmation dynamique?

Je compris que cette fonction fonctionne en O (2^n)

Je suis censé réduire le temps d'exécution par la programmation dynamique, mais ne comprennent pas le concept.

Juste demander un coup de pouce dans la bonne direction.

Answer 1

Bien que je ne peux pas donner une réponse à votre question réelle, je suis intrigué par tout autre chose, à savoir la déclaration

return g+fun(h-1)+fun(n-4); 

De toute évidence, votre fonction a pour effet secondaire de modifier la variable statique globale g . Je ne suis pas sûr à 100% si l'expression de l'instruction return évalue réellement d'une manière clairement définie, ou si le résultat peut être indéfini.

Cela peut être un bon exercice de penser à l'ordre dans lequel ces appels de fonction sont exécutés, et comment cela affecte g et ainsi le résultat de la fonction.

Answer 2

Oui, il est possible d'utiliser DP pour l'accélérer et éviter d'utiliser la pile CPU, mais je suis d'accord avec stakx sur les effets secondaires de la modification de la variable statique globale g. Il est préférable de fournir une expression mathématique car la fonction récursive ci-dessus peut donner un résultat différent en fonction de l'ordre & nombre d'appels.

Answer 3

Si nous définissons cet ordre de sommation dans g + fun (h-1) + fun (n-4) est de gauche à droite, que c'est un bon problème défini. Avec ce que je reçois des valeurs pour le plaisir (n), n = 1, ..., 15:

3, 6, 10, 15, 33, 74, 154, 295, 575, 1143, 2269, 4414, 8508, 16396, 31634 

Valeur de retour de plaisir (n) est évalué comme séquence de sommations avec des éléments non-descendants. Chaque somme est pour un plus grand que le précédent (return g ++;) ou identique au précédent (return g + fun() + fun()). La séquence d'exécution des instructions de retour dépend uniquement du paramètre d'entrée fun(). Donc, avec g mis à la valeur initiale! = 0 nous obtenons les mêmes invocations qu'avec g = 0, mais chaque somme est plus grande pour la même valeur initiale. Avec cela, le plaisir (n) avec g initiale> 0 retournera valeur est g * nombre de déclarations de retour exécutées plus grandes qu'avec initial g = 0.

Définir A (n) que le nombre de déclarations de retour exécutées lors de l'exécution du numéro fun (n) et G (n) de l'instruction return exécutée dans la clause si (identique au nombre d'exécutions d'instructions g ++). A et G détient:

A(n) = A(n-1) + A(n-4) + 1 
G(n) = G(n-1) + G(n-4) 
A(n) = 1 and G(n) = 1, for n <= 0 

A partir de ces observations, on peut voir que pour n> 0 est vérifiée:

fun(n) = fun(n-1) + G(n-1) * A(n-4) + fun(n-4) 

implémentation Python simple:

def x(h): 
    Rg = { -3:1, -2:1, -1:1, 0:1 } 
    Ra = { -3:1, -2:1, -1:1, 0:1 } 
    F = { -3:1, -2:1, -1:1, 0:1 } 
    for i in xrange(1, h+1): 
    F[i] = F[i-1] + Rg[i-1]*Ra[i-4] + F[i-4] 
    print i, F[i] 
    Rg[i] = Rg[i-1] + Rg[i-4] 
    Ra[i] = Ra[i-1] + Ra[i-4] + 1 

@stakx: pour l'expression g + fun (h-1) + fun (h-4) on ne peut pas avoir de garantie d'ordre d'évaluation, surtout pas en C.

Answer 4

OK. Nous partons du fun (une version sérialisée où l'ordre d'évaluation est forcé).

int fun(int h){ 
    if(h<=0){ 
     g++; 
     return g; 
    } 
    int tmp1 = g; 
    int tmp2 = fun(h-1); 
    int tmp3 = fun(h-4); 
    return tmp1+tmp2+tmp3; 
} 

Concentrons-sur g et oublier le résultat courant de la fonction

Maintenant, il est facile de changer la fonction de passer en g en tant que paramètre et retourner la nouvelle valeur de g en conséquence.

int gun(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    int tmp1 = g0; 
    int tmp2 = gun(h-1, g0); 
    int tmp3 = gun(h-4, tmp2); 
    return tmp3; 
} 

What can be simplified into: 

int gun(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    return gun(h-4, gun(h-1, g0)); 
} 

Revenons maintenant à l'amusement:

int fun2(int h, int g0){ 
    if(h<=0){ 
     return g0+1; 
    } 
    return g0+fun2(h-1, g0)+fun2(h-4, gun(h-1,g0)); 
} 

fun2 fait exactement la même chose que le plaisir initial, mais maintenant que nous avons supprimé l'effet secondaire et la fonction ne dépend que de son paramètre, nous pouvons memoize résultats (stocker les résultats déjà calculés dans un tableau), ce qui devrait accélérer le calcul.

Nous pouvons encore simplifier un peu le pistolet. Le paramètre G0 est pas vraiment nécessaire, Fixons à 0.

int gun2(int h){ 
    if(h<=0){ 
     return 1; 
    } 
    return gun2(h-4) + gun2(h-1); 
} 

On peut même définir un fun3 avec le paramètre G0 fixé à 0, désormais un peu plus simple, mais il doit encore appeler fun2. Je ne vois pas encore comment simplifier encore mais c'est probablement possible.

int fun3(int h){ 
    if(h<=0){ 
     return 1; 
    } 
    return fun3(h-1)+fun2(h-4, gun2(h-1)); 
}