Số bước là một số có hiệu giữa các chữ số liên tiếp là 1. Bạn được cho một số n đại diện cho số chữ số. Bạn cần đếm tổng số bước có n chữ số.
Hãy xem một ví dụ.
Đầu vào
2
Đầu ra
17
Số thấp nhất có 2 chữ số là 10 và số cao nhất trong 2 chữ số là 99. Có 17 số bậc ở giữa chúng.
Thuật toán
- Khởi tạo số n.
- Khởi tạo số đếm bằng 0.
- Tìm số n chữ số thấp nhất, tức là .., pow (10, n - 1).
- Tìm số n chữ số cao nhất, tức là .., pow (10, n) - 1.
- Viết một vòng lặp lặp lại từ số n chữ số thấp nhất đến số n chữ số cao nhất.
- Kiểm tra xem số hiện tại có phải là số bước hay không.
- Kiểm tra sự khác biệt giữa các cặp chữ số liên tiếp trong số.
- Nếu kết quả của bất kỳ sự khác biệt nào không phải là 1, thì trả về false, còn lại là true.
- Tăng số lượng nếu số hiện tại là số bước.
- Trả lại số lượng.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
32