数列 2、12、28、50、77、112、152、198、… の第N項をC++で求めるプログラム

この問題では、整数 N が与えられ、C++ を用いて数列「2, 12, 28, 50, 77, 112, 152, 198, …」の第 N 項を求めるプログラムを作成します。

問題の概要

与えられた数列の第 N 項を求めることが課題です。

対象となる数列: 2, 12, 28, 50, 77, 112, 152, 198, ...(全 N 項)

入出力例

入力: N = 6
出力: 112

解法アプローチ

この数列は、項が進むにつれて増加幅が広がっていく、いわゆる放物線状(二次曲線的)な増加を示しています。そのため、一般項は二次式で表せると推測できます。実際に各項を N の式で整理すると、次の一般公式が得られます。

T_N = 3 × N² + N − 2

この公式を具体的な値で検証してみましょう。

• N = 1 のとき:3×1² + 1 − 2 = 2
• N = 2 のとき:3×2² + 2 − 2 = 12
• N = 3 のとき:3×3² + 3 − 2 = 28
• N = 6 のとき:3×6² + 6 − 2 = 112

このように一般項を明示的な式として導出できれば、ループで項を順に計算する必要がなく、O(1) の計算量で任意の第 N 項を直接求めることができます。

プログラム実装例

#include <iostream>
using namespace std;

int findNTerm(int N) {
    int nthTerm = ((3 * N * N) + N - 2);
    return nthTerm;
}

int main() {
    int N = 10;
    cout << N << "番目の項の値は " << findNTerm(N);
    return 0;
}

実行結果

10番目の項の値は 308

コードの解説

findNTerm 関数は、一般項の公式 T_N = 3N² + N − 2 に引数 N を代入し、第 N 項の値を計算して返します。main 関数では N = 10 を設定して関数を呼び出し、その結果を標準出力に表示しています。

この手法の計算量は以下の通りです。

• 時間計算量: O(1)
• 空間計算量: O(1)

数列の規則性を見抜いて一般項を二次式として表現できれば、非常に大きな N に対しても瞬時に答えを求められる点が、このアプローチの大きな利点です。