P3978 [TJOI2015] 概率论

题目描述

为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 n 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：

算法 1 ​Check(T1,T2)

        Require:  两棵树的节点                                if  T1=null or T2=null then 

                        return  T1=null and T2=null

                        else

                                return Check(T1→leftson,T2→leftson) 

                                        and Check(T1→rightson,T2→rightson)

                        endif​​

输入格式

输入一个正整数 n，表示有根树的结点数。

输出格式

输出这棵树期望的叶子节点数，要求误差小于 。

输入输出样例

输入 #1

1

输出 #1

1.000000000

输入 #2

3

输出 #2

1.200000000

说明/提示

数据范围

对于 30% 的数据，1≤n≤10。

对于 70% 的数据，1≤n≤100。

对于 100% 的数据，1≤n≤109。

思路

打表+数学

没啥好说的

代码也很短

但是一定要开long double

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{long double n;cin>>n;cout<<fixed<<setprecision(9)<<(n*n+n)/(4*n-2);
}

AC记录