C++で数列 0, 0, 2, 1, 4, 2, 6, 3, 8, 4 のN番目の項を求める方法

問題の概要

この問題では、整数値Nが与えられ、次の数列のN番目の項を求めることが課題となります。

0, 0, 2, 1, 4, 2, 6, 3, 8, 4, 10, 5, 12, 6, 14, 7, 16, 8, 18, 9, 20, 10…

一見すると規則性が分かりにくい数列ですが、実は2つの異なる数列を交互に並べたものになっています。この構造を見抜くことが解法の鍵となります。

入出力の例

入力: N = 6
出力: 2

解法のアプローチ

数列のN番目の項を求めるには、偶数番目の項と奇数番目の項に分けてそれぞれの規則を観察します。

偶数番目の項の規則

• T(2) = 0
• T(4) = 1
• T(6) = 2
• T(8) = 3
• T(10) = 4

nが偶数の場合、T(n)の値は {(n / 2) - 1} で表されます。

奇数番目の項の規則

• T(1) = 0
• T(3) = 2
• T(5) = 4
• T(7) = 6
• T(9) = 8

nが奇数の場合、T(n)の値は {n - 1} で表されます。

このように、項の位置が偶数か奇数かを判定するだけで、O(1)の計算量でN番目の項を求めることができます。

C++での実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;

bool isEven(int n){
    if(n % 2 == 0)
        return true;
    return false;
}

int findNthTerm(int n){
    if (isEven(n))
        return ((n / 2) - 1);
    else
        return (n - 1);
}

int main(){
    int N = 45;
    cout<<N<<"番目の項は "<<findNthTerm(N);
    return 0;
}

出力結果

45番目の項は 44

まとめ

この数列は、偶数番目では「(n / 2) - 1」、奇数番目では「n - 1」という2つの単純な規則が交互に現れる構造を持っています。偶奇の判定を行うだけで定数時間で答えが求まるため、ループ処理を必要としない非常に効率的な解法と言えます。数列の問題では、まず項をいくつか書き出して偶数番目と奇数番目を分けて観察すると、隠れた規則性を発見しやすくなります。