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セットの結果=結果+（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\n", catalan(n));
   return 0;
}

出力

catalan is :132