Kiểm tra số biểu diễn được bằng d chữ số trong cơ số 2-32 C++

Cho số n và số chữ số d. Kiểm tra n có thể viết dưới dạng d chữ số trong cơ số nào từ 2 đến 32 không.

Ví dụ: n=8, d=2 → nhị phân 1000 (4 chữ số) không, nhưng cơ số 3: 22 (2 chữ số) → YES.

Giải thuật

Thử mọi cơ số 2..32. Hàm đệ quy kiểm tra: - Nếu d==1 và n < base → true - Nếu d>1 và n ≥ base → đệ quy với n/base, d-1 - Ngược lại false

Ví dụ minh họa

#include <iostream>
using namespace std;

bool isRepresentedInDDigits(int num, int d, int base) {
    if (d == 1 && num < base) return true;
    if (d > 1 && num >= base) return isRepresentedInDDigits(num / base, d - 1, base);
    return false;
}

bool checkNumber(int num, int d) {
    for (int base = 2; base <= 32; base++)
        if (isRepresentedInDDigits(num, d, base))
            return true;
    return false;
}

int main() {
    int num = 8, dig = 2;
    cout << (checkNumber(num, dig) ? "Co the bieu dien" : "Khong the bieu dien");
}

Kết quả

Co the bieu dien