/ Vijos / 题库 /

随机树

随机树

描述

一棵含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
1984
难度
5
分类
(无)
标签
递交数
40
已通过
14
通过率
35%
上传者

相关

在下列训练计划中:

RP++分类题库