級数 1, 2, 2, 4, 4, 4, 4, 8, 8, 8… のN番目の項を求めるC++プログラム

この問題では、整数 N が与えられ、級数「1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8…」の N 番目の項を求めるプログラムを作成します。

この級数は「1」が1回、「2」が2回、「4」が4回、「8」が8回というように、各値がその値と同じ回数だけ繰り返されるのが特徴です。つまり、2のべき乗の値が出現回数ぶんだけ連続して並ぶ、規則的な構造を持っています。

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

入力

N = 7

出力

4

N = 7 の場合、級数は「1, 2, 2, 4, 4, 4, 4」と並ぶため、7番目の項は「4」になります。

解法1：ループを使った単純なアプローチ

最も基本的な解法は、ループを使って N 番目までの項を順にたどる方法です。各反復処理で現在の項の値だけカウンターを進め、その後項の値を2倍にしていきます。カウンターが N 以上になった時点で、直前の項の値が答えとなります。

• カウンターと項の値を、それぞれ 0 と 1 で初期化する
• カウンターが N 以上になるまで、「カウンターに現在の項の値を加算し、項の値を2倍にする」処理を繰り返す
• ループ終了後、項の値を2で割ったものを返す

実装例

#include <iostream>
using namespace std;

int calcNthTerm(int N) {
    int termCounter = 0, termValue = 1;
    while (termCounter < N) {
        termCounter += termValue;
        termValue *= 2;
    }
    return termValue / 2;
}

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

出力

10 番目の項の値は 8

解法2：一般項を利用した効率的なアプローチ

級数の規則性を数学的に分析すると、より効率的に N 番目の項を求めることができます。まず、各項とそれが最後に現れる位置（インデックス）の関係を見てみましょう。

1 -> 最後のインデックス = 1
2 -> 最後のインデックス = 3
4 -> 最後のインデックス = 7
8 -> 最後のインデックス = 15
...
T(N) -> 最後のインデックス = 2 * T(N) - 1

この結果から、級数の各項 T(N) は必ず2のべき乗、すなわち T(N) = 2^m の形をしており、値 2^m はインデックス 2^m+1 − 1 まで続きことが分かります。

したがって、N 番目の項を求めるには、次の不等式を満たす m を計算すればよいことになります。

2m − 1 < N
これより、m < log2(N + 1)

つまり m = ⌊log₂(N + 1)⌋ となり、答えは 2^m として即座に求められます。この方法は O(1) の時間計算量で動作するため、N が非常に大きい場合でも高速に処理できます。

実装例

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

int calcNthTerm(int N) {
    return pow(2, floor(log(N + 1) / log(2)));
}

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

出力

10 番目の項の値は 8

まとめ

本記事では、級数「1, 2, 2, 4, 4, 4, 4, 8, …」の N 番目の項を求める2つの方法を紹介しました。1つはループによる O(N) の単純な方法、もう1つは対数を活用した O(1) の効率的な方法です。級数の一般項を見抜いて数学的に解くアプローチのほうが、大きな N に対しても高速に動作するため、実践的には有利といえます。