当前位置:网站首页>P1024 solution of univariate cubic equation (dichotomy & Violence & Newton iteration)

P1024 solution of univariate cubic equation (dichotomy & Violence & Newton iteration)

2021-08-10 08:04:46 wx6110fa547fd20

P1024 Solve the cubic equation of one variable ( Two points & violence & Newton iteration )

  Subject portal

The question : Given a cubic equation of one variable, solve three roots .

Ideas :sol 1: Enumeration of each length of 1 The range of , Dichotomize each interval . sol 2: Violence from -100, 100 Every time 1e-3 Enumeration .
sol 3: Find the two extreme points of the function , Then it is divided into three intervals for Newton iteration .

Two points AC Code :

#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){ // Special judgment endpoint . 
			printf("%.2lf ",l);
			cnt++;
		}
		if(s*t<0){// If there is a solution in the interval  
			while(r-l>1e-4){ // Two points  
				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.

violence AC Code :

#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.

Newton iteration :

#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){// derivative  
	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);// Here, the current iteration value becomes the value of the next iteration .nt Become the last now 
	 }
	 return nt; 
} 
int main(){
	cin>>a>>b>>c>>d;
	double q1=(-b-sqrt(b*b-3*a*c))/(3*a);//q1,q2 Represents two extreme points . 
    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://chowdera.com/2021/08/20210810080205586E.html

随机推荐