หมายเลขก้าวคือตัวเลขที่ความแตกต่างระหว่างหลักที่ต่อเนื่องกันคือ 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
