In số dưới dạng chuỗi 'A' và 'B' theo thứ tự từ điển trong C++

Giới thiệu

Biểu diễn số nguyên N dưới dạng chuỗi chỉ chứa 'A' và 'B' theo thứ tự từ điển (lexicographic order):

1 = A      5 = BA
2 = B      6 = BB
3 = AA     7 = AAA
4 = AB     8 = AAB
...

Quan sát quy luật

Tương tự hệ nhị phân nhưng dùng A/B thay vì 0/1:

• Độ dài 1: 2 chuỗi (A, B) → vị trí 1-2
• Độ dài 2: 4 chuỗi (AA, AB, BA, BB) → vị trí 3-6
• Độ dài 3: 8 chuỗi → vị trí 7-14
• Độ dài L: 2ᴸ chuỗi → vị trí (2ᴸ - 1) đến (2ᴸ⁺¹ - 2)

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

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

void printNumberAsABString(int N) {
    int len = findStringLength(N);
    int indexInLength = N - (pow(2, len) - 2); // Vị trí trong nhóm độ dài len
    
    string result;
    for (int i = len - 1; i >= 0; i--) {
        int half = pow(2, i);
        if (indexInLength > half) {
            result += 'B';
            indexInLength -= half;
        } else {
            result += 'A';
        }
    }
    cout << result << endl;
}

int main() {
    int N = 47;
    cout << "N = " << N << " -> ";
    printNumberAsABString(N);
    
    // Test thêm
    cout << "\nBang tra cuu N=1..20:" << endl;
    for (int i = 1; i <= 20; i++) {
        cout << i << ": ";
        printNumberAsABString(i);
    }
    return 0;
}

Kết quả chạy chương trình

N = 47 -> BAAAA

Bang tra cuu N=1..20:
1: A
2: B
3: AA
4: AB
5: BA
6: BB
7: AAA
8: AAB
9: ABA
10: ABB
11: BAA
12: BAB
13: BBA
14: BBB
15: AAAA
16: AAAB
17: AABA
18: AABB
19: ABAA
20: ABAB

Phân tích độ phức tạp

• Thời gian: O(log N) - độ dài chuỗi ≈ log₂N
• Không gian: O(log N) - lưu kết quả

Mối liên hệ với hệ nhị phân

Chuỗi A/B chính là biểu diễn nhị phân của (N - 2ˡᵉⁿ + 1) với 0→A, 1→B, đệm 0 ở đầu để đủ độ dài len.

Kết luận

Bài toán ánh xạ số nguyên sang chuỗi A/B theo thứ tự từ điển. Giống như đếm nhị phân nhưng ký tự A/B thay vì 0/1.