题意是给定一长为 L 的木棒,每次任意切去一部分直到剩余部分的长度不超过 D,求切割次数的期望。
若木棒初始长度不超过 D,则期望是 0.000000;
设切割长度为 X 的木棒切割次数的期望是 F(X).
则 F(X) = F(切割点位置为 0 ~ D) + F(切割点位置为 D ~ X ) + 1;(此处的 +1 是指首次切割产生的次数)
而 F(切割点位置为 0 ~ D ) = 0;(因为已无需再切割)
令下一次切割点的位置为 T,
F(切割点位置为 D ~ X ) = 在D~X上积分 ( 1 / X ) * F( T ) dT ;(在长度为 X 的木棒上选择到任何一点切割的概率为 1 / X)
F( X ) = F(切割点位置为 0 ~ D) + F(切割点位置为 D ~ X ) + 1 = 0 + 在D~X上积分 ( 1 / X ) * F( T ) dT + 1
两边求导:F‘( X ) = - ( 1 / X² ) * ∫ F( T ) dT + F( X ) / X;(积分区间均为 D ~ X)
又: F( X ) = ∫ ( 1 / X ) * F( T ) dT + 1
得: - ( 1 / X² ) * ∫ F( T ) dT = ∫ ( 1 / X ) * F( T ) dT / ( -1 / X ) = ( F(X) - 1 ) / ( -1 / X )
则: F’( X ) = - ( 1 / X² ) * ∫ F( T ) dT + F( X ) / X = ( F(X) - 1 ) / ( -1 / X ) + F( X ) / X = 1 / X
即: F( X ) = ln( X ) + C ( C为常数 )
由 F( D ) = 1,得:C = 1 - ln( D )
得:F( L ) = ln( L ) + 1 - ln( D ) = log( L / D ) + 1.
代码如下:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int t;
6 double l,d;
7 scanf("%d",&t);
8 while(t--)
9 {
10 scanf("%lf%lf",&l,&d);
11 if(l<=d) puts("0.000000");
12 else printf("%.6lf\n",log(l/d)+1);
13 }
14 return 0;
15 }
View Code
感谢这些博客的作者:
https://blog.csdn.net/jay__bryant/article/details/81188557
https://blog.csdn.net/blue_skyrim/article/details/53262572
https://www.cnblogs.com/Yumesenya/p/7657820.html
转载于:https://www.cnblogs.com/Taskr212/p/9740728.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)