Giả sử chúng ta có một số n và số chữ số d. Chúng ta phải kiểm tra xem số n có thể được biểu diễn dưới dạng chữ số d trong bất kỳ cơ số nào từ 2 đến 32. Giả sử số n là 8 và d =4, thì số này có thể được biểu diễn dưới dạng 1000 trong hệ nhị phân, ở đây d là 4 .
Ý tưởng là kiểm tra tất cả các căn cứ lần lượt từ 2 đến 32. Chúng ta có thể làm theo các bước sau để kiểm tra căn cứ.
- Nếu số nhỏ hơn cơ số và chữ số là 1, thì trả về true
- nếu chữ số nhiều hơn một và số lớn hơn cơ số, thì hãy xóa chữ số cuối cùng khỏi số bằng cách thực hiện num / cơ số, do đó giảm số chữ số, sau đó thực hiện lặp lại điều này một cách đệ quy.
- Nếu không, trả về false.
Ví dụ
#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, base);
return false;
}
bool checkNumber(int num, int d) {
// Check for all bases one by one
for (int base=2; base<=32; base++)
if (isRepresentedInDDigits(num, d, base))
return true;
return false;
}
int main() {
int num = 8;
int dig = 2;
if(checkNumber(num, dig))
cout << "Can be represented";
else
cout << "Can not be represented";
} Đầu ra
Can be represented