C++でn桁のステッピング数を数える方法を解説

ステッピング数（Stepping Number）とは、隣り合う桁同士の差がすべて1となっている数のことです。この記事では、桁数を表す整数 n が与えられたとき、n 桁のステッピング数が全部で何個あるかを数える方法を解説します。

具体例

まずは例を見てみましょう。

入力

2

出力

17

2桁の数のうち最小は10、最大は99です。この範囲には 10, 12, 21, 23, …, 89, 98 のように、合計17個のステッピング数が存在します。

アルゴリズム

ここでは、n桁のすべての数を順番に調べるシンプルな全探索アプローチを紹介します。手順は以下の通りです。

• 桁数 n を初期化します。
• カウント用の変数を 0 で初期化します。
• n桁の最小値を求めます。具体的には pow(10, n - 1) です。
• n桁の最大値を求めます。具体的には pow(10, n) - 1 です。
• 最小値から最大値まで順番にループ処理を行います。
  • 現在の数がステッピング数かどうかを判定します。
  • 数値内の隣接する桁同士の差を確認し、1つでも差が1でない桁があれば false を返し、すべての差が1なら true を返します。
  • 現在の数がステッピング数であれば、カウントを1増やします。
• 最後にカウントを返します。

C++での実装

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

#include <bits/stdc++.h>
using namespace std;

bool isSteppingNumber(int n) {
    int previousDigit = -1;
    while (n) {
        int currentDigit = n % 10;
        if (previousDigit != -1 && abs(previousDigit - currentDigit) != 1) {
            return false;
        }
        previousDigit = currentDigit;
        n /= 10;
    }
    return true;
}

int getSteppingNumbersCount(int n) {
    int lowestNumber = pow(10, n - 1), highestNumber = pow(10, n) - 1;
    int count = 0;
    for (int i = lowestNumber; i <= highestNumber; i++) {
        if (isSteppingNumber(i)) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int n = 3;
    cout << getSteppingNumbersCount(n) << endl;
    return 0;
}

実行結果

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

32

これは、3桁の範囲（100〜999）にはステッピング数が32個存在することを示しています。

補足：計算量について

この方法は非常にシンプルで分かりやすい一方、調査対象の数は約 9 × 10^n-1 個に及ぶため、n が大きくなるほど処理時間が急激に増加します。より大きな n に対応したい場合は、先頭の桁から順に「差が1となる次の桁」だけを枝狩りしながら数え上げるDFS（深さ優先探索）やBFS（幅優先探索）を用いることで、効率的に答えを求めることができます。