C++で数列 1, 2, 11, 12, 21… のN番目の項を求めるプログラム

この問題では、数値 N が与えられ、C++を用いて数列 1, 2, 11, 12, 21… のN番目の項を求めるプログラムを作成します。

問題の概要

次の数列のN番目の項を求めます。

1, 2, 11, 12, 21, 22, 111, 112, …（第N項まで）

この数列には一定のパターンが隠されており、それをもとに一般項を導き出す必要があります。

具体例を見てみましょう。

入力

N = 8

出力

112

解法のアプローチ

一般項を導くためには、まず数列を注意深く観察することが重要です。この数列には次のような特徴があります。

• すべての項が「1」と「2」のみで構成されている。
• 各項の末尾の数字が「1」と「2」で交互に現れる。
• 前半の項を10倍して1または2を加えることで、後続の項が生成される。

これらの規則性から、一般項は以下の漸化式で表せます。

• N が奇数の場合：T(N) = T(N/2) × 10 + 1
• N が偶数の場合：T(N) = T((N/2) − 1) × 10 + 2

なお、初期条件は T(1) = 1、T(2) = 2 となります。

実装例

#include <iostream>
using namespace std;

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

int main() {
    int N = 12;
    cout << N << "番目の数列の項は " << findNTerm(N);
    return 0;
}

出力

12番目の数列の項は 212

コードの解説

このプログラムでは、再帰関数 findNTerm() を使用して漸化式を実装しています。

例として N = 12 の場合を追ってみましょう。N = 12 は偶数なので、T(12) = T(5) × 10 + 2 となります。次に T(5) は奇数なので、T(5) = T(2) × 10 + 1 = 21 です。したがって、T(12) = 21 × 10 + 2 = 212 が求まります。

各ステップでNが約半分になるため、計算量は非常に効率的です。

• 時間計算量：O(log N)
• 空間計算量：O(log N)（再帰呼び出しのスタック分）