HDU - 2199

Can you solve this equation?

Description

Now,given the equation 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y,can you find its solution between 0 and 100;

Now please try your lucky.

Input

The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has a real number Y (fabs(Y) <= 1e10);

Output

For each test case, you should just output one real number(accurate up to 4 decimal places),which is the solution of the equation,or “No solution!”,if there is no solution for the equation between 0 and 100.

Sample Input

2

100

-4

Sample Output

1.6152

No solution!

題目大意：

沒什麼好多說的了，就是求解 方程y=8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 。對于給定的y值在0~100的範圍内求x的近似解。

解題思路：

利用二分查找的方式搜尋x的近似解，這裡注意到函數是單調遞增的，可以利用這個性質快速搜尋。另外在計算Y值的時候，可以用y = (((x*x+7)*x+2)*x+3)*x+6的方法。

注意： 題目中要求精确到小數點後4位，也就要求的近似解的第5位小數必須是精确的！（不然會WrongAnswer…）

源代碼：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<sstream>
using namespace std;


bool test(double x, double y) {
    double temp = (double) * x + ;
    temp = temp*x + ;
    temp = temp*x + ;
    temp = temp*x + ;
    return (temp - y)>;
}

double binary_search(double y) {
    double l = , h = ;
    double m;
    while (h-l>) {            //近似的精度
        m = (h + l) / ;
        if (test(m, y))
            h = m;
        else
            l = m;
    }
    return m;
}

int main() {
    int times;
    double num;
    scanf("%d", &times);
    for (int ti = ; ti < times; ti++) {
        scanf("%lf", &num);
        if (num <  || num >)      //在0~100的範圍内求解
            printf("No solution!\n");
        else
            printf("%.4lf\n", binary_search(num));
    }

    return ;
}