C++でパスカルの三角形を生成して表示する方法

パスカルの三角形とは、二項係数（binomial coefficient）を三角形の形に整然と並べた数表のことです。最上段は n = 0 行目と定義され、各行内の要素は左端から k = 0 として番号が振られます。各数値は、直前の行に存在する2つの数、すなわち現在のセルの真上に位置する左右の値を足し合わせることで求められます。

また、パスカルの三角形は数学的には「n行目・k列目の値 = 二項係数 C(n, k)」として計算することもできます。つまり、組み合わせの公式 nCr(n, k) を用いて各セルの値を直接導出できるのです。

例えば、入力として 10 を与えた場合、出力は次のようになります。

                1
               1 1
              1 2 1
             1 3 3 1
            1 4 6 4 1
          1 5 10 10 5 1
         1 6 15 20 15 6 1
        1 7 21 35 35 21 7 1
       1 8 28 56 70 56 28 8 1
    1 9 36 84 126 126 84 36 9 1

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

• i を 0 から n まで繰り返す
  • j を 0 から (n − i − 2) まで繰り返し、空白を出力する（三角形の形状を作るため）
  • j を 0 から i まで繰り返し、nCr(i, j) を計算して出力する

C++による実装例

それでは、実際のC++コードを見てみましょう。階乗を計算する関数 fact()、二項係数を求める関数 nCr()、そして三角形全体を生成する関数 genPascalsTriangle() の3つの部分で構成されています。

#include<iostream>
#include<iomanip>
using namespace std;
long fact(long n){
   int i, fact = 1;
   for(i = n; i>1; i--)
      fact *= i;
   return fact;//引数で渡された数の階乗を返す
}
long nCr(long n, long r){
   long nume = 1, i;
   for(i = n; i>r; i--)
      nume *= i;
   return long(nume/fact(n-r));//nCrの計算結果を返す
}
void genPascalsTriangle(long n){
   for(int i = 0; i<n; i++){
      for(int j = 0; j<(n-i-1); j++)
         cout <<setw(3)<< " ";//三角形の形になるよう空白を出力
      for(int j = 0; j<(i+1); j++)
         cout <<setw(3)<< nCr(i, j) <<setw(3)<< " ";
      cout << endl;
   }
}
main(){
   int n;
   cout << "Enter Number of lines: "; cin >> n;
   genPascalsTriangle(n);
}

コードのポイント

• fact() 関数： 与えられた整数 n の階乗（n!）を計算します。
• nCr() 関数： 組み合わせの公式 nCr(n, r) = n! / (r! × (n−r)!) を利用して二項係数を求めます。
• genPascalsTriangle() 関数： 外側のループで行を制御し、内側の最初のループで左側の空白を、2番目のループでその行の各要素を出力します。setw(3) により桁を揃えて整形しています。

実行結果

入力

10

出力

                      1
                     1 1
                    1 2 1
                   1 3 3 1
                  1 4 6 4 1
                1 5 10 10 5 1
               1 6 15 20 15 6 1
              1 7 21 35 35 21 7 1
             1 8 28 56 70 56 28 8 1
          1 9 36 84 126 126 84 36 9 1

このように、C++では階乗と組み合わせの計算を組み合わせるだけで、パスカルの三角形を簡単に生成できます。なお、大きな n に対しては階乗の値が急激に大きくなりオーバーフローする可能性があるため、その場合は加算方式（上の行の隣接する2つの値を足す方法）や動的計画法を用いると安全です。