紫色网站模板,会所网站模板,外贸新品开发网站,php可以做网站吗题干#xff1a;
蒜头君在玩一个战争模拟游戏#xff0c;他有高度为 1,2,3,\ldots ,n1,2,3,…,n 的炮台各一个#xff0c;他需要把这 nn 个炮台从左往右排成一行#xff0c;并且炮口都朝向右边。
在这个游戏中#xff0c;所有炮台发射的炮弹会摧毁前方所有高度比自己低的…题干
蒜头君在玩一个战争模拟游戏他有高度为 1,2,3,\ldots ,n1,2,3,…,n 的炮台各一个他需要把这 nn 个炮台从左往右排成一行并且炮口都朝向右边。
在这个游戏中所有炮台发射的炮弹会摧毁前方所有高度比自己低的炮台。每当蒜头君把 nn 个炮台排成一行后可能会有一些炮台被摧毁。举个例子当前有 55 个炮台从左到右高度分别为 2,1,3,5,42,1,3,5,4往右发射炮弹后高度为 44 的炮台被高度为 55 的摧毁高度为 11 的炮台被高度为 22 的炮台摧毁最后只会剩下 2,3,52,3,5 这三个炮台。
现在蒜头君想知道如果随机地摆放这 nn 个炮台最后剩下炮台个数的期望是多少比如 n2n2 时有两种摆放方式高度序列分别为 1,21,2 和 2,12,1前者最后剩下 22 个炮台后者最后剩下一个炮台因此期望为 {(21)\over 2}1.50002(21)1.5000。
请你求出 n2019n2019 时剩下炮台个数的期望保留四位小数。
样例输入复制
无
样例输出复制
无 解题报告
有n个位置不同的位置摆放不同的数共有 n! 的排列。对于留存的炮台数的期望可以对每一个数留存下来的概率进行累加从而得到期望值。比如最大的数无论放在哪留存下的概率都为1。第二大的数如果最大的数放在其前面会被摧毁而放在后面不会被摧毁所以留存的概率为。最小的数除了放在第一个位置其余位置都会被摧毁所以留存的概率为所以期望为。代入n2019即可算出答案
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
int main()
{double ans 0;int n 2019;for (int i 1; i n; i) {ans 1.0 / i;}printf(%.4f\n, ans);return 0;}
