แปลงตัวเลขเป็นสตริง 'A' และ 'B' แบบ Lexicographic Order ใน C++

บทนำ

การแทนตัวเลขด้วยสตริง 'A' และ 'B' แบบ Lexicographic: 1=A, 2=B, 3=AA, 4=AB, 5=BA, 6=BB, 7=AAA, 8=AAB, ...

ข้อสังเกต

คล้าย Binary Number: A=0, B=1 แต่เริ่มนับจาก 1 ไม่ใช่ 0 ความยาว 1: 2 ตัว (1-2) ความยาว 2: 4 ตัว (3-6) ความยาว 3: 8 ตัว (7-14) รวมถึงความยาว L: 2^(L+1) - 2 ตัว

ขั้นตอนการแก้ปัญหา

1. หาความยาวสตริง L ที่ทำให้ 2^(L+1) - 2 ≥ N
2. คำนวณลำดับในกลุ่มความยาว L: stringNumber = N - (2^L - 2)
3. สร้างสตริงทีละตัว: เปรียบเทียบ stringNumber กับ 2^(L-1) ตัดสินใจ A หรือ B

ตัวอย่างโค้ด

#include <iostream>
#include <math.h>
using namespace std;

int findStringLength(int M) {
    int stringLen = 1;
    while ((pow(2, stringLen + 1) - 2) < M) {
        stringLen++;
    }
    return stringLen;
}

void printNumString(int N) {
    int stringLen, num, stringNumber;
    stringLen = findStringLength(N);
    stringNumber = N - (pow(2, stringLen) - 2);
    while (stringLen) {
        num = pow(2, stringLen - 1);
        if (num < stringNumber) {
            cout << "B";
            stringNumber -= num;
        } else {
            cout << "A";
        }
        stringLen--;
    }
}

int main() {
    int N = 47;
    cout << "The number as sting of 'A' and 'B' in lexicographic order is ";
    printNumString(N);
    return 0;
}

ผลลัพธ์

The number as sting of 'A' and 'B' in lexicographic order is BAAAA

ตรวจสอบ N=47

ความยาว 5: ครอบคลุม 31-62 (2^6-2=62) ลำดับในกลุ่ม: 47 - 30 = 17 17 ใน binary (5 bits) = 10001 → BAAAA ✓

สรุป

การแปลงเลขเป็นสตริง A/B คือการเขียนเลขใน Binary แล้ว map 0→A, 1→B พร้อม offset การนับ