找到长度为N且标准偏差为K的任意数组

Question

这个问题是在ACM ICPC 2018预赛中提出的。您必须打印任何长度N且标准偏差为K的数组。

Answer 1

您没有提到对数据类型的限制，所以我认为您可以接受浮点结果(另一种选择是，您想要仅限整数的解决方案，如果这是目的，那么下面的内容远远不足以完成该任务。)

在实数上，我们期望给定一个具有标准偏差k'的长度为n-1的数组，我们应该能够通过向较短的数组添加一些元素来导出具有标准偏差k > k'的长度为n的数组。也就是说，通过调整新元素，我们可以连续扫描从k开始并向上的所有值。

根据这一观察结果，我们可能会猜测，我们可以从任何标称数组开始，比如长度为n - 1的[0, 0, ..., 0]，并在其中添加一些元素，使标准偏差"出来"。让我们将要添加的值称为v。这种阵列的平均值是：

m = (0 + 0 + ... + 0 + v) / n = v/n

差异为：

s^2 = [(0-m)^2 + (0-m)^2 + ... + (0-m)^2 + (v-m)^2] / n

我们可以在表达式中用代替平均值

s^2 = [(v/n)^2 + (v/n)^2 + ... + (v/n)^2 + (v-v/n)^2] / n

我们可以考虑出一个v^2术语：

s^2 = v^2[(1/n)^2 + ... + (1/n)^2 + (1-1/n)^2] / n

我们可以用乘法代替重复加法：

s^2 = v^2 [(n-1)(1/n)^2 + (1-1/n)^2] / n

最后，我们可以求解v，看看我们在数组中添加了什么：

v = s / sqrt([(n-1)(1/n)^2 + (1-1/n)^2] / n)

一些代数表明这简化为：

v = s * n / sqrt(n - 1)

回想一下，我们得到了s = k，所以通过代入，我们可以确定v:

v = k * n / sqrt(n - 1)

得到的数组将包含n - 1零和一个v。

示例：k = 1, n = 10:

v = 1 * 10 / sqrt(9) = 10/3
m = 1/3
s = sqrt((9*(1/3)^2 + (10/3-1/3)^2)/10)
= sqrt((9(1/9) + (9/3)^2)/10)
= sqrt((1 + 9)/10)
= sqrt(10/10) = 1