Stepping Number คือเลขที่ผลต่างระหว่างหลักติดกันเป็น 1 ให้ n หาจำนวน stepping number n หลัก
ตัวอย่าง:
Input: 2 Output: 17
เลข 2 หลัก 10-99 มี stepping number 17 ตัว
อัลกอริทึม
- กำหนด n
- lowest = 10^(n-1), highest = 10^n - 1
- count = 0
- วนลูป i = lowest ถึง highest:
- เช็ค stepping number: ตรวจสอบผลต่างหลักติดกันทุกคู่
- ถ้าเป็น count++
- คืนค่า count
การเขียนโปรแกรม 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++; } return count; } int main() { int n = 3; cout << getSteppingNumbersCount(n) << endl; return 0; }
ผลลัพธ์
32
