\(\color{#0066ff}{ 題目描述 }\)

為了提高智商,ZJY開始學(xué)習(xí)概率論。有一天,她想到了這樣一個問題：對于一棵隨機(jī)生成的n個結(jié)點的有根二叉樹(所有互相不同構(gòu)的形態(tài)等概率出現(xiàn)),它的葉子節(jié)點數(shù)的期望是多少呢?

判斷兩棵樹是否同構(gòu)的偽代碼如下：

\(\color{#0066ff}{輸入格式}\)

輸入一個正整數(shù)n,表示有根樹的結(jié)點數(shù)

\(\color{#0066ff}{輸出格式}\)

輸出這棵樹期望的葉子節(jié)點數(shù),要求誤差小于1e-9

\(\color{#0066ff}{輸入樣例}\)

13

\(\color{#0066ff}{輸出樣例}\)

1.0000000001.200000000

\(\color{#0066ff}{數(shù)據(jù)范圍與提示}\)

對于30%的數(shù)據(jù)，1 ≤ n ≤ 10

對于70%的數(shù)據(jù)，1 ≤ n ≤ 100

對于100%的數(shù)據(jù)，1 ≤ n ≤ \(10^9\)

\(\color{#0066ff}{ 題解 }\)

根據(jù)概率，顯然\(ans=\frac{\sum二叉樹葉子節(jié)點個數(shù)}{二叉樹個數(shù)}\)

n個點的二叉樹個數(shù)為\(Catalan(n)\)

考慮第n個點的位置（作為葉子節(jié)點），通過手胡，可以發(fā)現(xiàn)有n個位置可以作為葉子節(jié)點，于是方案為\(Catalan(n-1)\)

因此。。。\(ans=\frac{Catalan(n-1)*n}{Catalan(n)}\)

化簡一下就是\(\frac{n*(n+1)}{4*n-2}\)

#include<bits/stdc++.h> #define LL long long LL in() {char ch; LL x = 0, f = 1;while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));return x * f; } double n; int main() {n = in();printf("%.10f", (double)((n) * (n + 1)) / (4.0 * n - 2));return 0;}

轉(zhuǎn)載于:https://www.cnblogs.com/olinr/p/10278306.html

總結(jié)

以上是生活随笔為你收集整理的P3978 [TJOI2015]概率论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。