資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究第 n 個卡特蘭數的 C 程式
給定一個整數 n；任務是找到第 n 個位置上的卡特蘭數。因此，在編寫程式之前，我們必須知道什麼是卡特蘭數？
卡特蘭數是自然數的序列，以各種計數問題的形式出現。
卡特蘭數 C0、C1、C2、… Cn 由以下公式得出：
$$c_{n}=\frac{1}{n+1}\binom{2n}{n} = \frac{2n!}{(n+1)!n!}$$
對於每個 n = 0、1、2、3、…，前幾個卡特蘭數是 **1、1、2、5、14、42、132、429、1430、4862、…**
因此，如果我們輸入 n = 3，則程式應該輸出 5
**卡特蘭數的一些應用**：
- 計算具有 n 個鍵的二叉搜尋樹的可能數量。
- 查詢包含 n 對正確匹配的括號的表示式的數量。例如，對於 n = 3，可能的括號表示式將是 ((()))、()(())、()()()、(())()、(()())。
- 查詢連線圓上點的不同弦的方法數量，等等。
示例
Input: n = 6 Output: 132 Input: n = 8 Output: 1430
**我們將用來解決給定問題的方案**：
- 輸入 n。
- 檢查 n <= 1，如果是，則返回 1
- 迴圈從 i=0 到 i
- 對於每個 i，設定 result = result + (catalan(i)*catalan(n-i-1))
- 返回並列印結果。
演算法
Start Step 1 -> In function unsigned long int catalan(unsigned int n) If n <= 1 then, Return 1 End if Declare an unsigned long variable res = 0 Loop For i=0 and i<n and i++ Set res = res + (catalan(i)*catalan(n-i-1)) End Loop Return res Step 2 -> int main() Declare an input n = 6 Print "catalan is : then call function catalan(n) Stop
示例
#include <stdio.h>
// using recursive approach to find the catalan number
unsigned long int catalan(unsigned int n) {
// Base case
if (n <= 1) return 1;
// catalan(n) is sum of catalan(i)*catalan(n-i-1)
unsigned long int res = 0;
for (int i=0; i<n; i++)
res += catalan(i)*catalan(n-i-1);
return res;
}
//Main function
int main() {
int n = 6;
printf("catalan is :%ld
", catalan(n));
return 0;
}輸出
catalan is :132
更新於： 2019年11月20日
1K+ 閱讀量
廣告