三分法讲解

二分法适用于求单调的时候用的，就比如说排序好的数组，那是递增的或者递减的。如果像出现了下图二次函数那样的怎么求他的最值呢？

二分法早就失去了他的意义了。不过还是可以用三分法来实现的，就是二分中再来二分。比如我们定义了L和R，m = (L + R) / 2，mm = (mid + R) / 2; 如果mid靠近极值点，则R = mm；否则就是mm靠近极值点，则L = m;这样的话，极值还是可以求的。具体的还是看看题目吧。

三分查找的算法，对于求凸性或凹性函数的极值非常方便

模版：

 1 double  solve(double l,double r)
 2 {
 3 
 4         double mid,midmid;
 5         while(r - l > eps)
 6         {
 7               mid = (l + r)/2.0;
 8              midmid = (r + mid)/2.0;
 9 
10 
11             if(f(mid) <= f(midmid))// f 就算函数值
12                 r = midmid;
13             else  l = mid;
14         }
15     return f(l);
16 }

只要知道函数怎么求，套模版就可以了；

zoj 3203 Light Bulb

Light Bulb

Time Limit: 1 Second Memory Limit: 32768 KB

Compared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bulb in his house. Every night, he is wandering in his incommodious house, thinking of how to earn more money. One day, he found that the length of his shadow was changing from time to time while walking between the light bulb and the wall of his house. A sudden thought ran through his mind and he wanted to know the maximum length of his shadow.

Input

The first line of the input contains an integer T (T <= 100), indicating the number of cases.

Each test case contains three real numbers H, h and D in one line. H is the height of the light bulb while h is the height of mildleopard. D is distance between the light bulb and the wall. All numbers are in range from 10^-2 to 10³, both inclusive, and H - h >= 10^-2.

Output

For each test case, output the maximum length of mildleopard's shadow in one line, accurate up to three decimal places..

Sample Input

Sample Output

1.000
0.750
4.000

View Code

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<set>
 8 #include<map>
 9 #define Min(a,b)  a>b?b:a
10 #define Max(a,b)  a>b?a:b
11 #define CL(a,num)  memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 50010
14 #define eps  1e-6
15 #define ll long long
16 using namespace std;
17 double a[maxn],w[maxn];
18 double   H,h,d;
19 double f(double pos)
20 {
21      return  ((d - pos)*h - (H - h)*pos)/(d - pos) + pos;
22 
23 }
24 double  solve(double l,double r)
25 {
26 
27         double mid,midmid;
28         int size = 100;
29         while(size--)
30         {
31               mid = (l + r)/2.0;
32              midmid = (r + mid)/2.0;
33 
34 
35             if(f(mid) >= f(midmid))// f 就算函数值
36                 r = midmid;
37             else  l = mid;
38         }
39     return f(l);
40 }
41 int main()
42 {
43     int t,i;
44     scanf("%d",&t);
45     int cas = 0;
46 
47     while(t--)
48     {
49         double ans = 0 ;
50        scanf("%lf %lf %lf",&H,&h,&d);
51 
52 
53        ans = solve(0,d*(h/(H*1.0)));
54        printf("%.3lf\n",ans );
55     }
56 }

三分法 讲解

三分法讲解