C++でN以下のジャンピングナンバーをすべて出力する方法

この記事では、与えられた数値 n 以下のジャンピングナンバー（Jumping Numbers）をすべて出力するC++プログラムを紹介します。

ジャンピングナンバーとは？

ジャンピングナンバーとは、隣り合う桁どうしの差が必ず「1」になっている数のことです。例えば、4565、98、7 などが該当します。

• すべての1桁の数字（0〜9）は、ジャンピングナンバーとみなされます。
• 235 のように、隣接する桁の差が1以外になる箇所がある数は、ジャンピングナンバーではありません。

問題の例

具体的な入力と出力の例を見てみましょう。

入力: N = 32
出力: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32

解法のアプローチ：グラフとして捉える

この問題を効率的に解くには、0 を起点とするグラフを想定し、そこから到達可能なすべてのノードを探索する方法が有効です。探索には BFS（幅優先探索）または DFS（深さ優先探索）を使用できます。

グラフの構築ルールはシンプルです。ある数 num の末尾の桁を d とするとき、次の候補となる子ノードは以下のように決まります。

• 末尾が 0 の場合 → 「num×10 + 1」のみを生成
• 末尾が 9 の場合 → 「num×10 + 8」のみを生成
• それ以外の場合 → 「num×10 + (d−1)」と「num×10 + (d+1)」の両方を生成

この条件で生成される数は、定義上すべてジャンピングナンバーになります。

C++での実装例

以下のコードは、BFSを用いてこの解法を実装したものです。

#include <bits/stdc++.h>
using namespace std;
void traverse(int N, int num) {
    queue<int> q;
    q.push(num);
    while (!q.empty()) {
        num = q.front();
        q.pop();
        if (num <= N) {
            cout << num << " ";
            int last_dig = num % 10;
            if (last_dig == 0)
                q.push((num * 10) + (last_dig + 1));
            else if (last_dig == 9)
                q.push((num * 10) + (last_dig - 1));
            else {
                q.push((num * 10) + (last_dig - 1));
                q.push((num * 10) + (last_dig + 1));
            }
        }
    }
}
void printJumpingNumber(int N) {
    cout<<0<<" ";
    for (int i = 1; i <= 9 && i <= N; i++)
        traverse(N, i);
}
int main() {
    int N = 54;
    cout<<"Jumping Numbers less than "<<N<<" are :\n";
    printJumpingNumber(N);
    return 0;
}

実行結果

Jumping Numbers less than 54 are −
0 1 10 12 2 21 23 3 32 34 4 43 45 5 54 6 7 8 9

コードのポイント

• traverse関数：キューを使った幅優先探索（BFS）により、各ジャンピングナンバーから次の候補を順次生成していきます。
• N以下かどうかの判定：キューから取り出した数が N 以下の場合のみ出力し、その次の候補をキューへ追加します。N を超えた数はそれ以上展開されません。
• printJumpingNumber関数：まず 0 を出力し、1〜9 の各1桁の数字を起点として traverse を呼び出します。

なお、出力順序はBFSの探索順に依存するため、昇順にはなりません。ソートされた出力が必要な場合は、結果を一旦コンテナに格納してから並べ替えてください。

計算量について

各ノードから生成される子候補は最大2つなので、探索にかかる時間は n 以下のジャンピングナンバーの個数に比例します。d 桁のジャンピングナンバーは高々 9 × 2^(d−1) 個程度しか存在しないため、n の大きさそのものに比べて非常に少ないノードだけで済む、効率的なアルゴリズムです。