C言語で二項係数テーブルを出力するプログラムの作成方法

正の整数値(ここでは「val」とします)が与えられたとき、0からvalまでの範囲にある任意のnとkに対する二項係数B(n, k)の値を計算し、テーブル形式で出力するのが本記事の目的です。

二項係数とは

二項係数(n, k)とは、「n個の選択肢の中からk個を選ぶ組み合わせ」の総数を表す値です。正の整数nおよびkに対する二項係数は、次の式で定義されます。

$$C_k^n=\frac{n!}{(n-k)!k!}$$

ただし、条件として n >= k が満たされている必要があります。

計算例

入力: B(9,2)
出力:

$$B_2^9=\frac{9!}{(9-2)!2!}$$ 

$$\frac{9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1}{(6\times 5\times 4\times 3\times 2\times 1)\times 2\times 1}=\frac{362,880}{1440}=252$$

このように、9個の中から2個を選ぶ組み合わせの総数は252通りであることが分かります。

二項係数テーブルとは

二項係数テーブルとは、nとkのさまざまな組み合わせに対して生成される複数の値を、一度に計算・確認できるようにまとめた表のことです。いわゆる「パスカルの三角形」としても知られています。

計算例

入力: value = 5
出力:

プログラムのアプローチ

本プログラムでは、以下の手順で二項係数テーブルを生成します。

• テーブルを生成するための上限値として、ユーザーから変数「val」を受け取ります。
• 二項係数の値は0からvalの範囲に収まるため、0からvalまでループ処理を行います。
• nとkがどちらも0でない場合、次の漸化式を適用して計算量を抑えます。
  B(m, x) = B(m, x - 1) * (m - x + 1) / x
• 計算結果を出力します。

この漸化式を使うことで、階乗を毎回計算する必要がなくなり、効率的にテーブルを作成できます。

アルゴリズム

開始
ステップ1 -> 二項係数テーブル用の関数を宣言する
    int bin_table(int val)
    ループ: int i = 0 から i <= val まで、iを1ずつ増やす
        i の値を出力する
        int num = 1 を宣言する
        ループ: int j = 0 から j <= i まで、jを1ずつ増やす
            もし (i != 0 かつ j != 0) ならば
                num = num * (i - j + 1) / j を設定する
            終了
            num の値を出力する
        終了
        改行を出力する
    終了
ステップ2 -> main() 内での処理
    int value = 5 を宣言する
    bin_table(value) を呼び出す
終了

サンプルコード

#include <stdio.h>
// 二項係数テーブルを出力する関数
int bin_table(int val) {
    for (int i = 0; i <= val; i++) {
        printf("%2d", i);
        int num = 1;
        for (int j = 0; j <= i; j++) {
            if (i != 0 && j != 0)
            num = num * (i - j + 1) / j;
            printf("%4d", num);
        }
        printf("\n");
    }
}
int main() {
    int value = 5;
    bin_table(value);
    return 0;
}

実行結果

このプログラムを実行すると、value = 5 の場合、各行がnに対応し、その行内の各値が対応するkに対する二項係数を示す三角形状のテーブル(パスカルの三角形)が出力されます。