TIMUS1503(高階代數方程求根)

題目

題意：

給定方程 anxn+an−1xn−1+...+a1x+a0=0 a n x n + a n − 1 x n − 1 + . . . + a 1 x + a 0 = 0 ，求出該方程的所有實數解

Solution：

首先對其求導，求出其導函數的所有零點，那麼在導函數兩個相鄰的零點之間，該 n n 次方程一定是單調的，并且最多隻有一個零點，利用這個性質，我們可以二分求出這個零點。

而求出導函數的零點可以遞歸地做下去，直到n=1n=1時，可以直接傳回答案

時間複雜度 O(n3log) O ( n 3 l o g )

Code：

//equ->equation
//d->delta
//s->sign
//rt->root
#include<bits/stdc++.h>
using namespace std;
typedef double D;
typedef vector<D> V;
const D inf=,eps=;
V ans,equ;
int n,i;
D x;
inline int sgn(D x){
    return x<-eps?-:x>eps;
}
D get(V equ,D x){
    D e=,s=;
    for (int i=;i<equ.size();i++) s+=e*equ[i],e=e*x;
    return s;
}
D find(V equ,D l,D r){
    int sl,sr;
    if ((sl=sgn(get(equ,l)))==) return l;
    if ((sr=sgn(get(equ,r)))==) return r;
    if (sl*sr>) return inf;
    for (;r-l>eps;){
        D m=(l+r)/;
        int sm=sgn(get(equ,m));
        if (sm==) return m;
        if (sl*sm<) r=m;
        else l=m;
    }
    return (l+r)/;
}
V solve(V equ,int n){
    V res;
    if (n==){
        if (sgn(equ[])) res.push_back(-equ[]/equ[]);
        return res;
    }
    V dequ(n);
    for (int i=;i<n;i++) dequ[i]=equ[i+]*(i+);
    V drt=solve(dequ,n-);
    drt.insert(drt.begin(),-inf);
    drt.push_back(inf);
    for (int i=;i<drt.size()-;i++){
        D ans=find(equ,drt[i],drt[i+]);
        if (ans<inf) res.push_back(ans);
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for (i=;i<=n;i++) scanf("%lf",&x),equ.push_back(x);
    reverse(equ.begin(),equ.end());//注意逆序
    ans=solve(equ,n);
    sort(ans.begin(),ans.end());
    for (i=;i<ans.size();i++) printf("%.6lf\n",ans[i]);
}