数列 5, 2, 19, 13, 41, … の第N項を求めるC++プログラム

この問題では、整数 N が与えられ、「5, 2, 19, 13, 41, 31, 71, 57 …」という数列の第N項を求めるプログラムを作成します。

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

入力

N = 5

出力

41

説明

この数列は「5, 2, 19, 13, 41, …」と続いていきます。第5項にあたる値は41です。

解法アプローチ

本問題を効率的に解くには、数列の一般項（第N項を表す公式）を利用します。ポイントは、この数列がNの偶奇によって異なる規則性を持っているという点です。具体的には、次の式で第N項を求められます。

Nが偶数の場合（N % 2 == 0）：第N項 = (N−1)² + N
Nが奇数の場合（N % 2 != 0）：第N項 = (N+1)² + N

この公式を用いれば、数列を先頭から順に生成する必要がなく、O(1)の定数時間で第N項を直接計算できます。

実際に検証してみましょう。N=5（奇数）の場合は (5+1)² + 5 = 36 + 5 = 41、N=6（偶数）の場合は (6−1)² + 6 = 25 + 6 = 31 となり、いずれも実際の数列と一致します。

それでは、この解法の動作を示すプログラムを見てみましょう。

サンプルコード（C++）

#include <iostream>
using namespace std;
int calcNthTerm(int N) {
    if (N % 2 == 0)
        return ( ( (N - 1)*( N - 1) ) + N ) ;
    return ( ( (N + 1)*( N + 1) ) + N ) ;
}
int main() {
    int N = 7;
    cout<<N<<"th term of the series is "<<calcNthTerm(N);
    return 0;
}

実行結果

7th term of the series is 71

まとめ

このように、偶奇ごとの一般項を事前に導出しておけば、ループ処理を行わずに任意のN番目の項を即座に計算できます。計算量はO(1)であるため、非常に大きなNが与えられた場合でも高速に動作するのが大きな魅力です。