P1024 一元三次方程求解 （二分&暴力&牛顿迭代）

题目传送门

题意：给定一元三次方程求解三个根。

思路：sol 1：枚举每个长度为1的区间，对每个区间进行二分。 sol 2：暴力从-100， 100 每次1e-3的枚举。
sol 3：求出函数的两个极值点 ，然后分成三个区间进行牛顿迭代。

二分AC代码：

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double fun(double x){
	return a*pow(x,3)+b*pow(x,2)+c*x+d;
}
int main(){
	cin>>a>>b>>c>>d;
	int cnt=0;
	for(int i=-100;i<=100;i++){
		double l=i,r=i+1;
		double s=fun(l),t=fun(r);
		if(!s){ //特判端点. 
			printf("%.2lf ",l);
			cnt++;
		}
		if(s*t<0){//如果区间内有解 
			while(r-l>1e-4){ //二分 
				double mid=(l+r)/2.0;
				if(fun(l)*fun(mid)<0)
					r=mid;
				else l=mid;
			}
			printf("%.2lf ",r);
			cnt++;
		}
		if(cnt==3) break;
	}
	puts(""); 
	return 0;
}

暴力AC代码：

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double fun(double x){
	return a*pow(x,3)+b*pow(x,2)+c*x+d;
}
int main(){
	cin>>a>>b>>c>>d;
	for(double i=-100;i<=100;i+=1e-3){
		double j=i+1e-3;
		if(fun(i)*fun(j)<=0)
			printf("%.2lf ",(i+j)/2.0);
	}
	puts("");
	return 0;
}

牛顿迭代：

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x){
	return a*pow(x,3)+b*pow(x,2)+c*x+d;
}
double f1(double x){//导数 
	return 3*a*x*x+2*b*x+c;
}
double fun(double l,double r){
	 double now=(l+r)/2.0,nt=0;
	 while(abs(now-nt)>1e-4){
	 	 nt=now-f(now)/f1(now);
	 	 swap(nt,now);//这里当前的迭代值成为下一次需要迭代的值。nt变成上一次的now 
	 }
	 return nt; 
} 
int main(){
	cin>>a>>b>>c>>d;
	double q1=(-b-sqrt(b*b-3*a*c))/(3*a);//q1,q2表示两个极值点. 
    double q2=(-b+sqrt(b*b-3*a*c))/(3*a);
    double ans1=fun(-100,q1),ans2=fun(q1,q2),ans3=fun(q2,100);
    printf("%.2lf %.2lf %.2lf\n",ans1,ans2,ans3);
    return 0;
}