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

2021-08-10 08:04:46

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

https://chowdera.com/2021/08/20210810080205586E.html