首页 > 代码库 > HDU 2899 Strange fuction (求导解方程+二分查找)

HDU 2899 Strange fuction (求导解方程+二分查找)

题目链接:click here~~

【题目大意】:

Now, here is a fuction:  F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)  Can you find the minimum value when x is between 0 and 100.给你一个方程,求其给定范围内的最小值。

【解题思路】:

首先,对该式子。求一阶导,得到F‘(x) = 42*x^6 + 48*x^5+21*x^2+10*x-y。这里,我们忽略y,可发现,导函数42*x^6 + 48*x^5+21*x^2+10*x是递增的。范围在[0, 10^13],
所以我们能够发现不管y取什么值,总能够找到x1∈[0, 100]。使F‘(x1)=0,又由于此时x∈[0, x1]时。函数递减(导函数小于零,原函数递减,反之,递增)。x∈[x1, 100]时。函数递增。所以F(x1)便是极小值,也是最小值。

综上。先对F‘(x)使用二分法就可以,最后结果输出F(x)的值就可以

代码:

 
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int t;
double y;
double fun(double x)
{
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
double func(double x)
{
    return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y;
}
int main()
{
    //freopen("1.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf",&y);
        double ll=0,rr=1e2,mid;
        while(ll+eps<=rr){
            mid=(ll+rr)/2;;
            if(func(mid)>0) rr=mid;
             else ll=mid;
        }
        printf("%.4f\n",fun(mid));
    }
    return 0;
}

HDU 2899 Strange fuction (求导解方程+二分查找)