4

假设您有一个 int 数组（使用任何具有固定大小 int 的语言）。您将如何计算最接近其平均值的 int 值？

编辑：要清楚，结果不必存在于数组中。也就是说，对于输入数组 [3, 6, 7]，预期结果是 5。另外我想我们需要指定一个特定的舍入方向，所以如果你同样接近两个数字，就说向下舍入。

编辑：这不是家庭作业。我已经五年没有做作业了。这是我第一次使用stackoverflow，所以请友好！

编辑：总结和划分的明显方法可能会溢出，所以我试图考虑一种对于大型数组和大型整数来说安全溢出的方法。我认为正确处理溢出（不作弊和使用不同的类型）是迄今为止这个问题中最难的部分。

4

8 回答 8

5

这是一种快速、合理的溢出安全方法，并且可以在事先不知道元素数量时工作。

// The length of someListOfNumbers doesn't need to be known in advance.
int mean(SomeType someListOfNumbers) {  
    double mean = 0, count = 0;
    foreach(element; someListOfNumbers) {
        count++;
        mean += (element - mean) / count;
    }
    if(count == 0) {
        throw new UserIsAnIdiotException(
                  "Problem exists between keyboard and chair.");
    }
    return cast(int) floor(mean);
}
于 2009-02-21T03:32:36.137 回答
2

嗯...如何计算平均值然后舍入为整数？round(mean(thearray))大多数语言都有允许您指定舍入方法的工具。

编辑：所以事实证明，这个问题实际上是关于避免溢出，而不是四舍五入。让我明确一点，我同意那些（在评论中）说这在实践中不需要担心的人，因为它很少发生，当它发生时，你总是可以使用更大的数据类型。

我看到其他几个人给出的答案基本上包括将数组中的每个数字除以数组的计数，然后将它们相加。这也是一个很好的方法。但只是为了好玩，这里有一个替代方案（在 C-ish 伪代码中）：

int sum_offset = 0;
for (int i = 1; i < length(array); i++)
     sum_offset += array[i] - array[i-1];
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + array[0];

或另一种方法来做同样的事情：

int min = INT_MAX, max = INT_MIN;
for (int i = 0; i < length(array); i++) {
     if (array[i] < min) min = array[i];
     if (array[i] > max) max = array[i];
}
int sum_offset = max - min;
// round by your method of choice
int mean_offset = round((float)sum_offset / length(array));
int mean = mean_offset + min;

当然，您需要确保sum_offset不会溢出，如果最大和最小数组元素之间的差异大于 INT_MAX，就会发生这种情况。在这种情况下，将最后四行替换为如下内容：

// round by your method of choice
int mean_offset = round((float)max / length(array) - (float)min / length(array));
int mean = mean_offset + min;

琐事：这种方法，或者类似的方法，也适用于心理计算一个数组的平均值，该数组的元素聚集在一起。

于 2009-02-21T02:45:22.523 回答
2

通过将数字相加并除以它们的数量来计算总和，并进行四舍五入：

mean = (int)((sum + length/2) / length;

如果您担心溢出，可以执行以下操作：

int mean = 0, remainder = 0
foreach n in number
   mean += n / length
   remainder += n % length
   if remainder > length
       mean += 1
       remainder -= length
if remainder > length/2
   mean += 1
print "mean is: " mean

请注意，这不是很快。

于 2009-02-21T02:34:56.790 回答
1

保证不溢出：

length ← length of list
average ← 0
for each result in the list do:
    average ← average + ( result / length )
end for

如果由于截断而使用整数，这会导致严重的准确性问题（六个 4 的平均值为 0）

于 2009-02-21T03:40:04.153 回答
0

ARM 组件。=] 未经测试。不会溢出。曾经。（我希望。）

大概可以优化一下。（也许使用 FP/LR？） =S 也许 THUMB 在这里会更好用。

.arm

; r0 = pointer to array of integers
; r1 = number of integers in array
; returns mean in r0
mean:
stmfd sp!, {r4,r5}
mov r5, r1

mov r2, 0          ; sum_lo
mov r3, 0          ; sum_hi

cmp r1, 0          ; Check for empty array
bz .end

.loop:
ldr r4, [r0], #4
add r2, r2, r4
adc r3, r3, #0     ; Handle overflow
sub r1, r1, #1     ; Next
bnz .loop

.end:
div r0, r2, r3, r5 ; Your own 64-bit/32-bit divide: r0 = (r3r2) / r5
bx lr
于 2009-02-21T04:44:27.277 回答
0

欢迎。鱼，希望您的逗留愉快。

以下伪代码显示了在总和适合整数类型的情况下如何执行此操作，并四舍五入到最接近的整数。

在您的示例中，数字加总和为 16，除以 3 得到 5 1/3，四舍五入为 5。

sum = 0
for i = 1 to array.size
    sum = sum + array[i]
sum = sum / array.size
sum = round (sum)
于 2009-02-21T02:54:39.160 回答
0

获取平均值的伪代码：

double mean = 0
int count = 0
foreach int number in numbers
    count++
    mean += number - mean / count

round(mean) // rounds up
floor(mean + 0.5) // rounds up
ceil(mean - 0.5) // rounds down

舍入通常涉及加 0.5，然后截断（下限），这就是为什么 3.5 舍入为 4。如果您希望 3.5舍入为 3，请自己执行舍入代码，但反过来：减去 0.5，然后找到上限。

编辑：更新的要求（没有溢出）

于 2009-02-21T03:00:18.227 回答
0

此伪代码找到平均值并涵盖溢出问题：

double avg = 0
int count = 0
for x in array:
    count += 1
    avg = avg * (count - 1) / count   // readjust old average
    avg += x / count                  // add in new number

之后，您可以应用舍入代码。如果没有简单的方法以您的语言进行四舍五入，那么这样的方法将起作用（超过 0.5 时四舍五入）：

int temp = avg - int(avg)   // finds decimal portion
if temp <= 0.5
    avg = int(avg)          // round down
else
    avg = int(avg) + 1      // round up
于 2009-02-21T03:17:33.833 回答