C++で数列1、6、17、34、56、86、121、162、…のN番目の項を求めるプログラム

本チュートリアルでは、数列 1、6、17、34、56、86、121、162、… のN番目の項を求めるプログラムについて解説します。

この問題では、ある数値が与えられ、その位置に該当する数列の項を求めることが課題となります。

アプローチ

まず、この数列がどのような規則で構成されているかを観察してみましょう。隣接する項の差そのものは一定ではありませんが、その差(階差)の変化が一定である二次数列に分類されます。このような数列のN番目の項は、次の一般項で表すことができます。

a_n = 3n² − 4n + 2

実際に検証すると、n = 1 のとき 3 − 4 + 2 = 1、n = 2 のとき 12 − 8 + 2 = 6、n = 3 のとき 27 − 12 + 2 = 17 となり、数列の各項と一致します。したがって、任意の位置 N に対して、この式に代入するだけで目的の項を即座に求められます。

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;

// 与えられた数列のn番目の項を計算する関数
int nthTerm(int n) {
    return 3 * pow(n, 2) - 4 * n + 2;
}

int main() {
    int N = 4;
    cout << nthTerm(N) << endl;
    return 0;
}

出力

34

コードの解説

nthTerm 関数は、引数として受け取った位置 n を一般項 3n² − 4n + 2 に代入し、その結果を呼び出し元に返します。例えば N = 4 の場合、3 × 4² − 4 × 4 + 2 = 48 − 16 + 2 = 34 となり、数列の4番目の項と一致していることがわかります。

なお、pow() 関数を使わずに 3 * n * n - 4 * n + 2 と記述することもできます。こちらの書き方の方が浮動小数点演算を伴わないため、より効率的で安全です。

この手法の計算量は O(1) です。数列を先頭から順番に生成していき目的の位置まで到達するアプローチ(O(N))と比較すると、N が非常に大きい場合でも瞬時に答えを得られる点が大きなメリットといえます。