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 の場合と同様に、使用できる括弧の式は ((()))、()(())、()()()、(())()、(()()) になります。
• 円上の点を接続するための複数の接続方法を見つけます。その他のコード。問題を解決する方法
−

入力。

循環を返します。 〜i 各 i に対して、result = result (catalan(i)*catalan(n-i-1))

• が設定され、結果が返され、印刷されます。
#算法

• Input: n = 6
  Output: 132
  Input: n = 8
  Output: 1430

例
• の中文翻訳:
例例

• 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;
  }

以上がn番目のカタロニア数のCプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。