2

在许多编程问题中，都提到了上述约束。我在 codechef 和 SPOJ 中都看到了这一点。

例如Link-1、Link-2等等。（请参阅这两个示例链接中的输出部分）

这个约束是什么意思？以及如何确保我的输出指定了此约束？

4

4 回答 4

11

绝对错误是：

|computedAnswer - correctAnswer|

相对误差为：

|(computedAnswer - correctAnswer) / correctAnswer|

直观地说，绝对误差是计算出的答案（或近似值）与正确（可能未知）答案的差距。相对误差是绝对误差与正确答案的比率。

因此，无论您是使用激光测距仪测量到月球的距离，还是在狐步小跑中尝试正确放置左脚，在任何一种情况下，您的绝对误差都可能是半米。对于月球距离测量，那将是相当不错的；对于狐步舞，它会让你开始与星共舞。

于 2013-03-03T22:12:06.903 回答
3

除了 Ted Hopp 所说的之外，减少错误的一个可能重要因素是通过以下方式最大限度地减少浮点漂移/不准确性：

  • 通过简化/评估将在您的输入上起作用的操作集来减少总浮点计算。（例如，尽可能简化数学表达式）。这是因为浮点错误会在后续操作中复合。
  • 使用最高精度（例如双精度）进行计算。
  • 或者，您可以使用分数类型或更数字化的类，然后在最后将其评估为浮点值。
于 2013-03-03T22:32:22.920 回答
2

这是一个简单的计算机问题：计算 1/3。

如果您使用“普通”计算机数字，例如浮点数、双精度等，那么您计算出的 1/3 版本将不会是 0.3333 ....，它将是 0.333333333332 或 0.333333333334 或类似的东西，因为 1/3 不能完全正确表示为浮点数或有限十进制扩展。当然可以将 1/3 评估到 10^-6 的相对和绝对误差范围内；0.333333333332 和 0.333333333334 都满足这个精度要求。

因此，答案仅在 10^-6 以内的要求允许使用浮点数和双精度的计算机解决方案来解决仅使用浮点数和双精度没有精确数值解的问题。这实际上是几乎所有的数字问题——大多数分数不能精确地用数字计算；计算机使用近似值。

于 2013-03-04T06:26:02.360 回答
1

问题提出者说，如果：

sqrt((your_answer - their_answer)^2) < 1*10^-6

那么你是“正确的”

准确地比较浮点值是非常有问题的。这是因为在有限精度的机器中进行四舍五入（即某些数学答案不能用有限的数字表示，例如 1.0/3.0）。

在计算机上执行的许多问题的解决方案都是迭代的。这意味着，您从第一个猜测开始，然后计算要更改多少猜测。然后你重复这个，计算多少可以改变你的猜测。重复此过程后，您更改猜测的量会越来越小（它会收敛）。一旦变化小于某个指定量，您可以认为您的答案已经收敛，您现在有一个“正确”的答案。梯度体面算法是这种技术的一个典型例子。我没有仔细查看提供的链接，但也许要获得答案，您需要一个迭代解决方案，在这种情况下，您应该使用 1.0 * 10^-6 作为限制来测试您的解决方案是否已经收敛。

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

看来您发布的网站的链接是可以将它们借给数值方法的问题：

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

这似乎是一个有趣的网站，有一些具有挑战性的问题。

于 2013-03-03T23:41:55.457 回答