题目描述
为了提高智商,ZJY开始学习概率论。有一天,她想到了这样一个问题:对于一棵随机生成的n个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?
输入格式
输入一个正整数n,表示有根树的结点数
输出格式
输出这棵树期望的叶子节点数,要求误差小于1e-9
这是啥啊?卡特兰数吧
推导明天再补(咕咕咕) ,脑袋疼
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#define int long long
using namespace std;
int n;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
main(){
n=read();
printf("%.12lf",double(n*n+n)/(4*n-2));
return 0;
}