C++ 中 n 位阶梯数的个数

阶梯数是指一个数字，其中连续数字之间的差为 1。给定一个表示数字位数的数字 n。你需要计算 n 位阶梯数的总数。

让我们来看一个例子。

输入

2

输出

17

2 位数的最小数字是 10，最大数字是 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

更新于： 2021-10-26

143 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告