1

编辑：我不是在寻找一种算法，而是一个类似于 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 和我的例子一样简单，如果可行的话）。我真的不知道做这种事情的正式方法，我通常通过直觉来解决更简单的问题。

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

4

3 回答 3

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;
}
于 2013-10-21T22:48:02.857 回答
0

这是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;
}

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

于 2013-10-21T22:33:32.537 回答
0 
result=A[n-1];
for(count=1;count<n;count++)
{
    result=result*C+A[n-1-count];
}
return result;
于 2013-10-21T22:31:08.230 回答