【UVa】10341-Solve it!

題目連結
題目大意:
給一方程式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

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s