C++で二項係数を要素に持つ配列を定義するメモ

やりたいこと

二項係数を要素に持つ一次元配列を定義したい．すなわち：

$$ \begin{align} {}_n C_k = \binom{n}{k} = \frac{n!}{k!(n-k)!} \tag{1} \end{align} $$

を要素に持つような $n+1$ 次元配列を定義したい．

Python による実装

Python では，以下のような関数を定義することによって所望の配列を生成できる．内包記法は便利．

import math
def binominal(n):
    return [int(math.factorial(n)/(math.factorial(i)*math.factorial(n-i))) for i in range(n+1)]

出力例としては，次のようになる．

binom = binominal(8)
print(binom) # [1, 8, 28, 56, 70, 56, 28, 8, 1]

C++ による実装

C++ では，階乗を計算してくれる関数が用意されていないので，自分で定義する必要がある．

int factorial(int n)
{
    int val = 1;
    if (n==0 | n==1)
    {
        return val;
    }
    else
    {
        return n * factorial(n-1);
    }
}

こんな感じで再帰処理を用いて書いてあげればいいと思う．なお，入力に負数が入った場合の処理は記述していない．この関数を使ってあげれば，式(1)より二項係数を計算することができるので，各要素ごとに計算して配列に入れてあげれば所望の配列を生成できる．ここで，関数の引数として配列のアドレスを指定してあげる必要があることに注意が必要．

void binominal(int *binom, int n) // アドレスを受け取る関数の定義
{
    for (int i=0; i<n+1; i++)
    {
        binom[i] = (factorial(n)) / (factorial(n-i) * factorial(i));
    }
}

全体的なコードは次のようになる．確認のため，配列の各要素を順番に出力する処理も書いてある．

#include <iostream>

int factorial(int n);
void binominal(int *binom, int n);

int main()
{
    int n = 8;
    int binom[n+10]; // 余分に確保
    binominal(binom, n);

    for (int i=0; i<n+1; i++)
    {
        std::cout << binom[i] << std::endl; // 配列の要素を順番に出力
    }
    return 0;
}

int factorial(int n)
{
    // 上と同じなので省略
}

void binominal(int *binom, int n)
{
    // 上と同じなので省略
}

出力の結果は次にようになって，Python での結果と一致します．

1
8
28
56
70
56
28
8
1

おわりに

今回は C++ で二項係数を要素に持つような配列の定義の仕方について述べた．C++ なので，上記のような配列による実装ではなくて，例えば std::vector を使ったりすることにより，もっと簡単に実装ができるのかもしれない．なので，std::vector を含め，C++ ならではの文法についても覚えていきたいが，C 言語もおろそかにするわけにはいかないので，今回はポインタを使った実装にした．Python は確かに便利なモジュールが豊富で，記述も容易であるので，非常に使いやすいという利点があるのだが，一方で処理速度が遅いという致命的な欠点を有する．最近，重ための処理を行う機会が多くなり，Python を使っている場合ではなくなったこともあって，今回このような内容について扱った．もっと研鑽を積んで C 言語ならびに C++ をマスターしていきたい．