C++で数列0, 0, 2, 1, 4, 2, 6, 3, 8…のN番目の項を求めるプログラム

この記事では、数値Nが与えられたとき、C++を用いて数列「0, 0, 2, 1, 4, 2, 6, 3, 8…」のN番目の項を求めるプログラムの作成方法を解説します。

問題の概要

与えられた数列のN番目の項を求めることが目標です。

0, 0, 2, 1, 4, 2, 6, 3, 8 ....（N項まで）

ポイントは、この数列の一般項を導き出すことです。

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

入力

N = 8

出力

3

解法のアプローチ

数列の一般項を求めるには、数列を注意深く観察する必要があります。この数列は一見すると規則性が分かりにくいのですが、実は2つの数列が交互に並んだものです。1つは奇数番目の位置に現れる数列、もう1つは偶数番目の位置に現れる数列です。

奇数番目の数列： 0, 2, 4, 6, 8, 10, 12, ...（2ずつ増加）

偶数番目の数列： 0, 1, 2, 3, 4, 5, 6, ...（1ずつ増加）

このことから、数列のn番目の項の値は次のように表せます。

• nが奇数の場合： 値は (n-1)
• nが偶数の場合： 値は T(n-1) / 2（直前の項を2で割った値）

C++での実装例

#include <iostream>
using namespace std;

int findNTerm(int N) {
    if (N % 2 == 0)
        return findNTerm(N - 1) / 2;
    else {
        return (N - 1);
    }
}

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

出力

13番目の項の値は 12

コードの解説

関数findNTermは再帰的に定義されています。Nが偶数の場合は、直前の項findNTerm(N-1)の値を2で割った値を返し、Nが奇数の場合はそのまま(N-1)を返します。数列の規則性がそのままコードに反映されたシンプルな実装です。

なお、偶数番目の項は T(N-1)/2 = (N-2)/2 と変形できるため、再帰を使わずに次のように書くこともできます。

int findNTerm(int N) {
    if (N % 2 == 0)
        return (N - 2) / 2;
    else
        return (N - 1);
}

この方法であれば再帰呼び出しのオーバーヘッドがなく、O(1)の計算量でN番目の項を求めることができます。