题目描述

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

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

$$\def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T1,T2) \\ \hline 1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\\ 2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\\ 4&\qquad\textbf{else}\\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \\ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\\ 6&\qquad\textbf{endif}\\ \hline \end{array}$$

输入格式

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

输出格式

输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$ 。

1.000000000

1.200000000

数据范围

对于 $30\%$ 的数据， $1 \le n \le 10$ 。

对于 $70\%$ 的数据， $1 \le n \le 100$ 。

对于 $100\%$ 的数据， $1 \le n \le 10^9$ 。

题目描述

输入格式

输出格式

数据范围

相关推荐