Trong bài toán này, chúng ta được cho một số n và phải in tất cả các số nhảy (jumping numbers) nhỏ hơn hoặc bằng n.
Số nhảy (Jumping Numbers) là số mà các chữ số kề nhau chỉ khác nhau 1 đơn vị. Ví dụ: 4565, 98, 7. Tất cả số một chữ số được coi là số nhảy. 235 không phải số nhảy.
Ví dụ để hiểu vấn đề:
Đầu vào: N = 32 → Đầu ra: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32
Để giải quyết, ta giả định một đồ thị với 0 là nút bắt đầu và duyệt đến tất cả nút có thể đạt được. Có thể dùng BFS hoặc DFS. Đồ thị được tạo dựa trên điều kiện tạo số nhảy.
Ví Dụ
Mã triển khai giải pháp:
#include <bits/stdc++.h>
using namespace std;
void traverse(int N, int num) {
queue<int> q;
q.push(num);
while (!q.empty()) {
num = q.front();
q.pop();
if (num <= N) {
cout << num << " ";
int last_dig = num % 10;
if (last_dig == 0)
q.push((num * 10) + (last_dig + 1));
else if (last_dig == 9)
q.push((num * 10) + (last_dig - 1));
else {
q.push((num * 10) + (last_dig - 1));
q.push((num * 10) + (last_dig + 1));
}
}
}
}
void printJumpingNumber(int N) {
cout << 0 << " ";
for (int i = 1; i <= 9 && i <= N; i++)
traverse(N, i);
}
int main() {
int N = 54;
cout << "Các số nhảy nhỏ hơn " << N << " là:\n";
printJumpingNumber(N);
return 0;
}
Đầu Ra
Các số nhảy nhỏ hơn 54 là: 0 1 10 12 2 21 23 3 32 34 4 43 45 5 54 6 7 8 9