大致题意： 问你一棵(n)个节点的有根二叉树叶节点的期望个数。
大致思路
看到期望，比较显然可以想到设(num_i)为(i)个节点的二叉树个数，(tot_i)为所有(i)个节点的二叉树的叶节点总数。
则答案显然为(frac{tot_i}{num_i})。
而(num_i)其实就是一个卡特兰数（这其实就是(NOIP2018)提高组初赛卷中(T8)的(A)选项改正后的结果啊），故可以得到(num_i=(2n)!/(n+1)!/n!)。
通过找规律可以发现(tot_i=ncdot num_{i-1})。
于是答案就是(frac{ncdot num_{i-1}}{num_i}=frac{ncdot(2n-2)!/n!/(n-1)!}{(2n)!/(n+1)!/n!}=frac{n}{2n(2n-1)/(n+1)/n}=frac{n(n+1)}{4n-2})。
代码也十分简洁。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
scanf("%d",&n),printf("%.9lf",1.0*n*(n+1)/(4LL*n-2));//求出n(n+1)/(4n-2)
return 0;
}