C言語で二項係数の最大値を求める方法を解説

正の整数 N が与えられたとき、すべての二項係数の中から最大となる係数項を求める問題について解説します。

二項係数とは

二項係数の列は次のように表されます。

nC₀, nC₁, nC₂, …, nC_r, …, nC_n-2, nC_n-1, nC_n

この中で nC_r の最大値を見つけるのが目的です。二項係数は以下の式で計算できます。

nCr = n! / (r! × (n − r)!)

入出力例

例1：N = 4 の場合

出力： 最大係数 = 6

説明：

• 4C₀ = 1
• 4C₁ = 4
• 4C₂ = 6
• 4C₃ = 4
• 4C₄ = 1

この場合、最大の係数は 6 です。

例2：N = 5 の場合

出力： 最大係数 = 10

説明：

• 5C₀ = 1
• 5C₁ = 5
• 5C₂ = 10
• 5C₃ = 10
• 5C₄ = 5
• 5C₅ = 1

この場合、最大の係数は 10 です。

アルゴリズムの考え方（動的計画法）

このプログラムでは、パスカルの三角形を利用した動的計画法によって二項係数を効率的に計算します。手順は以下のとおりです。

1. ユーザーから N の値を入力として受け取ります。
2. 関数 maxCoeff(int n) は引数 n を受け取り、二次元配列 C[n+1][n+1] を使って各二項係数の値を格納します。
3. 変数 min と max を 0 で初期化します。min は配列 C[][] を走査する範囲の上限、max は見つかった最大の係数値を保持するために使います。
4. i = 0 から n までの for ループで配列 C[][] を初期化していきます。
5. 内側の for ループでは、i と n のうち小さい方まで走査します。
6. j == 0 または j == i のときは C[i][j] = 1 とし、それ以外はパスカルの法則に従って C[i][j] = C[i-1][j-1] + C[i-1][j] とします。
7. すべての計算が終わったら、配列 C[][] の最終行を再度走査し、最大値を変数 max に保存します。
8. 結果として max を返します。

C言語での実装例

#include <stdio.h>
int maxCoeff(int n){
    int C[n+1][n+1];
    int max=0,min=0;
    // 二項係数の値を計算する
    for (int i = 0; i <= n; i++){
        min=i<n?i:n;
        for (int j = 0; j <= min; j++){
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    for (int i = 0; i <= n; i++){
        max = max> C[n][i] ? max: C[n][i];
    }
    return max;
}
int main(){
    int N = 3;
    printf("Maximum Coefficient :%d", maxCoeff(N) );
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Maximum Coefficient: 3

計算量について

このアルゴリズムの時間計算量は O(n²)、空間計算量も O(n²) です。二項係数を階乗で直接計算する方法と比べ、大きな数のオーバーフローを抑えながら段階的に値を構築できる点がメリットです。なお、数学的な性質から最大の二項係数は必ず中央（r = n/2）付近に現れるため、nC_⌊n/2⌋ のみを計算すればさらに効率化することも可能です。