切換
舊版
前往
大廳
主題

ZeroJudge - a581: 祖靈的煩惱 ˊ^ˋ 解題心得

Not In My Back Yard | 2019-05-20 23:25:40 | 巴幣 0 | 人氣 117

題目連結:


題目大意:
給定六個整數 p 、 q 、 r 、 s 、 t 、 u (0 ≦ p 、 r ≦ 20 , -20 ≦ q 、 s 、 t ≦ 0),代表有一方程式
p × e ^ (-x) + q × sin(x) + r × cos(x) + s × tan(x) + t × x ^ 2 + u = 0
試問在 0 ≦ x ≦ 1 的情況下,方程式有無解。

有解的話,請精確到小數點後第四位,第五位四捨五入;反之,輸出「No solution」。



範例輸入:
0 0 0 0 -2 1
1 0 0 0 -1 2
1 -1 1 -1 -1 1


範例輸出:
0.7071
No solution
0.7554


解題思維:
本題可以利用勘根定理(即中間值定理(Intermediate Value Theorem,見維基頁面)的特例)並搭配二分搜尋法(Binary Search)漸漸地求得解,也就是 x 之值。

當區間兩端點分別代入方程式得到的值相乘 ≦ 0 時,代表 a ~ b (含)之間存有解;反之代表在此範圍無解。

因此一開始代入[0, 1]區間。如果相乘結果 > 0 ,即無解,輸出「No solution」;反之,取中間點,用類似的方式看解落在區間的左半邊還是右半邊,並替換原有的區間繼續迭代下去。

而迭代的次數大約 20 次即可跳出,因為 2 ^ (-20)< 0.000001 因而保證了前一次迭代與這一次迭代的 x 值之差不會影響到小數點後第五位的結果。

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

創作回應

胖胖貓
附個你寫過也一樣用到堪根定理的題目:https://home.gamer.com.tw/creationDetail.php?sn=4159163
2019-05-21 12:13:14
Not In My Back Yard
感謝補充,自己都忘記有寫過這題了XD
2019-05-21 12:24:11
心彩
code 那邊要改20 才會過
2023-05-04 14:54:28
Not In My Back Yard
看來我當初不小心複製到疊代數寫 18 的版本了。感謝提醒。
2023-05-04 19:08:58

更多創作