C++でのn桁のステップ数

ステッピング番号は、連続する桁の差が1である番号です。桁数を表す番号nが与えられます。 n桁のステップ数の総数を数える必要があります。

例を見てみましょう。

入力

2

出力

17

2桁の最小数は10で、2桁の最大数は99です。それらの間に17のステップ番号があります。

アルゴリズム

• 番号nを初期化します。
• カウントを0に初期化します。
• n桁の最小数、つまりpow（10、n-1）を見つけます。
• n桁の最大数、つまりpow（10、n）-1を見つけます。
• 最小のn桁の数字から最大のn桁の数字まで繰り返すループを作成します。
  • 現在の番号がステップ番号であるかどうかを確認します。
  • 数字の連続する数字のペアの違いを確認します。
  • 差の結果が1でない場合は、falseを返します。それ以外の場合はtrueを返します。
  • 現在の番号がステップ番号の場合は、カウントを増やします。
• カウントを返します。

実装

以下は、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