数列 9, 33, 73, 129, ... の第n項を求めるC++プログラム

問題概要

この問題では、整数 N が与えられ、数列 9, 33, 73, 129, ... の第 n 項を求めることが課題となります。

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

入力

N = 4

出力

129

説明

数列は 9, 33, 73, 129, ... と続いており、4番目の項は 129 です。

解法のアプローチ

この問題を解く鍵となるのは、数列の一般項(第n項の公式)を導出することです。まず数学的に一般項を求め、その公式をプログラムに適用します。

まず、元の数列と、それを1項だけずらした数列の差を取ってみましょう。

Sum  = 9 + 33 + 73 + … + t(n-1) + t(n)
-Sum =      9 + 33 + … + t(n-2) + t(n-1)

0    = 9 + ((33 - 9) + (73 - 33) + … + (t(n) - t(n-1))) - t(n)
t(n) = 9 + (24 + 40 + 56 + ….)

※ 24 + 40 + 56 + …. は初項24・公差16の等差数列です。

等差数列の和の公式を適用すると、一般項は次のように変形できます。

t(n) = 9 + [ ((n−1)/2) × (2×24 + (n−2)×16) ]

t(n) = 9 + [(n − 1) × (24 + (n − 2) × 8)]

t(n) = 9 + [(n − 1) × (8n + 8)]

t(n) = 9 + 8 × [(n − 1) × (n + 1)]

t(n) = 9 + 8 × (n² − 1²)

t(n) = 9 + 8n² − 8

t(n) = 8n² + 1

以上より、この数列の第 n 項は 「8n² + 1」 というシンプルな公式で表せることが分かりました。検算として n = 4 を代入すると、8 × 16 + 1 = 129 となり、正しい結果が得られます。

実装例

導出した公式を使ったプログラムの動作を見てみましょう。

#include <iostream>
using namespace std;

// 第n項を求める関数(一般項: 8n^2 + 1)
int findNthTerm(int n) {
    return (8*n*n) + 1;
}

int main(){
    int n = 12;
    cout<<"The series is 9, 33, 73, 129...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

出力

The series is 9, 33, 73, 129...
12th term of the series is 1153

まとめ

数列の各項を順番に計算していく方法(O(N))と異なり、一般項 8n² + 1 を使えば、どれほど大きな n でも定数時間 O(1) で答えを求められます。「数列の規則性を数学的に分析し、公式へ落とし込む」というアプローチは、競技プログラミングでも非常に重要なテクニックなので、ぜひ覚えておきましょう。