Chương trình đệ quy in các số < N chỉ chứa chữ số 1 và 3 trong C++

Cho số nguyên dương N. Nhiệm vụ: đệ quy in ra tất cả các số nhỏ hơn N chỉ bao gồm chữ số 1, 3 hoặc tổ hợp của cả hai.

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: num = 40

Đầu ra: 33 31 13 11 3 1

Giải thích: Các số < 40 chỉ chứa 1,3: 1, 3, 11, 13, 31, 33. In theo thứ tự giảm dần do đệ quy từ N-1 xuống 1.

Đầu vào: num = 5

Đầu ra: 3 1

Đầu vào: num = 1

Đầu ra: Wrong Input

Giải thích: Không có số nguyên dương < 1 chỉ chứa 1,3.

Phương pháp tiếp cận (Đệ quy + Kiểm tra chữ số)

• Hàm Recursive_Numbers(num):
  • Nếu num > 0:
    • Kiểm tra từng chữ số của num (bằng %10, /10). Nếu tất cả đều là 1 hoặc 3 → in num.
    • Gọi đệ quy Recursive_Numbers(num - 1).
• Trong main: nếu num <= 1 in "Wrong input", ngược lại gọi hàm đệ quy.

Ví dụ mã C++

#include <iostream>
using namespace std;

void Recursive_Numbers(int num) {
    bool check = true;
    int temp = num;
    if (num > 0) {
        while (temp > 0 && check) {
            int digit = temp % 10;
            if (digit != 1 && digit != 3) check = false;
            temp /= 10;
        }
        if (check) cout << num << " ";
        Recursive_Numbers(num - 1);
    }
}

int main() {
    int num = 40;
    if (num <= 1) cout << "Wrong input";
    else {
        cout << "Numbers < N with digits 1 or 3 only: ";
        Recursive_Numbers(num);
    }
    return 0;
}

Đầu ra chương trình

Numbers < N with digits 1 or 3 only are: 33 31 13 11 3 1