想象一下，速度表中顯示速度的指標 脫落了。
它被重新連接，但不是以正確的角度。因此，雖然速度表顯示了當前速度的值，但
v它的實際值是v k，其中k是一個未知常數（可能也是負數）。因此，我們開始誠實地記錄我們為找出神秘常數 k 的值而進行的旅行。輸入：
輸入的第一行包含兩個整數：
n(1 ≤ n ≤ 1000)，表示單次運行的部分數，和t(1 ≤ t ≤ 10^6)，表示總運行時間。接下來是幾
n行，每行描述了我們記錄的旅行的一部分。每行包含兩個整數：s(1 ≤ s ≤ 1000) 和v(|v| ≤ 1000)，在這段旅程中，指標插在車速表上時所指示的距離和速度。請記住，即使手套箱上的速度計指標可能有負讀數，它的實際速度在行程的每個部分都始終大于 0。時間以小時為單位，距離以公里為單位，速度以公里/小時為單位。輸出：
問題是要找到K。以每小時公里數給出的神秘常數 k。
輸入示例：
3 5 4 -1 4 0 10 3輸出：
3.000000000輸入：
4 10 5 3 2 2 3 6 3 1輸出：
-0.508653377
好吧，有人告訴我這個問題可以用Approximate algorithm解決。
有人可以寫一個偽代碼解決方案或解釋我如何用這個演算法解決這個問題嗎？
uj5u.com熱心網友回復：
所有這些都在評論中提到，但不清楚......
如果您猜測k的值，那么您可以確定如果該猜測正確，整個行程將花費多長時間：
總時間 T = 距離1 /（速度1 k） 距離2 /（速度2 k）...
如果這個總時間超過了問題中給出的實際總時間，那么你的猜測太小了（你比你猜測的要快）。如果猜測的總時間小于實際的總時間，那么你的猜測太大了（你比你猜測的要慢）。
有了做出和測驗這些猜測的能力，您可以玩更高/更低的游戲來縮小可能的 k 值范圍，直到您盡可能接近真實值。
您不一定能得到確切的值，這就是為什么這可以稱為近似演算法的原因。但是我們使用的數字也具有有限的精度，因此它們可能甚至不能代表確切的值。您可以輕松獲得最接近的可表示值之一，這與“精確”計算一樣好。
玩高/低游戲的演算法稱為“二分搜索”。雙打有點棘手，所以我會寫出來。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;
}
請注意，由于雙精度數字的表示方式，如果 k 為 0 或非常接近它，則此回圈最多可以迭代 2000 次。如果您不希望這樣，那么您可以將(lo < hi)測驗更改為(lo < hi - REALLY_SMALL). 您將不得不忍受不太準確的答案，但您可以限制最大迭代次數。
您還可以使用其他需要較少迭代的近似演算法，例如牛頓法
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/455474.html