Editorial for dec2hex: Đổi hệ thập phân sang hệ cơ số 16

Hiểu bài toán

Bài toán yêu cầu chuyển đổi một số nguyên dương từ hệ thập phân (cơ số 10) sang hệ thập lục phân (cơ số 16). Đầu vào gồm T số test, mỗi test là một số n (1 ≤ n ≤ 10^18). Đầu ra là biểu diễn của n dưới dạng chuỗi ký tự trong hệ 16, trong đó các chữ cái từ A đến F được viết hoa. Ví dụ: 10 -> A, 15 -> F, 16 -> 10.

Các cách tiếp cận

Cách Quy hoạch đảo ngược (Recursive Reverse)

#include <stdio.h>

void rev(long long n){
    if(n==0) return;
    rev(n/16);
    if(n%16<10) printf("%d",n%16);
    else printf("%c",'A'-10+n%16);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long n;
        scanf("%lld",&n);
        rev(n);
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(log n)

Phương pháp này sử dụng đệ quy để xử lý thứ tự in ra các chữ số. Hàm rev được gọi đệ quy với n/16 trước khi in ra chữ số cuối cùng (n%16). Điều này đảm bảo các chữ số được in ra theo thứ tự từ trái sang phải (từ chữ số có trọng số cao nhất đến thấp nhất).

1. Điều kiện dừng: Nếu n == 0, hàm trả về (đối với n=0, không in gì).
2. Gọi đệ quy: rev(n/16) được gọi trước. Việc này sẽ in ra tất cả các chữ số trước chữ số hiện tại.
3. Xử lý và in chữ số hiện tại:
   • Tính số dư r = n % 16.
   • Nếu r < 10, in ra ký tự số tương ứng.
   • Nếu r >= 10, in ra ký tự chữ cái tương ứng ('A' cho 10, 'B' cho 11, ...).

Ví dụ với n=257:

1. rev(257): Gọi rev(16). Chưa in gì.
2. rev(16): Gọi rev(1). Chưa in gì.
3. rev(1): Gọi rev(0). Chưa in gì.
4. rev(0): Dừng.
5. Quay lại rev(1): In 1 % 16 = 1 -> '1'.
6. Quay lại rev(16): In 16 % 16 = 0 -> '0'.
7. Quay lại rev(257): In 257 % 16 = 1 -> '1'. Kết quả: '101'.

Cách Lưu vào mảng và in ngược (Iterative with Array)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int t;
    scanf("%d",&t);
    for (int j = 0;j < t;j++){
        long long n;
        scanf("%lld",&n);

        char hex[100];
        int i = 0;
        while (n > 0){
            int r = n%16;
            if (r < 10){
                hex[i++] = r + '0';
            } else {
                hex[i++] = r - 10 + 'A';
            }
            n /= 16;
        }
        for (int k = i-1;k >=0;k--){
            printf("%c",hex[k]);
        }
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(log n)

Đây là cách tiếp cận trực quan nhất.

1. Tạo một mảng ký tự hex (hoặc chuỗi) để lưu trữ các chữ số.
2. Dùng vòng lặp while (n > 0):
   • Tính số dư r = n % 16.
   • Chuyển đổi số dư thành ký tự:
     • Nếu r < 10: hex[i++] = r + '0'.
     • Nếu r >= 10: hex[i++] = r - 10 + 'A'.
   • Cập nhật n = n / 16.
   • Vòng lặp này sẽ thu được các chữ số từ phải sang trái (ví dụ: 257 -> '1', '0', '1' trong mảng).
3. Sau khi vòng lặp kết thúc, in mảng hex theo chiều ngược lại từ i-1 về 0.

Phương pháp này dễ hiểu và dễ debug so với đệ quy.

Cách Sử dụng hàm định dạng chuỗi (Printf %llX)

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long n;
        scanf("%lld", &n);
        printf("%llX\n", n);
    }
    return 0;
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Trong ngôn ngữ C, hàm printf hỗ trợspecifier %llX để in ra số nguyên dài (long long) dưới dạng hệ 16 hoa (uppercase hexadecimal). Đây là cách tối ưu nhất về mặt mã nguồn và thường được tối ưu hóa tốt trong thư viện chuẩn.

• %ll: Chỉ định kiểu dữ liệu là long long.
• X: Chỉ định hệ cơ số 16 và in hoa.

Lưu ý: Vấn đề này không yêu cầu xử lý trường hợp n=0 theo cách đặc biệt, nhưng printf sẽ xử lý đúng (in ra '0').

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

Bài học kinh nghiệm

• Cơ số 16 có 16 ký hiệu: 0-9 và A-F (A=10, B=11, ..., F=15).
• Thuật toán chuyển cơ số chung: Lấy số chia cho cơ số, lấy số dư làm chữ số, lặp lại cho đến khi số bằng 0.
• Thứ tự xuất ra của thuật toán lặp trực tiếp là ngược với thứ tự cần in (từ chữ số cuối lên đầu), cần lưu lại hoặc dùng đệ quy để in đúng thứ tự.

Lỗi thường gặp

• Xử lý sai thứ tự in (in ngược): Nếu chỉ lặp và in ngay số dư mà không lưu vào mảng hoặc dùng đệ quy, kết quả sẽ bị ngược.
• Quên xử lý số 0: Nếu input là 0, vòng lặp while(n>0) sẽ không chạy và không in gì. Tuy nhiên, với giới hạn n≥1 trong đề bài, lỗi này không xảy ra. Nhưng nếu mở rộng bài toán cho n≥0 thì cần kiểm tra riêng.
• Sai kiểu dữ liệu: Với n lên tới 10^18, cần dùng long long (hoặc unsigned long long). Dùng int sẽ bị tràn số.
• Sai quy tắc đổi số dư sang ký tự: Lỗi tính toán r + '0' hoặc r - 10 + 'A'' sai.