#2294. 概率论

    ID: 2294 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest2466来源:qoj.ac数据:公开样例动态规划数学

概率论

概率论

题目描述

NOI 2015天津市代表队选拔赛day2 C 概率论 • 输入输出文件: prob.in/prob.out • 源文件名: prob.cpp/prob.c/prob.pas • 时间限制: 1s 内存限制: 128M 题目描述 为了提高智商,ZJY开始学习概率论。有一天,她想到了这样一个问题: 对于一棵随机生成的n个结点的有根二叉树(所有互相不同构的形态等概率出 现),它的叶子节点数的期望是多少呢? 判断两棵树是否同构的伪代码如下: 算法1: boolCheck(T1, T2) Require: 两棵树的节点T1,T2 if T1 == null || T2 == null then return T1 == null && T2 == null else return Check(T1−> leftson, T2−> leftson) && Check(T1−> rightson, T2−> rightson) end if 输入 输入一个正整数n,表示有根树的结点数。 输出 输出这棵树期望的叶子节点数,要求误差小于1e−9 样例输入1 1 样例输出1 1.000000000 样例输入2 3 6

NOI 2015天津市代表队选拔赛day2 样例输出2 1.200000000 数据范围 对于30%的数据,1 ≤n ≤10 对于70%的数据,1 ≤n ≤100 对于100%的数据,1 ≤n ≤109 7

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
1.000000000