arrays - 将递归函数转换为代表算法输出的迭代函数

Question

编辑：我不是在寻找一种算法，而是一个类似于 f(i) = sum i=0 to n-1 (C * A[i]) 的数学方程，但相对于 n（数组的长度）而不是我（迭代＃）。

我有一个算法，它遍历大小为 n 的数组 A（元素 A[0] 到 A[n-1]），并对数组的元素进行一些计算。我设法为算法的输出值提取了以下递归函数 f(i)，其中 i 是循环的迭代：

• f(0) = A[n-1]
• f(i) = C * f(i-1) + A[n-1-i]

...其中 C 是一个整数常量。

知道我们循环遍历整个数组后，我们进行 n-1 次迭代（我们在循环之前处理 f(0)）。我想将此递归函数表示为直接迭代函数，例如 f(i) = sum i=0 to n-1 (C * A[i])，但我不知道如何（肯定不是） t 和我的例子一样简单，如果可行的话）。我真的不知道做这种事情的正式方法，我通常通过直觉来解决更简单的问题。

可行吗？如果是这样，怎么做？希望我足够清楚，谢谢。

Answer 1

我想说你描述的功能很简单

f(n) = sum (0 <= i < n: C^i * A[i])

你可以计算出

int c = 1;
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += c * A[i];
    c *= C;
}

Answer 2

这是Java中的解决方案：

public static int[] f(int[] A) {
  int n = A.length();
  int[] result = int[n];
  result[0] = A[n-1];
  for (int i = 1; i < n; i++) {
    result[i] = result[i-1] + A[n-1-i];
  }
  return result;
}

只需使用一个新数组，原始递归算法的转换几乎是直接的。

Answer 3

result=A[n-1];
for(count=1;count<n;count++)
{
    result=result*C+A[n-1-count];
}
return result;