前往
大廳
主題

ZeroJudge - f981: P = NP 解題心得

Not In My Back Yard | 2021-07-29 00:00:03 | 巴幣 0 | 人氣 243

題目連結:


題目大意:
輸入有多筆測試資料,每筆佔三列。

測資三列依序代表著複數 A 、 B 、 C 之值。每列各給定一個實數數對 a 、 b(-100 ≦ a 、 b ≦ 100),代表複數值 a + bi。

請輸出 Ax ^ 2 + Bx + C = 0 的 x 之解。如果為兩個相異解,則將實部值小的排前面輸出,如果實部一樣則將虛部小的排前面。其格式為「first x = ans1, second x = ans2」,其中 ans1 、 ans2 即為兩根之值;如果為重根則輸出「 the only x = ans」,其中 ans 為該重根之值;如果無解,則輸出「Xx」。

輸出時請將數值四捨五入至小數點後第二位。



範例輸入:
-1.00 0.00
4.60 -14.00
43.71 32.20
26.41 56.63
72.20 72.65
-29.71 -44.80
-1.00 0.00
3.40 -7.40
10.80 12.58
-1.00 0.00
7.40 -6.20
-4.08 22.94
25.03 -48.73
-90.07 -92.53
-71.80 3.71
94.81 -39.49
32.44 -0.88
25.67 -8.62


範例輸出:
the only x = 2.30-7.00i
first x = -1.96+0.51i, second x = 0.42+0.04i
the only x = 1.70-3.70i
the only x = 3.70-3.10i
first x = -0.59+0.42i, second x = -0.16+1.82i
first x = -0.15+0.44i, second x = -0.15-0.55i


解題思維:
根據代數基本定理(Fundamental Theorem of Algebra),一個非零一元 n 次方複係數方程式必有 n 個複數解。因此本題不會出現無解的情況。

而耳熟能詳的一元二次實係數方程式之公式是可以套用在複數系統上的(參見維基的說明)。

再加上 Python 、 C++ 都有著內建的複數類別,所以套公式時會用到的加減乘除以及複數平方根運算都不用自己寫(但是 Java 沒有,得自力更生QQ)。

但是要注意的是比較數值大小時候的浮點數誤差還有要避免「-0.00」這種數值。可以參見這題的作法。




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

創作回應

相關創作

更多創作