程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【noi 2.2_7891】一元三次方程求解(二分枚舉),noi2.2_7891

【noi 2.2_7891】一元三次方程求解(二分枚舉),noi2.2_7891

編輯:C++入門知識

【noi 2.2_7891】一元三次方程求解(二分枚舉),noi2.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 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved