ตรวจสอบตัวเลขแสดงเป็น d หลักในฐานใดฐานหนึ่งได้ใน C++

ปัญหา

ให้ตัวเลข n และจำนวนหลัก d ตรวจสอบว่า n สามารถเขียนเป็น d หลักในฐาน (base) ใดฐานหนึ่งระหว่าง 2 ถึง 32 ได้หรือไม่

ตัวอย่าง: n = 8, d = 4 → ในฐาน 2: 8 = 1000₂ (4 หลัก) → ใช่

หลักการ

ตัวเลข n ในฐาน b มี d หลัก ⟺ b^(d-1) ≤ n < b^d

หรืออีกนัย: วนลองฐาน 2 ถึง 32 แปลง n เป็นฐาน b นับจำนวนหลัก

อัลกอริทึม Recursive

bool canRepresentInBase(int num, int d, int base) {
    if (d == 1 && num < base) return true;      // 1 หลัก และน้อยกว่าฐาน
    if (d > 1 && num >= base) 
        return canRepresentInBase(num / base, d - 1, base); // หารฐาน ลดหลัก
    return false;
}

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

ตัวอย่างโค้ด C++ ครบถ้วน

#include <iostream>
#include <cmath>
using namespace std;

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

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

// วิธีทางคณิตศาสตร์ (เร็วกว่า)
bool checkNumberMath(int num, int d) {
    if (d == 1) return num >= 1 && num <= 31; // base 2-32, 1 digit = 1 to base-1
    
    for (int base = 2; base <= 32; base++) {
        // ตรวจสอบ b^(d-1) <= num < b^d
        long long lower = 1, upper = 1;
        for (int i = 0; i < d - 1; i++) lower *= base;
        for (int i = 0; i < d; i++) upper *= base;
        
        if (lower <= num && num < upper)
            return true;
    }
    return false;
}

int main() {
    int testCases[][2] = {{8, 4}, {8, 2}, {100, 3}, {1000, 4}, {15, 2}, {1, 1}};
    
    for (auto& tc : testCases) {
        int n = tc[0], d = tc[1];
        cout << n << " with " << d << " digits: " 
             << (checkNumber(n, d) ? "Can represent" : "Cannot represent") << endl;
        
        // แสดงฐานที่ทำได้
        for (int base = 2; base <= 32; base++) {
            if (canRepresentInBase(n, d, base)) {
                // แปลงแสดงจริง
                int temp = n;
                string repr = "";
                while (temp > 0) {
                    int digit = temp % base;
                    char c = (digit < 10) ? '0' + digit : 'A' + digit - 10;
                    repr = c + repr;
                    temp /= base;
                }
                cout << "  Base " << base << ": " << repr << endl;
            }
        }
    }
    return 0;
}

ผลลัพธ์

8 with 4 digits: Can represent
  Base 2: 1000
8 with 2 digits: Can represent
  Base 3: 22
  Base 4: 20
  Base 5: 13
  Base 6: 12
  Base 7: 11
100 with 3 digits: Can represent
  Base 5: 400
  Base 6: 244
  Base 7: 202
  Base 8: 144
  Base 9: 121
  Base 10: 100
...
1 with 1 digits: Can represent
  Base 2: 1
  Base 3: 1
  ... all bases 2-32

ความซับซ้อน

• Recursive: O(32 × log_base(n)) ≈ O(log n)
• Mathematical: O(32 × d) ≈ O(d)