第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同じように、可能な括弧表現は（（（()）），()（()），()()()，（()）()，（()()）。

• 円の交差しない弦上に接続点を見つける方法など

例

入力:　n　=　6
出力:　132
入力:　n　=　8
出力:　1430

私たちが問題を解決するために使用する方法-

• nを取得し入力する。

• n <= 1、それから返す1

• i = 0からi < nまでのループ ++

• 各iに対して結果を設定する+（catalan(i)* catalan(ni-1)）

• 結果を返し、出力する。

アルゴリズム

Start
　　　ステップ　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
　　　　　　ループ For　i=0　and　i<n　and　i++
　　　　　　　　　Set　res　=　res　+　(catalan(i)*catalan(n-i-1))
　　　　　　ループの終わり
　　　　　　Return　res
　　　ステップ　2　->　int　main()　Declare　an　input　n　=　6
　　　「catalan　is　:」を出力し、その後 function catalan(n) を呼び出す
停止

例

#include　<stdio.h>
//再帰法を使用してカタロニア数字を見つける
unsigned　long　int　catalan(unsigned　int　n)　{
　　　//基本的な状況
　　　if　(n　<=　1) return　1;
　　　//カタロニア語(n)はカタロニア語(i)*カタロニア語(n)-1)の合計
　　　unsigned　long　int　res　=　0;
　　　for　(int　i=0;　i<n;　i++)
　　　　　　res　+=　catalan(i)*catalan(n-i-1);
　　　return　res;
}
//主要機能
int　main()　{
　　　int　n　=　6;
　　　printf("catalan　is　:%ld\n",　catalan(n));
　　　return　0;
}

出力結果

catalan　is　:132