5

私はこのプログラムを持っています

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

動的計画法を使用して高速化することは可能ですか?

この関数は O(2^n) で実行されることがわかりました

動的計画法で実行時間を短縮することになっているのですが、概念がわかりません。

正しい方向へのナッジを求めるだけです。

4

4 に答える 4

7

あなたの実際の質問に答えることはできませんが、私はまったく別のことに興味をそそられます。

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

明らかに、関数にはグローバル静的変数を変更するという副作用がありますg。returnステートメントの式が実際に明確に定義された方法で評価されるかどうか、または結果が未定義になる可能性があるかどうかは 100%わかりません。

gこれらの関数呼び出しが実行される順序と、これが関数の結果にどのように影響するかを考えるのは良い練習になるかもしれません。

于 2010-04-27T20:45:52.457 に答える
1

g+fun(h-1)+fun(n-4) の合計順序が左から右であると定義すると、これは適切に定義された問題になります。これで fun(n), n=1,...,15 の値を取得します:

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

fun(n) の戻り値は、非降順の要素を持つ合計のシーケンスとして評価されます。各被加数は、前よりも大きい (return g++;) または前と同じ (return g +fun()+fun()) です。return ステートメントの実行順序は、fun() 入力パラメーターのみに依存します。したがって、g を初期値 != 0 に設定すると、g=0 の場合と同じ加数が得られますが、すべての加数は同じ初期値に対して大きくなります。これにより、初期 g > 0 の fun(n) は、初期 g = 0 よりも大きいg * 実行された return ステートメントの数である値を返します。

fun(n)実行時のreturn文の実行回数をA(n)、if節でreturn文の実行回数をG(n)と定義する(g++文の実行回数と同じ)。A および G 保留の場合:

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

これらの観察から、n > 0 が成り立つことがわかります。

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

シンプルな python 実装:

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: 式 g+fun(h-1)+fun(h-4) の場合、特に C では、評価順序の保証はありません。

于 2010-11-13T17:42:02.883 に答える
0

わかった。楽しいから始めます（評価の順序が強制される連載版）。

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

g に注目して、関数の現在の結果を忘れましょう

これで、g をパラメーターとして渡し、結果として g の新しい値を返すように関数を簡単に変更できます。

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

楽しいことに戻りましょう:

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 は最初の fun とまったく同じことを行いますが、副作用を取り除き、関数がそのパラメーターのみに依存するようになったため、結果をメモ化 (既に計算された結果を配列に格納) できるため、計算が高速化されます。

銃を少し単純化することもできます。g0 パラメータは実際には必要ありません。0 に設定しましょう。

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

g0 パラメーターを 0 に固定して fun3 を定義することもできます。これ以降は少し単純になりますが、それでも fun2 を呼び出す必要があります。さらに単純化する方法はまだわかりませんが、おそらく可能です。

int fun3(int h){
    if(h<=0){
         return 1;
    }
    return fun3(h-1)+fun2(h-4, gun2(h-1));
}
于 2010-11-13T23:15:55.097 に答える
0

はい、DP を使用して高速化し、CPU スタックの使用を回避することは可能ですが、グローバル静的変数 g を変更することの副作用については stakx に同意します。上記の再帰関数は、呼び出しの順序と回数によって異なる結果になる可能性があるため、数式を提供することをお勧めします。

于 2010-11-02T12:49:25.583 に答える