【C++入門】動的計画法（DP）で階乗を効率的に計算する方法

正の整数 n の階乗（n!）は、1×2×3×…×n として定義されます。負の数に対する階乗は定義されていないため、存在しません。本記事では、動的計画法（Dynamic Programming）を活用して、指定された整数の階乗を効率的に求める C++ プログラムを紹介します。

階乗と動的計画法の考え方

階乗は「n! = n × (n-1)!」という漸化式で表せるため、小さい値から順に結果を配列に保存しながら計算する動的計画法と非常に相性が良い問題です。すでに計算した結果を再利用することで、無駄な再計算を避けられます。

アルゴリズム

処理の流れは以下の通りです。

開始
    fact(int n):
        数値 n を読み込む
        初期化
        i = 1, result[1000] = {0}
        result[0] = 1
        i が 1 から n まで繰り返し
            result[i] = i * result[i-1]
    result を出力
終了

サンプルコード

実際の C++ 実装例は以下の通りです。

#include <iostream>
using namespace std;
int result[1000] = {0};
int fact(int n) {
   if (n >= 0) {
      result[0] = 1;
      for (int i = 1; i <= n; ++i) {
         result[i] = i * result[i - 1];
      }
      return result[n];
   }
}
int main() {
   int n;
   while (1) {
      cout<<"Enter integer to compute factorial (enter 0 to exit): ";
      cin>>n;
      if (n == 0)
      break;
      cout<<fact(n)<<endl;
   }
   return 0;
}

実行結果

Enter integer to compute factorial (enter 0 to exit): 2
2
Enter integer to compute factorial (enter 0 to exit): 6
720
Enter integer to compute factorial (enter 0 to exit): 7
5040
Enter integer to compute factorial (enter 0 to exit): 10
3628800
Enter integer to compute factorial (enter 0 to exit): 0

注意点

この実装では int 型を使用しているため、オーバーフローに注意が必要です。13 以上の階乗は int 型の最大値を超えてしまうため、大きな数値を扱う場合は long long 型や多倍長整数の利用を検討してください。また、result 配列はグローバル変数として宣言されているため、複数回の呼び出しでも既存の計算結果が保持され、再計算のコストを削減できます。