b893 - 勘根定理
題目描述
題目描述了勘根定理，並要求撰寫程式來找出一個五次多項式函數的所有實根，並輸出根所在的連續整數範圍。如果有多個根，則按升序輸出。如果沒有根，則輸出 "N0THING! >\<"。如果有多個根落在同一個整數點，則輸出兩次該整數。如果根的數量過多，則輸出 "Too many... = ="。
解題思路
題目要求找出多項式函數的根的範圍，可以使用勘根定理的原理，即在兩個整數 a 和 b 之間，如果 f(a) 和 f(b) 的符號不同，則說明在這個範圍內存在至少一個根。程式碼使用暴力搜尋的方法，遍歷從 -36 到 36 的整數，計算多項式函數的值。如果找到一個根（函數值為 0），則輸出該根兩次。如果找到兩個符號相反的函數值，則輸出這兩個整數作為根的範圍。
複雜度分析
- 時間複雜度: O(n)，其中 n 是搜尋的整數範圍的大小 (36 - (-36) + 1 = 73)。由於迴圈遍歷固定範圍內的整數，因此時間複雜度是線性的。
- 空間複雜度: O(1)，程式碼只使用了幾個變數來儲存中間結果，空間複雜度是常數級別。
程式碼
#include <iostream>
using namespace std;
int main(){
long long int a,b,c,d,e,f;
while(cin>>a>>b>>c>>d>>e>>f){
if(!a&&!b&&!c&&!d&&!e&&!f){
cout << "Too many... = =\"\n";
continue;
}
bool ans=0;
long long int tmp=0,tmp2=0;
for(int x=-36;x<=36;++x){
tmp=a*x*x*x*x*x+b*x*x*x*x+c*x*x*x+d*x*x+e*x+f;
if(!tmp){
cout << x << " " << x << "\n";
ans=1;
}
else if(tmp2*tmp<0){
cout << x-1 << " " << x << "\n";
ans=1;
}
tmp2=tmp;
}
if(!ans)
cout << "N0THING! >\\\\\\<\n";
}
}