zcmimi's blog
查看原题

点击跳转

f_n表示n个节点可以构成的二叉树的个数,g_n表示n个节点可以构成的二叉树的叶子节点的总数

打表: 可以发现g_n=nf_{n-1}

证明: 对于每棵有n个节点的二叉树,若它有k个叶子节点,删去后可以得到kn-1个节点的二叉树,而这kn-1个节点的二叉树每棵都有n个位置可以放置新的叶子节点

f_1=1\\ f_n=\sum_{i=1}^{n-1}f_if_{n-i-1}

f其实就是卡特兰数

代入ans=\frac{g_n}{f_n}得到\frac{n(n+1)}{2(2n-1)}

#include<cstdio>
int main(){
  double n;
  scanf("%lf",&n);
  printf("%.12f",n*(n+1)/2/(2*n-1));
}
LG 3978 [TJOI2015]概率论
comment评论
Search
search