三分搜索算法&hdu 2899 Strange fuction

三分搜索算法&hdu 2899 Strange fuction

三分搜索算法： 整个算法在最坏情况下的计算时间复杂性为O(log3(n))，每执行一次算法的循环，待搜索数组的大小减少三分之二。对具体n值的数组进行搜索时，虽然三分搜索法在数据搜索时，循环次数减少了，但在一次循环中最坏情况下需要进行数据的两次比较，由于充分利用了待搜索数组的最大数和最小数，在搜索方向的选择上灵活性更强。这是因为三分算法稍加变化可得从大到小方向上的三分法的搜索算法或从小到大方向上的三分搜索算法。 从小到大方向上的三分：

int ternarysearch(int a[]，int low，int high，int x){ if(higha[mia2]) res=ternarysearch(a,mid2+1,high,x); else res=ternarysearch(a,midl+1,mid2-1,x); } return res; }

应用： hdu 2899 Strange fuction ： ​​​ Description

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.

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 only one real numbers Y.(0 < Y <1e10)

Output

Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100.

Sample Input

2 100 200

Sample Output

-74.4291 -178.8534

分析：先对函数x一阶求导，然后得到：42x^6+48x^5+21x^2+10x-y=0.求出x(显然不能直接算出，找点带入计算吧，所以和二分，三分联系在一起了）。它就是极小值。再带入函数表达式求出结果即可。

#include #include#includeusing namespace std;double y,x; // F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*xdouble cal(double m){ return 42*pow(m,6)+48*pow(m,5)+21*pow(m,2)+10*m;}double cal_t(){ return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;}double ternarysearch(double low,double high){ double mid1=low+(high-low)/3,mid2=high-(high-low)/3; double re1=cal(mid1),re2=cal(mid2),ans; if(abs(y-re1)<1e-6)ans=mid1; else if(re1>y)ans=ternarysearch(low,mid1); else if(abs(y-re2)<1e-6)ans=mid2; else if(re2>t; while(t--){ scanf("%lf",&y); x=-1; x=ternarysearch(0,100); printf("%.4lf\n",cal_t()); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。