Przyspieszenie funkcji z programowania dynamicznego

Question

mam ten program

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

Czy to możliwe, aby ją przyspieszyć stosując dynamiczne programowanie?

zorientowali się, że ta funkcja działa w czasie O (2^n)

ja powinienem zmniejszyć czas pracy przez programowania dynamicznego, ale nie rozumieją pojęcia.

Po prostu prośbą o skierowanie we właściwym kierunku.

Answer 1

Chociaż nie mogę dać odpowiedź na pytanie rzeczywistego, jestem zaintrygowany coś zupełnie innego, a mianowicie oświadczenie

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

Oczywiście czynność ma efekt uboczny zmianę globalną zmienną statyczną g . Nie jestem w 100% pewny, czy wyrażenie wyrażenia return faktycznie ocenia w sposób jasno określony, czy też wynik może być niezdefiniowany.

To może być miłe ćwiczenie, aby pomyśleć o kolejności wywoływania tych wywołań funkcji i o tym, w jaki sposób wpływa to na g, a tym samym na wynik funkcji.

Answer 2

Tak, można użyć DP do przyspieszenia i uniknięcia stosu procesora, ale zgadzam się ze stakxem na temat skutków ubocznych zmiany globalnej zmiennej statycznej g. Lepiej podać wyrażenie matematyczne, ponieważ powyższa funkcja rekursywna może dawać inny wynik w zależności od liczby zleceń &.

Answer 3

Jeśli zdefiniujemy, że kolejność sumowania w g + fun (h-1) + zabawa (n-4) jest od lewej do prawości, to jest to dobrze zdefiniowany problem. Z tym mam wartości dla zabawy (n), n = 1, ..., 15: wartość

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

Return Of Fun (n) jest oceniany jako sekwencji sumowania z elementami nie-malejącym. Każdy summand jest większy niż poprzedni (return g ++;) lub taki sam jak poprzedni (return g + fun() + fun()). Sekwencja wykonywania instrukcji return zależy tylko od parametru wejściowego fun(). Tak więc, przy g ustawionej na wartość początkową! = 0 otrzymujemy te same sumy co przy g = 0, ale każdy summand jest większy dla tej samej wartości początkowej. Z tym, zabawy (n) o początkowej zawartości G> 0 powróci wartość jest g * ilość wykonanych instrukcji obie większych niż w początkowej zawartości G = 0.

zdefiniować (n), jak liczba wykonanych instrukcji obie podczas wykonywania fun (n) i G (n) liczba wykonanej instrukcji return w jeśli klauzula (taka sama jak liczba instrukcji g ++). Dla A i G posiada:

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 

z tych obserwacji można zauważyć, że dla n> 0 zachodzi:

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

Prosta implementacja Pythona:

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: do wyrażania g + zabawa (h-1) + zabawa (h-4) nie możemy zagwarantować porządku oceny, zwłaszcza nie w C.

Answer 4

OK. Zaczynamy od zabawy (serializowana wersja, w której wymuszona jest kolejność oceny). nacisk

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

Miejmy na gi zapomnieć bieżący wynik funkcji

Teraz łatwo jest zmienić funkcję przechodzić w g jako parametr i powrócić nową wartość g wyniku.

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

Wracając do zabawy:

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 robi dokładnie to samo, co w początkowej zabawy, ale teraz, kiedy usunięto efekt uboczny, a funkcja zależy tylko od jego parametrów, możemy memoize wyniki (zapisano już wyniki w tablicy), co powinno przyspieszyć przetwarzanie.

Nadal możemy uprościć broń. Parametr G0 nie jest to naprawdę konieczne, niech ustawić go na 0.

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

Możemy nawet zdefiniować fun3 z parametrem g0 ustalonej na 0, odtąd trochę prostszy, ale nadal ma zadzwonić fun2. Nie widzę jeszcze, jak uprościć dalej, ale prawdopodobnie jest to możliwe.

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