숫자 n과 자릿수 d가 있다고 가정합니다. 숫자 n이 2에서 32 사이의 모든 밑수에서 d 자리 숫자로 표시될 수 있는지 확인해야 합니다. 숫자 n이 8이고 d =4라고 가정하면 이진수로 1000으로 나타낼 수 있습니다. 여기서 d는 4입니다. .
아이디어는 2에서 32까지 모든 기지를 하나씩 확인하는 것입니다. 다음 단계에 따라 기지를 확인할 수 있습니다.
- 숫자가 밑수보다 작고 숫자가 1이면 true를 반환합니다.
- 숫자가 하나 이상이고 숫자가 밑수보다 크면 num/base를 수행하여 숫자에서 마지막 숫자를 제거하여 자릿수를 줄인 다음 이 작업을 재귀적으로 반복합니다.
- 그렇지 않으면 false를 반환합니다.
예시
#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";
} 출력
Can be represented