第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 作為程式的輸出

Some加泰隆尼亞數字的一些應用 -

• ##計算具有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</p><p>", catalan(n));
   return 0;
}

輸出

catalan is :132

以上是第n個卡塔蘭數的C程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！