HDU 2899 Strange fuction(二分||三分)

题目链接~~>

做题感悟：这题和 2199 那题差不多。

解题思路：一、题目让求函数的最小值，首先应该分析函数图象。将函数求导得  f(x) ’ =  42 * x^6 + 48 * x^5 + 21 * x^2 + 10*x - y,因为 y 大于 0 所以假设存在 k 使f(x)'= 0,所以当0<=x<k 时f（x）’小于0,原函数在0<=x<k单调递减。在 k<x<=100 单调递增。所以函数先递减再递增。所以求导后求出x值然后带入原函数即为最小值。二、也可以用三分解决。

代码（二分）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      double n ;
     
    
   

    

     

    
    

     

      double find(double x) // 求导后的式子
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return 42.0*pow(x,6)+48.0*pow(x,5)+21.0*pow(x,2)+10.0*x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      double binary_search(double x,double y)// 二分求 x 的值
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double mid,mx ;
     
    
   

    

     

    
    

     
 while(x<=y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mid=x+(y-x)/2.0 ;
     
    
   

    

     

    
    

     

       mx=find(mid) ;
     
    
   

    

     

    
    

     
 if(fabs(mx-n)<=0.0001)
     
    
   

    

     

    
    

     
 return mid ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       mx > n ?  y=mid : x=mid ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void print(double x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double mx=6.0*pow(x,7)+8.0*pow(x,6)+7.0*pow(x,3)+5.0*pow(x,2)-n*x ;
     
    
   

    

     

    
    

     
 printf("%.4lf\n",mx) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lf",&n) ;
     
    
   

    

     

    
    

     
 double mx=binary_search(0,100) ;
     
    
   

    

     

    
    

     

       print(mx) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（三分）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double EPS = 0.00001 ;
     
    
   

    

     

    
    

     

      double y ;
     
    
   

    

     

    
    

     

      double find(double x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return 6.0*pow(x,7)+8.0*pow(x,6)+7.0*pow(x,3)+5.0*pow(x,2)-y*x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      double third_search(double x,double y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 double mid,midd ;
     
    
   

    

     

    
    

     
 while(x+EPS<y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mid=(y+x)/2.0 ;
     
    
   

    

     

    
    

     

       midd=(y+mid)/2.0 ;
     
    
   

    

     

    
    

     
 if(find(mid)<find(midd))
     
    
   

    

     

    
    

     

       y=midd ;
     
    
   

    

     

    
    

     
 else x=mid ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return find(mid) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lf",&y) ;
     
    
   

    

     

    
    

     
 printf("%.4lf\n",third_search(0,100)) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/17526789