自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:55:09，当前版本为作者最后更新于2018-06-02 18:51:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

...这道题比楼下说的还要神奇——它不仅代码好写，证明也不用楼下说的那么麻烦。

首先，我们令$f_n$表示$n$个点的二叉树个数；$g_n$表示$n$个点的所有$f_n$棵二叉树的叶节点总数。

找规律第一步当然是打表啦~写个爆搜或者手算都可以。

我们发现一个规律：$g_n=nf_{n-1}$。

证明这个规律其实超级简单：

• 对于每棵$n$个点的二叉树，如果里面有$k$个叶节点，那么我们分别把这$k$个叶子删去会得到$k$棵$n-1$个点的二叉树；
• 而每棵$n-1$个点的二叉树恰好有$n$个位置可以悬挂一个新的叶子，所以每棵$n-1$个点的二叉树被得到了$n$次；
• 综上，我们即可得出结论：所有$n$个点的二叉树的叶子个数和等于$n-1$个点的二叉树个数$\times n$。

那么我们只需要求出$f$即可。而$f$的递推式可以通过枚举左子树结点个数得到：

边界是$f_1=1$。应该可以一眼看出来这是Catalan数列（其实一看那个$1,2,5,14,42$就应该知道，滑稽）

于是答案即为

代入卡特兰数的通项公式$f_n=\frac{\binom{2n}{n}}{n+1}$很容易就得到上式等于$\frac{n(n+1)}{2(2n-1)}$。

代码：

#include <cstdio>

int main() {
  double n;
  scanf("%lf", &n);
  printf("%.12f", n * (n + 1) / (2 * (2 * n - 1));
  return 0;
}