1

我有多个（N）嵌套循环，如下所示：

int k = 0;
for (int i1 = 0; i1 < n; i1++)
{
  for (int i2 = 0; i2 <= i1; i2++)
  {
    for (int i3 = 0; i3 <= i2; i3++)
    {
       ...
            for (int iN = 0; iN <= i{N-1}; iN++)
            { 
              k++;
              //k = f(i1, ... , iN);
            }
    } 
  } 
}

我需要一个公式来进入k基于i1, ... ,的循环iN。

对于N=1：k=f(i1)=i1

对于N=2：k=f(i1,i2)=i1*(i1+1)/2+i2

4

2 回答 2

0

一般来说，你有一个嵌套的 sum ：

sum(sum(sum(1,i3=0..i2),i2=0..i1),i1=0..n-1)

您可以使用这些基本的求和公式从内到外进行简化。最终结果将仅取决于 izomorphius 评论的 N，因为 N 是 i1 的上限，即 i2 的上限，...

编辑：好的，通过您的编辑，我现在看到您有不同的问题。现在它有点复杂，但仍然没有问题。

我们需要为此拆分一些东西。我将计算值 k= f(4,3,1)。在那个时间点，我们将执行 4 次完整的 i1 循环（i1=0,1,2,3）并且正在执行第五次。i1(=k_i1) 的 4 个完整循环后的 k 值（就在我们开始第五次之前）可以使用此函数计算（与以前相同）。

k_i1=sum(sum(sum(1,i3=0..i2),i2=0..l),l=0..i1-1) = f1(i1);

现在我们开始第 5 个循环并对 i2 循环执行相同的操作。那时，我们将完成 3 个完整的 i2 循环，因此我们得到

k_i2=sum(sum(1,i3=0..l),l=0..i2-1)=f2(i2);

这适用于所有循环。要获得最终值，您必须添加每个 fi 函数。k 看起来像

k=k_i1+k_i2+...

我的解释中可能存在一些小 (+-1) 错误，但基本思想是使用公式来计算完整循环。

于 2012-11-11T13:28:38.197 回答
0

我想我们可以把这个问题看作是与重复问题的组合。答案是 C(n+N-1,N)。您可以查看维基百科的组合部分以获取更多详细信息。希望能帮助到你！

于 2012-11-11T14:44:29.640 回答