切換
舊版
前往
大廳
主題

ZeroJudge - b893: 勘根定理 解題心得

Not In My Back Yard | 2018-10-11 23:27:53 | 巴幣 2 | 人氣 1521

題目連結:


題目大意:
給定6個整數a、b、c、d、e、f(皆介於 -40(含) ~ 40(含) 之間),代表一多項式函數ax ^ 5 + bx ^ 4 + cx ^ 3 + dx ^ 2 + ex + f。

對這函數的每個根,求出介於兩個連續整數之間,並由小到大輸出。

如果無實根,請輸出「N0THING! >\\\<」;如果有無限多組解,請輸出「Too many... = ="」;如果根剛好是整數,則輸出根的值「兩次」。

題目保證,不會在連續整數間有兩個以上的根。且所有輸出的數字X,滿足
-2147483647 ≦  X ^ 6 ≦ 2147483647



範例輸入:
0 0 6 -25 -29 20


範例輸出:
-2 -1
0 1
5 5



解題思維:
先討論有限組解的情形。因為輸出的數字X,滿足
-2147483647 ≦  X ^ 6 ≦ 2147483647

因此,我們可以推出X的範圍介於,-35.9 ≦ X ≦ 35.9。所以從-36代值到函數裡,直到X=36為止,這樣就可以跑遍所有可能的範圍了。

至於找根在哪幾個連續整數間,則需要「勘根定理」(題目標題的由來),詳細方法可以看題目本身XD

如果跑完以上步驟,卻沒有輸出任何一個根,則是無實根的情形,即輸出「N0THING! >\\\<」。值得注意的是,這段輸出的字串用到了脫逸字元「\」。在C++裡要輸出的話,記得寫成「\\」。

最後是有無限實根的情況,不難看出唯一的情形只會發生在a=b=c=d=e=f=0的時候,這時候就可以直接輸出「Too many... = ="」。類似地,這裡也有特殊字元「"」,要輸出請打成「\"」。




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

創作回應

場外第一邊緣人
先卡 段考完 看
2018-10-11 23:30:13

更多創作