Trong bài toán này, chúng ta được cho một số n và chúng ta phải in ra tất cả các số nhảy nhỏ hơn hoặc bằng n.
Số nhảy là số có các chữ số liền kề chỉ khác nhau một. Một số số nhảy là 4565, 98, 7. Tất cả các số có một chữ số được coi là số nhảy. 235 không phải là một số nhảy.
Bây giờ, hãy lấy một ví dụ để hiểu vấn đề
Input: N = 32 Output: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32
Để giải quyết vấn đề này, chúng ta sẽ giả sử một đồ thị trong đó 0 là nút bắt đầu và duyệt nó đến tất cả các nút có thể truy cập. Bạn có thể duyệt qua nó bằng BFS hoặc DFS . Biểu đồ này được tạo bằng cách sử dụng một điều kiện làm cho các giá trị nhảy số.
Ví dụ
Đoạn mã dưới đây triển khai giải pháp của chúng tôi -
#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<<"Jumping Numbers less than "<<N<<" are :\n";
printJumpingNumber(N);
return 0;
} Đầu ra
Jumping Numbers less than 54 are − 0 1 10 12 2 21 23 3 32 34 4 43 45 5 54 6 7 8 9