Java中整数溢出

Question

我在一次采访中被问及这一点。我被要求计算数字x1，x2，x3，…的平均值，。。。xn公司

class Iterator {
    bool hasNext;
    int getNext();
}

//所以归结起来是这样的：

double average (Iterator & it) {

double average = 0;
double sum = 0;
int len = 0;

while (it.hasNext == true) {

    sum += it.getNext();
}

if (len > 0)
    average = sum / len;
}

面试官说列表的大小是未知的，它可能很大，所以总和可能会溢出。他问我如何解决溢出问题，我的回答是跟踪我们可能超过最大数量的次数等等，他说了一些关于推入堆栈、平均值和长度的事情，我从来没有真正理解他的解决方案，将这两个变量推入某种列表中？有人知道吗？

Answer 1

如果进一步简化rgettman公式，您将得到以下结果：

len++;
average = average + (it.next() - average) / len;

Answer 2

他可能指的是这样一个事实：你不需要所有的术语来计算平均值，你可以跟踪移动平均值。这可以与迄今为止考虑得出的术语总数一起使用。

由于总数可能太大而无法存储很长时间，因此您希望使用Bigintger之类的东西来保存总数。

Answer 3

我不知道如何使用堆栈，但在代数的帮助下，我们可以使用旧的平均值推导出新平均值的公式。

假设您已经平均了n-1个项目，并且您在oldAvg中得到了该平均值。

oldAvg=（x₁x₂。x_n-1）/（n-1）

新的平均值将由newAvg表示：

=（x₁x₂... x_n-1x_n）/n

通过一些代数运算，我们可以使用旧的平均数、平均项数和下一项来表示新的平均数。

新平均值=（x_{1x2。xn-1）/n xn}

=（（n-1）/（n-1））*（x₁x₂... x_n-1）/n x_n/n

=oldAvg/n*（n-1）x_n/n

这可以通过在乘以n-1之前除以n来避免溢出。然后，只需添加下一项x除以n即可。

第一个循环将建立平均值等于第一个元素，但每个后续循环将使用上述公式来导出新的平均值。

n++;
newAvg = oldAvg / n * (n - 1) + it.next() / n;