主題

ZeroJudge - f362: 彼得的誤差率 解題心得

Not In My Back Yard | 2021-01-26 00:00:07

題目連結:


題目大意:
輸入每列給定一個小數點兩位的小數值 k (|k| ≦ 1000),代表你計算出來的自己做計算時的誤差率。

誤差率定義為 |(x - n) ÷ x| ,其中 x 為任一計算的正確答案、 n 為你自己算出來的答案。

但是很不幸的,當你在計算自己的誤差率時就已經被你自己的誤差率本身影響到了。因此,你計算得到的誤差率會有誤差。試問真正的誤差率可能為何?請四捨五入到小數點第二位後輸出。

若有多種可能請由小到大輸出,而若有多個答案四捨五入至小數點第二位後相同時,則只需輸出一次該值即可。若無解,則輸出「NULL」。



範例輸入:
0.00
1.00
0.25


範例輸出:
1.00
0.62
0.21 0.50


解題思維:
將輸入的 k 代入誤差率的公式 |(x - k) ÷ x| 理應得到正確誤差值 x (不過因為誤差,所以得到了 k)。因此
|(x - k) ÷ x| = x
兩邊平方,則得
(x - k) ^ 2 ÷ x ^ 2 = x ^ 2
兩邊同乘以 x ^ 2 得
(x - k) ^ 2 = x ^ 4
等號左邊展開並移項到等號右邊,變為
0 = x ^ 4 - x ^ 2 + 2kx - k ^ 2
分解等號右邊的式子並翻轉等號,可得
(x ^ 2 - x + k)(x ^ 2 + x - k) = 0
所以得到了
(x ^ 2 - x + k) = 0 或 (x ^ 2 + x - k) = 0

而一元二次方程式 ax ^ 2 + bx + c = 0 有相當經典的公式解:
(-b ± √(b ^ 2 - 4ac)) ÷ (2a)
代入上面兩個方程式的值,我們便得到了最終的公式
x = (1 ± √(1 - 4k)) ÷ 2 或 (-1 ± √(1 + 4k)) ÷ 2

可以看到當 1 - 4k = 0 時,方程式 (x ^ 2 - x + k) = 0 無實數解。同理,1 + 4k = 0 時,方程式 (x ^ 2 + x - k) = 0 無實數解。

因此我們可以先判斷以下四個解
(1 + √(1 - 4k)) ÷ 2
(1 - √(1 - 4k)) ÷ 2
(-1 + √(1 + 4k)) ÷ 2
(-1 - √(1 + 4k)) ÷ 2
哪些是實數(根據根號裡面的值)、哪些為負數或 0(可以看到誤差率的公式不會有這兩種輸出值)。篩掉這些不可能的解之後由小到大排序。之後再篩掉四捨五入至小數點第二位相同的解,最後就可以依序輸出剩下的解了。

但是因為我們在處理不少的浮點數,因此需要格外小心浮點數誤差。可以參見這題的做法。

此外,我們可以看到不可能會出現無解(實際上是無實數解)的情況。因為如果無解則將滿足以下兩式:
1 - 4k < 0 以及 1 + 4k < 0
但這將得到 4k 之值要同時大於 1 又要小於 -1 的結論,而這是不可能的。所以我們的方程式必定有實數解。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
35 巴幣: 0

創作回應

相關創作

更多創作