C++で数列 0, 11, 28, 51, 79, 115, 156, 203, … のN番目の項を求めるプログラム

本記事では、数列 0, 11, 28, 51, 79, 115, 156, 203, … のN番目の項を求めるプログラムを、C++で実装する方法を解説します。

問題の概要

整数Nが与えられたとき、上記の数列におけるN番目の項の値を求めるのが課題です。

入出力例

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

• 入力： N = 5
• 出力： 79

解法のアプローチ

この数列は、隣り合う項同士の差が一定のペースで増えていく「二次数列」です。そのため、各項を順番に計算していく必要はなく、N番目の項を次の一般式から直接求めることができます。

T_n = 3 × N² + 2 × N − 5

たとえば N = 9 を代入すると、3 × 81 + 18 − 5 = 256 となり、後述のプログラムの実行結果と一致します。この式を使えば、ループで項を足し合わせる処理が不要になり、O(1)の計算量で任意のN番目の項を即座に求められる点が大きなメリットです。

解法の動作を示すサンプルプログラム

#include <iostream>
using namespace std;

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

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

実行結果：

9番目の項の値は 256

このように、数列の規則性を一般式として捉えられれば、Nがどれほど大きくなっても瞬時に答えを求められます。競技プログラミングやアルゴリズムの学習においても頻出のテクニックなので、ぜひマスターしておきましょう。