如何在此问题中使用近似算法？

Question

Imagine that a needle in the speedometer, which shows the speed, has fallen off.

It was reattached, but not at the right angle. So, although the speedometer showed the value of the current speed v, its actual value was v+k, where k is an unknown constant (probably also negative). So we started keeping honest records of the trips we made to find out the value of the mysterious constant k.

Input:

The first line of the input contains two integers: n (1 ≤ n ≤ 1000), which represents the number of parts of a single run, and t (1 ≤ t ≤ 10^6), which represents the total run time.

This is followed by n lines, where each describes one part of the trip that we recorded. Each line contains two integers: s (1 ≤ s ≤ 1000) and v (|v| ≤ 1000), the distance and speed indicated by the speedometer with the needle stuck on during that part of the journey. Keep in mind that even though the speedometer needle on the glove box may have negative readings, its actual speed was always greater than 0 during every part of the trip. The time is given in hours, the distance in kilometres and the speed in kilometres per hour.

Output:

The problem is to find K. The mysterious constant k given in kilometers per hour.

Example of Input:
3 5
4 -1
4 0
10 3
Output:
3.000000000
Input:
4 10
5 3
2 2
3 6
3 1
Output:
-0.508653377

嗯，有人告诉我这个问题可以用近似算法解决。

有人可以写一个伪代码解决方案或解释一下我如何用这个算法解决这个问题吗？

Answer 1

所有这些都在评论中提到，但不清楚...

如果您猜测 k 的值，那么您可以确定如果猜测正确，整个行程 需要多长时间 :

总时间T=距离₁/(速度₁+k)+距离₂/(速度₂+k)...

如果这个总时间比问题中给出的实际总时间多，那么你的猜测就太小了（你比你猜的要快）。如果猜测的总时间小于实际总时间，则说明你猜的太大了（你比你猜的慢）。

有了做出和测试这些猜测的能力，您可以玩 higher/lower 游戏来缩小可能的 k 值范围，直到您尽可能接近真实值。

你不一定能得到准确的值，这就是为什么这可以称为近似算法。但是我们使用的数字也具有有限的精度，因此它们可能甚至不能代表准确的值。您可以轻松获得最接近的可表示值之一，这与“精确”计算一样好。

玩 higher/lower 游戏的算法称为“二进制搜索”。双打有点棘手，所以我会写出来。给定一个函数 isTooHigh 来测试对 k 的猜测，你可以这样做：

double findk()
{
    double lo = -minOfAll(speeds);
    double hi = max(1.0, lo);
    while(!isTooHigh(hi)) {
        hi *= 2.0;
    }
    while(lo < hi) {
        double test = lo + (hi-lo)*0.5;
        if (isTooHigh(test)) {
            if (test >= hi) {
               // we've reached the limit of precision
               break;
            }
            hi = test;
        } else {
            if (test <= lo) {
               // we've reached the limit of precision
               break;
            }
            lo = test;
        }
    }
    return lo;
}

请注意，由于 double-precision 数字的表示方式，如果 k 为 0 或非常接近它，此循环最多可迭代 2000 次。如果您不想这样，则可以将 (lo < hi) 测试更改为 (lo < hi - REALLY_SMALL)。您将不得不忍受不太准确的答案，但您可以限制最大迭代次数。

您还可以使用其他需要较少迭代次数的近似算法，例如 Newton's method

如何在此问题中使用近似算法？

How can I use the Approximate algorithm in this problem?

c

algorithm

approximation