数列 3, 12, 29, 54, 87, … のN番目の項を求めるC++プログラム

問題概要

この問題では、整数 N が与えられます。私たちのタスクは、以下の数列の N番目の項 を求めるC++プログラムを作成することです。

3, 12, 29, 54, 87, 128, …（第N項まで）

入出力例

まず、具体的な例を使って問題を確認しましょう。

入力： N = 5

出力： 87

数列の5番目の項は 87 であるため、これが正しい出力となります。

解法アプローチ：一般項の導出

この種の問題を効率的に解くには、数列の一般項（第n項を表す公式）を導き出すのが有効です。まず、隣り合う項の差に注目してみましょう。

• 12 − 3 = 9
• 29 − 12 = 17
• 54 − 29 = 25
• 87 − 54 = 33

階差は 9, 17, 25, 33 となっており、それぞれの差が一定（+8）です。つまり二次的な増加パターンを持つ数列であるため、一般項は n の二次式になります。係数を整理すると、この数列の一般項は次の式で表されます。

T_n = 4n² − 3n + 2

この公式を使えば、ループで順番に計算することなく、任意の項の値をO(1)で直接求められます。

検算例：

T8 = 4 × (8²) − 3 × 8 + 2
T8 = 4 × 64 − 24 + 2
T8 = 256 − 22 = 234

C++での実装例

上記の一般項の公式をそのままコードに反映すると、以下のようなシンプルな実装になります。

#include <iostream>
using namespace std;

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

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

実行結果

7番目の項は 177

実際に確認すると、4 × 49 − 21 + 2 = 177 となり、正しく計算できていることがわかります。

計算量について

• 時間計算量： O(1) — 一般項の公式に代入するだけのため、Nの大きさに依存しません。
• 空間計算量： O(1) — 追加のメモリは不要です。

このように、数列のパターンから一般項を見つけ出すことで、非常に効率的なプログラムを実現できます。