数列「1, 2, 2, 3, 3, 3, 4…」のn番目の項を求めるC++プログラム

この問題では、整数Nが与えられ、数列 1, 2, 2, 3, 3, 3, 4… のn番目の項を求めることが課題となります。

具体例で問題を理解しましょう。

入力

N = 6

出力

3

説明

n番目までの数列は 1, 2, 2, 3, 3, 3, … となるため、6番目の項は「3」です。

解法アプローチ①：二重ループを使うシンプルな方法

最も単純な解き方は、ネストした（入れ子になった）ループを使用する方法です。外側のforループを1からnまで回し、内側のループを1からi（外側のループのイテレータ）まで回します。内側のループの各反復で数列の要素数をカウントし、カウントがnに等しくなった時点でiの値を返せば答えが得られます。

この方法でも正しく求められますが、計算量がO(n²)になるため、Nが大きい場合は非効率です。

解法アプローチ②：パターンの位置を利用した効率的な方法

より効率的なアプローチは、数列のパターンと各要素の位置関係を利用することです。各要素が数列のどの位置に現れるかを見てみましょう。

要素 1：位置 1
要素 2：位置 2, 3
要素 3：位置 4, 5, 6
要素 4：位置 7, 8, 9, 10

これらの値から、各要素が数列内で占める最後の位置に注目すると、次のような数列が作れます。

1, 3, 6, 10, 15, 21, 28, …

これはいわゆる三角数です。つまり、値xが現れるのは 1 + 2 + 3 + … + (x−2) + (x−1) 番目以降であることが分かります。

これを一般化すると、次の式になります。

n = x × (x − 1) / 2

両辺に2を掛けて整理すると、

2n = x² − x　⇒　x² − x − 2n = 0

この二次方程式を解の公式で解くと、

x = (1 + √(1 + 8n)) / 2

この式により、ループを使わずにO(1)でn番目の項を直接計算できます。

ソリューションの動作を示すプログラム

コード例

#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
    int x = (((1) + (double)sqrt(1 + (8 * n))) / 2);
    return x;
}
int main(){
    int n = 12;
    cout<<"The series is 1, 2, 2, 3, 3, 3, 4, 4, ...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

出力

The series is 1, 2, 2, 3, 3, 3, 4, 4, ...
12th term of the series is 5

まとめ

本記事では、数列「1, 2, 2, 3, 3, 3, 4…」のn番目の項を求める2つの方法を紹介しました。二重ループによる素直な実装は理解しやすい一方で計算量が大きくなりますが、三角数の性質を利用した二次方程式の解法を使えば、定数時間で答えを求められる点が大きなメリットです。