algorithm - 多重嵌套循环索引

Question

我有多个 (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);
            }
    } 
  } 
}

我需要一个公式来根据 i1, ... , iN 在循环中获取 k。

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

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

Answer 1

一般来说，你有一个嵌套的总和:

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

您可以使用 these basic summation formules 从内到外进行简化.正如 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 循环执行相同的操作。到那时，我们将完成 i2 的 3 个完整循环，所以我们得到

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

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

k=k_i1+k_i2+...

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