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。我不能 100% 确定return语句的表达式是否以明确定义的方式实际计算，或者结果是否可能未定义。

考虑这些函数调用的执行顺序，以及它如何影响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) 的返回值被评估为具有非降序元素的求和序列。每个加数都比前一个大（返回 g++;）或与前一个相同（返回g +fun()+fun()）。返回语句的执行顺序仅取决于 fun() 输入参数。因此，将 g 设置为初始值！= 0 我们得到与 g=0 相同的加数，但对于相同的初始值，每个加数都更大。这样，初始 g > 0 的 fun(n) 将返回g * 执行的返回语句数，大于初始 g = 0 的值。

将 A(n) 定义为执行 fun(n) 时执行的 return 语句数，以及 G(n) 在if子句中执行的 return 语句数（与 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

是的，可以使用 DP 来加速它并避免使用 CPU 堆栈，但我同意 stakx 关于更改全局静态变量 g 的副作用。最好提供一个数学表达式，因为上面的递归函数可能会根据调用的顺序和次数给出不同的结果。

于 2010-11-02T12:49:25.583 回答
0

好的。我们从 fun（强制评估顺序的序列化版本）开始。

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

我们甚至可以定义一个 fun3，其中 g0 参数固定为 0，以后会更简单一些，但它仍然必须调用 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 回答