当前位置:网站首页>P1024 一元三次方程求解 (二分&暴力&牛顿迭代)

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

2021-08-10 08:02:41 wx6110fa547fd20

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;
} 

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.

暴力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;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.

牛顿迭代:

#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;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328291

随机推荐