C++で数列3, 14, 39, 84, ...のN番目の項を求めるプログラムの作成方法

問題の概要

この問題では、整数 N が与えられ、数列 3, 14, 39, 84, ... のN番目の項を求めるプログラムをC++で作成します。

入出力例

具体的な例を使って、問題を理解しましょう。

入力:

N = 4

出力:

84

説明:

4番目の項は、(4×4×4) + (4×4) + 4 = 64 + 16 + 4 = 84 となります。

解法アプローチ

この問題を解く最もシンプルな方法は、数列のN番目の項を表す一般項(一般式)を利用することです。各項を分解して観察すると、次のパターンが見えてきます。

N番目の項 = N³ + N² + N

実際に各項を確認してみましょう。

• 1番目の項: 1³ + 1² + 1 = 3
• 2番目の項: 2³ + 2² + 2 = 8 + 4 + 2 = 14
• 3番目の項: 3³ + 3² + 3 = 27 + 9 + 3 = 39
• 4番目の項: 4³ + 4² + 4 = 64 + 16 + 4 = 84

このように、すべての項が一般式 N³ + N² + N に一致することがわかります。したがって、Nの値を式に代入するだけで、ループ処理を使わずに任意のN番目の項を定数時間 O(1) で計算できます。

C++プログラムの実装

上記の解法をC++で実装したプログラムが以下の通りです。

#include <iostream>
using namespace std;

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

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

実行結果

6番目の項の値は 258

コードの解説

calcNthTerm関数は、引数として受け取ったNに対して N³ + N² + N を計算して返します。main関数では N = 6 を設定し、6番目の項を求めています。

計算内容を確認すると、6³ + 6² + 6 = 216 + 36 + 6 = 258 となり、正しい結果が出力されていることがわかります。

計算量

• 時間計算量: O(1) — 式への代入のみで求められるため
• 空間計算量: O(1) — 追加のメモリは不要

まとめ

数列の一般項を見つけることができれば、繰り返し処理なしにO(1)で任意の項を求められます。本問題のように、項そのものや項間の差分を観察し、冪乗の組み合わせで表現できないかを検討するのは、数列の問題を解く上で非常に有効なアプローチです。