c - 使用递归的简单移动平均线

Question

我正在尝试求一系列数字的平均值:

double moving_average((unsigned num )
{
    double temp;

    temp = calculate_number(num);

    if ( num > 0 ) moving_average( num - 1 );
    else
      return 0;
    return temp * (n - 1) / num;
}

我正在尝试实现指示此页面:

http://en.wikipedia.org/wiki/Moving_average

但是我做的这段代码没有返回正确的平均值 ¿ 实现有什么问题？

Answer 1

你的程序的主要缺陷是递归计算不正确。

要计算平均值，您必须获得当前值和剩余值的总和，然后将该总和除以值的数量。

• 值的数量是num。

• 当前值是calculate_number() 返回的值。

• 剩余值的总和是num-1乘以剩余值的平均值。

• 通过递归调用 average() 计算剩余值的平均值。

因此，我们编写如下:

double average(int num) {
    double current = calculate_number(num);
    if (num == 1) {
        return current;
    }
    return (current + (num-1)*average(num-1)) / num;
}

使用该函数的完整程序可能如下所示:

#include <stdio.h>

int arr_length = 16;
double arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3};

double calculate_number(int i) {
    return arr[arr_length-i];
}

double average(int num) {
    double current = calculate_number(num);
    if (num == 1) {
        return current;
    }
    return (current + (num-1)*average(num-1)) / num;
}

int main() {
    int i;
    for (i = 1; i <= 5; ++i) {
        printf("average of the last %d numbers = %.3f\n",
                i, average(i));
    }
    return 0;
}

请注意，这不是计算平均值的好方法，因为每次将当前总和除以 num 时都会失去精度。当此平均值随着递归调用返回而再次相乘时，您在除法中丢失的有效数字不会恢复。您通过除以然后乘以总和来破坏信息。为了获得更高的精度，您可能希望在遍历元素时跟踪总和，然后在最后进行除法。

要考虑的另一点是移动平均线的含义。我们上面实现的不是移动平均线而是固定平均线。它是元素固定窗口的平均值。如果将窗口移动一个位置，则必须重新开始并重新计算总和。

实现移动窗口的正确方法是跟踪窗口中的所有元素。当您将窗口向右移动一个位置时，您从窗口中删除最左边的元素并从总和中减去它的值，然后将新的最右边元素添加到窗口并将其值添加到总和中。这就是使它成为移动总和的原因。将移动总和除以元素数得到移动平均值。

实现移动窗口的自然方法是使用队列，因为您可以将新元素添加到头部并从尾部弹出旧元素。