【noi 2.2_7891】一元三次方程求解(二分枚举+输…
2018-06-17 23:48:53来源:未知 阅读 ()
对于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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:什么是虚继承?
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【做题笔记】[NOIOJ,非NOIp原题]装箱问题 2020-02-14
- P2052 [NOI2011]道路修建 2019-10-29
- CSP(noip)中的简单对拍写法 2019-10-25
- P2704 [NOI2001]炮兵阵地 (状压DP) 2019-10-12
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash