algorithm - 将条件求和转换为封闭形式的解决方案

Question

通常求和可以转换为封闭形式的解决方案。

例如

for (int i=0;i<n;i++)
  result += i;

相当于result += max(0, n * ( n - 1) / 2)

for (int i=0;i<n;i++)
  for (int j=0;j<m;j++)
    result += i;

相当于result += max(0, m * n * ( n - 1) / 2)

for (int i=0;i<n;i++)
  for (int j=0;j<m;j++)
    if (i < j)
      result += i;

相当于

for (int i=0;i<n;i++)
  for (int j=i+1;j<m;j++)
     result += i;

因此相当于

for (int i=0;i<n;i++)
  if (i+1 < m)
     result += i * (m-i);

因此相当于

for (int i=0;i<min(n,m-1);i++)
     result += m * i - i * i;

因此最终相当于 result += max(0, m * min(n,m-1) * (min(n,m-1) - 1) / 2 - (min(n,m-1) - 1) * ((min(n,m-1) - 1) + 1) * (2 * (min(n,m-1) - 1) + 1) / 6)或者更容易写成 result += max(0, m <= n ? m * (m-1) * ((m-1) - 1) / 2 - ((m-1) - 1) * (((m-1) - 1) + 1) * (2 * ((m-1) - 1) + 1) / 6) : m * n * (n - 1) / 2 - (n - 1) * ((n - 1) + 1) * (2 * (n - 1) + 1) / 6)

什么时候可以转换为封闭形式的解决方案？

看来，如果只允许条件、加法和乘法(即多项式)，总是可以从最内层循环开始，跟踪允许的最小/最大值范围和添加的多项式。

但是，手动执行此转换非常容易出错且耗时，因为范围在每个循环中都被拆分并呈指数增长。

是否有工具可以从迭代版本自动生成封闭形式的解决方案？

如果也允许除法，它会变得多难？

for (int i=2;i<n;i++)
  if (i % 2 == 0) 
    result += 1;

相当简单，因为 for (int i=2;i<n;i+=2) result += 1;相当于max(0, (n/2) * (n/2 + 1) )

另一方面

for (int i=2;i<n;i++)
  if (n % i == 0) 
    result += 1;

似乎很难转化。

Answer 1

虽然有许多求和的封闭形式表达式，但也有许多其他的，没有人能够找到一个，比如调和数(请注意，此类求和的数量取决于您在封闭形式)。

It seems, if only conditions, addition and multiplication (i.e. polynomials) are allowed, it is always possible to start at the inner most loop, track the range of allowed min/max and the added polynomial.

你几乎是对的，如果条件只影响求和的参数(第一项或最后一项，或可能的步长，如 if (i % 2 == 0))，则有始终是封闭形式，可以表示为有理函数。这些，以及其他表达式，可以使用例如 finite calculus 来计算。 .

对于更多种类的表达式，您可以使用 generating functions (请参阅第 17.2.2 节以获得非常温和的介绍)。这些在很大程度上可用于计算某些表达式(求和或递归关系)的封闭形式。

How much harder does it become, when division is allowed, too?

正如我所说，if (i % 2 == 0) 相当简单，因为它所做的只是增加求和的步长，例如

for (int i = 0; i <= n; i++)
  if (i % 2 == 0) 
    result += i;

有效地成为

for (int i = 0; i <= n/2; i++)
  result += 2*i;

这很适合 n 的封闭形式。其他条件，例如您提供的 if (n % i == 0)，将更加困难。例如，考虑非常相似的表达式，它计算除数之和

for (int i = 1; i < n; i++)
  if (n % i == 0)
    result += i;

如果它允许封闭形式的表达式，那么这可以很容易地用于分解具有两个素因数的数字，这通常被认为是困难的。