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记录