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

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.当递归调用返回时,此平均值再次成倍增加时,您在分区中丢失的有效数字将无法恢复.您通过除以并乘以和来破坏信息.为了获得更高的精确度,您需要在浏览元素时跟踪总和,然后在结尾处进行划分.

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

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

实现移动窗口的自然方式是使用队列,因为您可以向头部添加新元素并从尾部弹出旧元素.