資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C/C++程式計算第n個卡塔蘭數？
卡塔蘭數是一個數列。卡塔蘭數構成一系列自然數，出現在各種計數問題中，通常涉及遞迴定義的物件。
Cn是長度為2n的Dyck詞的個數。Dyck詞是一個由n個X和n個Y組成的字串，其任何初始段的Y的個數都不超過X的個數。例如，以下是長度為6的Dyck詞：
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
將符號X重新解釋為左括號，將Y解釋為右括號，Cn計算包含n對正確匹配的括號的表示式的個數。
((())) ()(()) ()()() (())() (()())
Cn是n+1個因子可以完全括號化的不同方法的個數（或應用二元運算子的n種關聯方法的個數）。例如，對於n=3，我們有以下五種不同的四因子括號化方法：
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
二元運算子的連續應用可以用滿二叉樹表示。（如果每個頂點要麼有兩個子節點，要麼沒有子節點，則根二叉樹是滿的。）因此，Cn是具有n+1個葉節點的滿二叉樹的個數。
示例
輸入 - 6
輸出- 1 1 2 5 14 42
解釋
對於n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...，前幾個卡塔蘭數是：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,
示例
#include<iostream>
using namespace std;
long int catalan( int n) {
if (n <= 1){
return 1;
}
long int result = 0;
for (int i=0; i<n; i++){
result += catalan(i)*catalan(n-i-1);
}
return result;
}
int main(){
for (int i=0; i<6; i++)
cout << catalan(i) << " ";
return 0;
}輸出
1 1 2 5 14 42
更新於：2019年8月13日
501 次檢視
廣告