【C++】数列2, 10, 30, 68, 130…の第N項を求めるプログラム

この問題では、整数Nが与えられ、数列 2, 10, 30, 68, 130, … の第N項を求めることが課題となります。

まずは具体例で問題を確認してみましょう。

入力

N = 7

出力

350

説明

数列は 2, 10, 30, 68, 130, 222, 350, … と続きます。
したがって、7番目の項は 350 となります。

解法アプローチ

この問題に対する最もシンプルな解決策は、数列の一般項を導き出すことです。各項とそのインデックス（項番号）の関係を調べると、この数列の第N項は次の式で表されることが分かります。

第N項 = N³ + N

実際に各項を検証してみましょう。

i = 1 のとき、T(1) = 2  = 1 + 1  = 1³ + 1
i = 2 のとき、T(2) = 10 = 8 + 2  = 2³ + 2
i = 3 のとき、T(3) = 30 = 27 + 3 = 3³ + 3

このように、すべての項が「N³ + N」の形で正しく表せるため、この式を使えば第N項を定数時間 O(1) で計算できます。ループで数列を順に生成する必要がないため、非常に効率的な解法です。

サンプルコード

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int findNthTerm(int N) {
    return ((N * N * N) + N);
}

int main() {
    int N = 8;
    cout << "数列の " << N << " 番目の項は " << findNthTerm(N);
    return 0;
}

実行結果

数列の 8 番目の項は 520

まとめ

本記事では、数列 2, 10, 30, 68, 130, … の第N項を求める方法を紹介しました。ポイントは、数列のパターンを分析して一般項「N³ + N」を見つけることです。これにより、どんなに大きなNでも即座に答えを計算でき、計算量はO(1)に抑えられます。