首页 > 代码库 > 【noi 2.2_7891】一元三次方程求解（二分枚举）
【noi 2.2_7891】一元三次方程求解（二分枚举）
对于noi上的题有2中解法：
1.数据很小（N=100），可以直接打for循环枚举和判断。
2.不会“三分”，便用二分。利用“两根相差>=1”和 f(x1)*f(x2)<0，转换意思为[x,x+1]内不会包含两个根，这样枚举可以保证不漏解。因此，枚举一个个根所在的区间，再用二分枚举找出根。其中，若N=10^5，由于保留2位小数，最好精确到4位小数计算。时间复杂度 O(N)=10^5+3*log(10^4)，约为10^5。
以下附上二分的代码——
1 //20160908 Ann 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7 //#include<ctime> 8 9 //eps. epsilon 精确度10 const double eps=1e-4,INF=1e4;11 double a,b,c,d;12 13 double f(double x)14 { return a*x*x*x+b*x*x+c*x+d; }15 16 double bisec(double l,double r)17 {18 if (f(l)==0) return l;19 if (f(r)==0) return INF;20 if (f(l)*f(r)>0) return INF;21 double m;22 while (l+eps<r)23 {24 m=(l+r)/2;25 if (f(m)==0) return m;26 if (f(l)*f(m)<0) r=m-eps;27 else l=m+eps;28 }29 return l;30 }31 32 int main()33 {34 //freopen("a.in","r",stdin);35 scanf("%lf%lf%lf%lf",&a,&b,&c,&d);36 int cnt=0;37 for(double i=-100.0;i<=100.0;i+=1.0)38 {39 double x=bisec(i,i+1.0);40 if (x!=INF) cnt++,printf("%.2lf ",x);41 if (cnt==3) break;42 }43 //printf("\nTime used = %.2lf\n",(double)clock()/CLOCKS_PER_SEC);44 return 0;45 }
【noi 2.2_7891】一元三次方程求解（二分枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。