随机树
测试数据来自 system/1984
描述
一棵含n个叶结点的二叉树可以通过如下方式生成。初始时只有根结点。首先,将根结点展开(本题中的展开是指给一个叶添上左、右两子);然后,等概率的随机将两个叶结点中的一个展开;之后,每次在当前二叉树的所有叶结点中,等概率地随机选择一个,将其展开。不断地重复这一操作,直至产生n个叶结点为止。
对于按这种方式随机生成的一棵含n个叶节点的二叉树,求(1)叶结点平均深度的数学期望值;(2)树深度的数学期望。约定根结点的深度为0。
格式
输入格式
输入仅有一行,包含两个正整数q和n,分别表示问题编号以及叶结点的个数。
输出格式
输出仅有一行,包含一个实数d,四舍五入精确到小数点后6位。如果q=1,则d表示叶结点平均深度的数学期望值;如果q=2,则d表示树深度的数学期望。
样例1
样例输入1
1 4
样例输出1
2.166667
样例2
样例输入2
2 4
样例输出2
2.666667
样例3
样例输入3
1 12
样例输出3
4.206421
样例4
样例输入4
2 12
样例输出4
5.916614
限制
有\(20\%\)的数据,\(q=1\),且\(2\le n\le 10\);
有\(30\%\)的数据,\(q=1\),且\(2\le n\le 100\);
有\(20\%\)的数据,\(q=2\),且\(2\le n\le 10\);
有\(30\%\)的数据,\(q=2\),且\(2\le n\le 100\)。
来源
SHTSC 2012 Day1
信息
- ID
- 1916
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者