カタラン数：C++

C++,アルゴリズム,プログラム

投稿者：

最初に

C++で書かれた、カタラン数コードです。

表記

カタラン数
C_n=\frac 1{n+1}{\left( \begin{array}{c} 2 n \\ n \\ \end{array} \right)}=\frac{(2 n)!}{(n+1)! n!}

情報

カタラン数 Wikipedia

C++コード

/**
* カタラン数を返す
* @param [in] n 要素数
* @return カタラン数を返す
*/
template<typename IntType>
IntType Catalan(IntType x)
{
    if (x == 0) return 1;
    IntType n = x << 1;

    IntType result = n;
    for (IntType i = 2; i <= x; ++i) {
        result *= (n - i + 1);
        result /= i;
    }
    return result/(x+1);
}

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。