数列 3、9、21、41、71…の第N項を求めるC++プログラム

この問題では、整数 N が与えられます。目的は、数列「3, 9, 21, 41, 71, …」の第 N 項を求めることです。

入力例

N = 7

出力例

169

説明

この数列は 3, 9, 21, 41, 71, 113, 169, … のように続きます。したがって、N = 7 のときの第 7 項は 169 となります。

解法アプローチ

この問題に対するシンプルな解法は、数列の一般項を導き出すことです。数列を注意深く観察すると、一般項は次の式で表せることに気づきます。

$$T(N) = \sum n^{2} + \sum n + 1$$

つまり、「最初の n 個の自然数の平方和」と「最初の n 個の自然数の和」の公式をそのまま利用し、それらの合計に 1 を加えればよいのです。

$$T(N)=\left(\frac{n*(n+1)*(2n+1)}{6}\right)+\left(\frac{n*(n+1)}{2}\right)+1$$

この公式を使えば、各項を順番に足し合わせるループ処理が不要になり、O(1) の時間計算量で答えを直接求められます。大きな N に対しても非常に効率的なのがポイントです。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
int findNthTerm(int n) {
    return ((((n)*(n + 1)*(2*n + 1)) / 6) + (n * (n + 1) / 2) + 1);
}
int main() {
    int N = 12;
    cout<<"The "<<N<<"th term of the series is "<<findNthTerm(N);
    return 0;
}

出力

The 12th term of the series is 729

このように、N = 12 の場合、数列の第 12 項は 729 と正しく計算されています。一般項の公式さえ見つけてしまえば、どのような N に対しても即座に答えを得られる、シンプルかつ強力なアプローチです。