【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】一元三次方程求解（二分枚举+输出程序运行时间）

最新文章

热门文章