题解 P1024 【一元三次方程求解】
GGN_2015
2017-10-03 16:43:55
牛顿迭代法，看到没人用这种方法，就写了一个。
对于一个已知的x值，每一次根据函数在这一点的导数，把x移动到，切线与x轴相交的地方。
即x[n+1]=x[n]-f(x)/f'(x)，可以证明结果会趋近于函数的一个解，据说这种方法比二分要快。
```cpp
#include<cstdio>
#include<complex>
#include<algorithm>
#include<set>
using namespace std;
struct func3
{
double a,b,c,d;
func3(double A=0,double B=0,double C=0,double D=0){a=A;b=B;c=C;d=D;}
double operator()(double x){return ((a*x+b)*x+c)*x+d;}
double dvt(double x){return (3.0*a*x+2.0*b)*x+c;}
};
void func3solve(func3 f,double st,double& val,double& sol)
{
for(int i=1;!(abs(f(st))<1e-6) && i<=100;i++)
{
st=st-f(st)/f.dvt(st);
}
val=f(st);sol=st;
}
double fix2(double sol)
{
return (double)int(sol*100.0+(sol>0?0.5:-0.5))/100.0;
}
set<double>solutions;
int main()
{
double a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
func3 f(a,b,c,d);
for(double i=-100.0;i<=100.0;i+=0.5)
{
double val,sol;
func3solve(f,i,val,sol);
sol=fix2(sol);
if(abs(val)<1e-6 && solutions.find(sol)==solutions.end())
solutions.insert(sol);
}
for(set<double>::iterator it=solutions.begin();it!=solutions.end();it++)
{
double x=(*it);
printf("%.2lf ",x);
}
return 0;
}
```