C++で数字{0, 1, 2, 3, 4, 5}のみを使って作られるn番目の数を求める方法

数字 {0, 1, 2, 3, 4, 5} のみを使用して作られる数を小さい順に並べると、次のような数列になります。

0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, ...

この数列は、最初の6つの数字をもとに、「既存の数 × 10 ＋ 各数字」というシンプルなパターンを繰り返すことで生成できます。具体的な生成過程を見てみましょう。

1 * 10 + 0 = 10
1 * 10 + 1 = 11
1 * 10 + 2 = 12
1 * 10 + 3 = 13
1 * 10 + 4 = 14
1 * 10 + 5 = 15

同じ要領で、2、3、4、5 に対してもこのパターンを適用すれば、それぞれ続く6個ずつの数（20〜25、30〜35、40〜45、50〜55）が得られます。さらにその先の数も、同じ手順を繰り返すことで順番に求められます。

アルゴリズム

• 整数 n を初期化します。
• 結果を格納するためのベクターを用意します。
• 0 から 5 までのループで、最初の6個の数をベクターに追加します。これで数列の最初の6項が揃います。
• 次に、0 から n / 6 までのループを実行します。
  • さらにその内側で 0 から 5 までのループを実行し、「既存の数 × 10 ＋ 数字」のパターンを適用して残りの数を生成します。
  • 生成した数を順次ベクターに追加していきます。
• 最後に、ベクターから n 番目の数を取り出して返します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>

using namespace std;

int findNthNumber(int n) {
    vector<int> numbers;

    // 最初の6個の数（0〜5）を追加
    for (int i = 0; i < 6; i++) {
        numbers.push_back(i);
    }
    // 既存の数をもとに残りの数を生成
    for (int i = 0; i <= n / 6; i++) {
        for (int j = 0; j < 6; j++) {
            if ((numbers[i] * 10) != 0) {
                numbers.push_back(numbers[i] * 10 + numbers[j]);
            }
        }
    }
    return numbers[n - 1];
}
int main() {
    int n = 7;
    cout << findNthNumber(n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

10

n = 7 の場合、数列の7番目の数は 10 となるため、正しく求められていることがわかります（0 が1番目、1 が2番目、…、5 が6番目、10 が7番目）。なお、先頭の 0 を使った「0 × 10」の組み合わせは数として意味を持たないため、コードでは除外しています。