一元n次函数求零点

未分类

给定$n,a_0,a_1,...,a_n$,求满足

基础思路是求导后，求出导函数的零点，然后对每个单调区间进行二分求零点，导函数的零点通过递归求解。
注意有些零点是单调区间的端点，在导函数中这些零点应该去掉，但是在最终求解的函数中应该保留。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20;
const double eps=1e-9;
const double INF=1e6;
typedef vector<double> fun;
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
fun cal_d(fun f,int n){
    fun ans(n,0.0);
    for(int i=0;i<n;i++){
        ans[i]=f[i+1]*(i+1);
    }
    return ans;
}
double val(double x,fun f,int n){
    double ans=f[n];
    for(int i=n-1;i>=0;i--){
        ans=ans*x+f[i];
    }
    return ans;
}
int search_ans(double l,double r,fun f,int n,double& ans){
    int ret=dcmp(val(l,f,n)*val(r,f,n));
    if(ret==0){
        if(dcmp(val(l,f,n))==0) ans=l;
        else ans=r;
        return 2;
    }
    else if(ret==1){
        return 0;
    }
    double a=l,b=r;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(dcmp(val(mid,f,n)*val(l,f,n))>=0) l=mid;
        else r=mid;
    }
    ans=l;
    return 1;
}
fun cal_root(fun f,int n,bool flag=0){
    if(n==1) return fun(1,-f[0]/f[1]);
    fun dfun=cal_d(f,n);
    fun droot=cal_root(dfun,n-1);
    droot.insert(droot.begin(),-INF);
    droot.push_back(INF);
    fun ans;
    for(int i=1;i<(int)droot.size();i++){
        double x;
        int ret=search_ans(droot[i-1],droot[i],f,n,x);
        if(ret==0) continue;
        else if(ret==1) ans.push_back(x);
        else{
            if(flag) ans.push_back(x);
        }
    }
    return ans;
}
void solve(){
    int n;
    scanf("%d",&n);
    fun f(n+1,0.0);
    for(int i=n;i>=0;i--){
        scanf("%lf",&f[i]);
    }
    fun ans=cal_root(f,n,1);
    for(auto x:ans){
        printf("%.6f %.6f\n",x,val(x,f,n));
    }
    printf("\n");
}
int main(){
    solve();
    return 0;
}