สมมติว่าเรามีตัวเลข n และจำนวนหลัก d เราต้องตรวจสอบว่าตัวเลข n สามารถแสดงเป็นตัวเลข d หลักในฐานใดก็ได้ตั้งแต่ 2 ถึง 32 หรือไม่ สมมติว่าตัวเลข n คือ 8 และ d =4 จึงสามารถแสดงเป็น 1000 ในรูปแบบไบนารี โดยที่ d คือ 4 .
แนวคิดคือการตรวจสอบฐานทั้งหมดทีละตัวตั้งแต่ 2 ถึง 32 เราสามารถทำตามขั้นตอนเหล่านี้เพื่อตรวจสอบฐานได้
- หากตัวเลขน้อยกว่าฐานและหลักเป็น 1 ให้คืนค่าเป็น true
- หากหลักมากกว่าหนึ่งและตัวเลขมากกว่าฐาน ให้ลบหลักสุดท้ายออกจากตัวเลขโดยทำ num/base ซึ่งจะเป็นการลดจำนวนหลัก จากนั้นทำซ้ำซ้ำแล้วซ้ำอีก
- มิฉะนั้นจะคืนค่าเท็จ
ตัวอย่าง
#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
