HDU2199 ZJNU1681 杰哥的难题1 二分查找

Description

有一天，杰哥在做高数的时候遇到下面这道难题，杰哥百思不得其解。于是他向聪明的程序员你来求助。你能帮助他解决这道题吗？

 

对于给定的Y，求8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y这个方程，在0<=x<=100中的实数解。

Input

第一行包含一个正整数T(1<=T<=100)，代表有多少组测试样例。

接下来T行，每行一个实数Y(fabs(Y)<=1e10)。

Output

对于每一个测试样例，输出一个实数(小数点后保留4位)，代表该方程的解。如果该方程在0~100没有解，则输出"No solution!"

Sample Input

2

100

-4

Sample Output

1.6152

No solution!

Hint

二分

代码区：

#include<iostream>
#include<cmath>
using namespace std;
double k=1e-8; //定义精度，当high-low<k时停止二分（为1e-7时好像不太行）
double f(double x) //定义函数，返回方程的解
{
    return 8*pow(x,4)+7*pow(x,3)+2*pow(x,2)+3*x+6;
}

int main()
{
    int n;
    double x,y;
    double low,high,mid;
    cin>>n; //输入测试样例数量
    while(n--)
    {
       cin>>y;
       low=0;high=100; //初始化
       if(y>f(high)||y<f(low))  //当f（0）和f（100）都不满足条件时
       {
            cout<<"No solution!"<<endl;
            continue;//退出此次循环，进入下一组数据
       }
       while(high-low>k) //精度要求
       {
           mid=(low+high)/2;
           double t=f(mid);//中间值
           if(t<y)low=mid+k;
           //当中间数小于y时，说明解在这个数后面，将low变为mid+k缩小范围
           else high=mid-k;//反之
       }
     printf("%.4lf\n",mid);//保留后四位小数
    }
  return 0;
}

新手上路，有错请指正