UVa-10341 : Solve It
問題概要
区間[0,1]で単調減少な関数が与えられるので根を求める問題。
解法
二分探索。浮動小数点数のせいで端点の処理が面倒くさい。
acceptされたコード
計算量O(iter)。
#include <cstdio> #include <cmath> using namespace std; double EPS = 1e-9; int p, q, r, s, t, u; double calc(double x){ return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u; } void solve(){ double low = 0.0, high = 1.0; double lval = calc(low), hval = calc(high); if( (fabs(lval) < EPS && fabs(hval) < EPS) || lval < -EPS || hval > EPS){ puts("No solution"); return ; } for(int loop=0; loop<100; loop++){ double mid = (high + low) / 2.0; if( calc(mid) > 0 ){ low = mid; } else{ high = mid; } } printf("%.4f\n", low + EPS); } int main(){ while(scanf("%d%d%d%d%d%d", &p, &q, &r, &s, &t, &u) != EOF){ solve(); } return 0; }