HDUOJ2199 Can you solve this equation?

Canyousolvethisequation?

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)
TotalSubmission(s):322AcceptedSubmission(s):148


ProblemDescription
Now,giventheequation8*x^4+7*x^3+2*x^2+3*x+6==Y,canyoufinditssolutionbetween0and100;
Nowpleasetryyourlucky.


Input
ThefirstlineoftheinputcontainsanintegerT(1<=T<=100)whichmeansthenumberoftestcases.ThenTlinesfollow,eachlinehasarealnumberY(fabs(Y)<=1e10);


Output
Foreachtestcase,youshouldjustoutputonerealnumber(accurateupto4decimalplaces),whichisthesolutionoftheequation,or“Nosolution!”,ifthereisnosolutionfortheequationbetween0and100.


SampleInput
2
100
-4


SampleOutput
1.6152
Nosolution!

题目分析:

很明显,这是一个2分搜索的题目, 但是注意下题目的数据!! 1e10 的实数!! 而且精度是要求在 0.0001 . 所以就算是2分数据量依旧比较大,如果用
通常的递归方法吗很遗憾 , RE了............. 没办法, 只能循环了.
下面的是递归 RE 的代码 :

#include <iostream>
#include <cmath>
using namespace std;
#define POW(x) ( (x) * (x) )
#define POW3(x) ( POW(x) * (x) )
#define POW4(x) ( POW(x) * POW(x) )
double y = 0;
bool douEql ( double a,double b )
{
if ( fabs( a - b ) <= 1e-6  )
return  true;
return false;
}
double cal ( double n )
{
return 8.0 * POW4(n) + 7 * POW3(n) + 2 * POW(n) + 3 * n + 6 ;
}
double biSearch ( double l, double r )
{
if ( douEql ( l,r ) )
{
if ( douEql ( y, cal ( l ) ) )
return l;
return -1;
}
double mid = ( l + r ) / 2.0;
if ( douEql ( y, cal ( mid ) ) )
return mid;
else if ( cal ( mid ) > y )
return biSearch ( l,mid - 0.0001 );
else
return biSearch ( mid + 0.0001, r );
}
int main ()
{
int T;
scanf ( "%d",&T );
while ( T -- )
{
scanf ( "%lf",&y );
if ( cal(0) >= y && cal(100) <= y )
{
printf ( "No solution!\n" );
continue;
}
double res = biSearch ( 0.0, 100.0 );
if ( res == -1 )
printf ( "No solution!\n" );
else
printf ( "%.4lf\n",res );
}
return 0;
}

AC代码如下:

#include <iostream>
#include <cmath>
using namespace std;
#define POW(x) ( (x) * (x) )
#define POW3(x) ( POW(x) * (x) )
#define POW4(x) ( POW(x) * POW(x) )
double y = 0;
double cal ( double n )
{
       return 8.0 * POW4(n) + 7 * POW3(n) + 2 * POW(n) + 3 * n + 6 ;
}
int main ()
{
    int T;
    scanf ( "%d",&T );
    while ( T -- )
    {
          scanf ( "%lf",&y );
          if ( cal(0) > y || cal(100) < y )
          {
               printf ( "No solution!\n" );
               continue;
          }
          double l = 0.0, r = 100.0,res = 0.0;
          while ( r - l > 1e-6 )
          {
                double mid = ( l + r ) / 2.0;
                res = cal ( mid );
                if ( res > y )
                     r = mid - 1e-6;    
                else 
                     l = mid + 1e-6;
          }
          printf ( "%.4lf\n",( l + r ) / 2.0 ); 
    }
    return 0; 
}