11082?完全二叉樹的種類

時間限制:800MS? 內(nèi)存限制:1000K
提交次數(shù):0 通過次數(shù):0

題型: 編程題???語言: G++;GCC;VC

?

Description

構(gòu)造n個(2<=n<=20)葉結(jié)點的的完全二叉樹(完全二叉樹意味著每個分支結(jié)點都有2個兒子結(jié)點),有多少種構(gòu)造方法?注意:不改變n個結(jié)點的相對順序,左右兒子不調(diào)換.例如: 4個葉子節(jié)點A1,A2,A3,A4，可構(gòu)造出如下完全二叉樹，共5種。 再例如:5個葉子結(jié)點,A1,A2,A3,A4,A5，可構(gòu)造出如下若干種完全二叉樹形狀，像這樣的完全二叉樹共有14種(下圖 并未全部列出)。

輸入格式

輸入n,表示構(gòu)造的完全二叉樹有n個葉結(jié)點(2<=n<=20)。

輸出格式

輸出構(gòu)造的完全二叉樹的種類。

?

輸入樣例

5

?

輸出樣例

14

?

?

提示

作者

?zhengchan　　

　　

　　題解：

　　首先看一般的遞推公式：題目規(guī)定是構(gòu)造完全二叉樹，那么不論怎么構(gòu)造，根節(jié)點的左子樹和右子樹也都是完全二叉樹。那么含有n個葉子的完全二叉樹的構(gòu)造方案數(shù)就等于左子樹的方案數(shù)乘以右子樹的方案數(shù)。列舉所有左右子樹的分布情況；得到公式f(n)=f(1)f(n-1)+f(2)f(n-2)+...+f(i)f(n-i)+...+f(n-1)f(1). 復雜度為O(n^2)，不僅復雜度不低，而且實現(xiàn)較復雜，遞歸時還得用額外的空間記錄已經(jīng)計算過的值。

?

　　現(xiàn)在從另一個角度分析。先假設(shè)取一個最小結(jié)點單位（即一個結(jié)點下接兩個葉子）。 然后構(gòu)造一棵含有n-1個葉子的完全二叉樹；再將剛提到的最下結(jié)點單位替換n-1個葉子中的任何一個，就是一棵含有n個葉子的完全二叉樹，這種情況的方案數(shù)為f(2)f(n-1)*(n-1)。 以此類推所有情況可得出n個葉子的完全二叉樹方案數(shù)有：f(2)f(n-1)*(n-1)+f(3)f(n-2)*(n-2)+...+f(i)f(n-i+1)*(n-i+1)+...+f(n-1)f(2)*2。 把首尾合并得：f(2)f(n-1)*(n+1)+f(3)f(n-2)*(n+1)+...+f(i)f(n-i+1)*(n+1) | i<=n/2. ?但這并不是正確的f(n)公式，因為沒有去除重復的情況。 在n>3時這個式子是一定只有n-2項的（指沒首尾合并前），而每一項的情況都會在其他的n-3項中重復一次（如果不清楚可以實際畫f(4)或f(5)的情況看下）。 所以要除以重復的n-2。 那么最終得到公式f(n)=[f(2)f(n-1)+f(3)f(n-2)+...+f(i)f(n-i+1)]*(n+1)/(n-2) | i<=n/2。

?

　　現(xiàn)在看會最開始的那個公式，將n+1代入得：f(n+1)=f(1)f(n)+f(2)f(n-1)+...+f(i)f(n-i+1)+...f(n)f(1)。 去掉首尾的f(1)f(n)和f(n)f(1)。中間的這個式子，正好就是后面推的f(n)公式大括號部分的“一半”。將該部分乘以二則有f(2)f(n-1)+...+f(i)f(n-i+1)+...+f(n-1)f(2)=f(n)*2(n-2)/(n+1)。 ?由f(1)=1，所以f(n+1)=2f(n)+f(n)*2(n-2)/(n+1). ?最后化簡得到公式f(n)=f(n-1)*(4n-6)/n.

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <algorithm> 6 #include <queue> 7 #include <map> 8 #include <stack> 9 #include <set> 10 #include <cstdlib> 11 using namespace std; 12 typedef long long ll; 13 14 ll catalan(int n) 15 { 16 if(n==1)return 1; 17 return catalan(n-1)*(4*n-6)/n; 18 } 19 int main() 20 { 21 int n; 22 scanf("%d",&n); 23 printf("%lld\n",catalan(n)); 24 return 0; 25 }

?

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

總結(jié)

以上是生活随笔為你收集整理的11082 完全二叉树的种类 O(n) 卡特兰数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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