为了提高智商,ZJY 开始学习概率论。有一天,她想到了这样一个问题:对于一棵随机生成的 n 个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?
判断两棵树是否同构的伪代码如下:
对于 100% 的数据,1≤n≤109。
对于每棵 n 个点的二叉树,设它有 k 个叶子,那么把这 k 个叶子分别删去就能得到 k 棵 n−1 个点的二叉树。
由于每一颗 n−1 个点的二叉树都能悬挂 n 个新的叶子,所以每一棵 n−1 个点的二叉树都会被上面的过程得到 n 次。
由于 n 个点的有根二叉树有 n+1(n2n) 种,所以 n 个点的所有二叉树总共有 (n−12n−2) 个叶子,期望有 n+1(n2n)(1n−12n−2)=n!2(2n)!(n+1)(n−1)!2(2n−2)!=2n(2n−1)(n+1)n2=2(2n−1)n(n+1) 个叶子。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main()
{
scanf("%d",&n);
printf("%.9Lf\n",n*(n+1)/(long double)(2*(2*n-1)));
return 0;
}