2015/04/06

【UVa】10341-Solve it! (Binary Search)




題目連結
題目大意:
給一方程式F(x)=0, input為參數,解x,或無解。

解題思路
function是一個遞減函數,所以如果F(0) < -eps, F(1)>eps,函數就不會和 0<x<1 有交集。
剩下的用binary search,因為是浮點數,要求lower_bound=upper_bound,會跑入無窮迴圈,只要相減在一個誤差內即可。



Code

?
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
#include <cstdio>
#include <cmath>
#define F(x) (p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u)
int main()
{
    int p,q,r,s,t,u;
    double lower_bound, upper_bound,mid,fofx;
    lower_bound = 0.0;
    upper_bound = 1.0;
    while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)!=EOF){
        if (F(0)<-(1e-14) || F(1)>1e-14) {
            printf("No solution\n");
        } else {
            lower_bound = 0.0;
            upper_bound = 1.0;
            while((upper_bound-lower_bound)>=1e-9){
                mid = (upper_bound+lower_bound)/2;
                fofx = F(mid);
                if(fofx>0)
                    lower_bound = mid;
                else
                    upper_bound = mid;
            }
            printf("%.4lf\n",upper_bound);
        }
    }
    return 0;
}


幾個技巧
1. 函數可以用define再代入x
2. 用binary search 找x較省時
3. 輸出精度4位:%4lf