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ệ nhị phân (cơ số 2). Với mỗi testcase, đầu vào là một số n (1 ≤ n ≤ 10^18), đầu ra là một chuỗi ký tự '0' và '1' biểu diễn số đó trong hệ nhị phân. Với T lên tới 10^5, giải thuật cần phải hiệu quả để xử lý trong thời gian cho phép.

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

Cách Quy hoạch động/Mảng động (Tương tự đệ quy)

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

int main(){
    int T;
    scanf("%d", &T);
    long long a[100005];
    for(int i=0;i<T;i++)
    scanf("%lld", &a[i]);
    for(int i=0;i<T;i++){
        char c[100];
        int j=0;
        while(a[i]){
            c[j]=a[i] % 2+'0';
            a[i]/=2;
            j++;
        }
        c[j]='\0';
        for(int k=j-1;k>=0;k--)
            printf("%c", c[k]);
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(T * log n)
• Space Complexity: O(T + log n)

Cách tiếp cận này đọc tất cả các số liệu vào mảng, sau đó xử lý từng số. Với mỗi số, ta dùng một mảng ký tự (chuỗi) để lưu trữ các bit được sinh ra. Vòng lặp while(a[i]) thực hiện phép chia lấy dư để lấy các bit từ LSB (Least Significant Bit) đến MSB (Most Significant Bit) và lưu vào chuỗi c. Sau đó, ta duyệt ngược lại mảng c để in ra các bit theo thứ tự đúng. Mảng c có kích thước cố định là 100, đủ để chứa số nhị phân của n (vì 10^18 < 2^60).

Cách Xử lý trực tiếp và đệ quy

#include <stdio.h>
#include <string.h>
void chuyen(long long n){
  char a[10000];
  if(n==0){
    printf("0");
    return;
  }
  else if(n==1){
    printf("1");
    return;
  }
  else{
  int index=0;
  while(n){
    a[index++]=n%2+'0';
    n/=2;
  }
  for(int i=index-1;i>=0;i--){
    printf("%c",a[i]);
  }}}
int main()
{
  int T;
  scanf("%d",&T);
  while(T){
    long long n;
    scanf("%lld\n",&n);
    chuyen(n);
    printf("\n");
    --T;
  }
}

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

Phương pháp này xử lý từng số ngay khi đọc vào. Hàm chuyen sử dụng mảng a để lưu các bit. Logic tính toán tương tự như Approach 1. Code có các điều kiện if(n==0) và if(n==1) ở đầu để xử lý các trường hợp cơ sở, nhưng thực tế vòng lặp while(n) ở dưới cũng xử lý được các trường hợp này (trừ n=0). Tuy nhiên, việc dùng mảng a trong hàm và in ngược là cách làm phổ biến.

Cách Mảng tĩnh và tối ưu bộ nhớ

#include <stdio.h>

void binary (long long n) {
   int bin[64];
   int b=0;
   while (n>0) {
       bin[b++]=n%2;
       n/=2;
   }
   for (int j=b - 1; j>=0; j--) {
       printf ("%d",bin[j]);
   }
}

int main() {
    int t;
    long long n;
    scanf("%d", &t);
    for (int i=0; i<t; i++) {
        scanf ("%lld", &n);
        binary (n);
        printf ("\n");
    }
    return 0;
}

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

Đây là cách tiếp cận tối ưu về mặt bộ nhớ trong số các giải pháp được cung cấp. Nó sử dụng một mảng int bin[64] có kích thước cố định. Vì n ≤ 10^18 < 2^60, nên 64 phần tử là đủ. Mảng lưu trữ các số nguyên 0 hoặc 1 thay vì ký tự, giúp tiết kiệm bộ nhớ một chút. Quan trọng nhất, nó không lưu trữ toàn bộ chuỗi kết quả trước khi in mà in trực tiếp các bit từ MSB đến LSB.

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

Bài học kinh nghiệm

• Thuật toán chuyển đổi cơ số: Lấy số chia cho 2, phần dư là bit cuối (LSB), thương là số tiếp theo. Lặp lại cho đến khi số bằng 0. thu được các bit từ LSB đến MSB.
• Vì n có thể lên tới 10^18, số bit cần thiết là khoảng 60 bit. Do đó, ta có thể dùng mảng tĩnh hoặc mảng có kích thước nhỏ (vd: 64 hoặc 100) để lưu kết quả thay vì dùng chuỗi động.
• Cần in các bit theo thứ tự từ MSB về LSB, do đó sau khi tính toán (thường thu được LSB trước), ta cần lưu lại và duyệt ngược hoặc in đệ quy (mặc dù code mẫu dùng mảng và in ngược).

Lỗi thường gặp

• Xử lý số 0: Nếu input n = 0, vòng lặp while(n) sẽ không chạy và không in gì. Code mẫu số 1 có xử lý if(n==0), nhưng code số 2 và 3 không xử lý rõ ràng (trong khi đề bài giới hạn n ≥ 1, nên vấn đề này không lỗi ngay trong bài này, nhưng là sai sót phổ biến).
• Sử dụng biến sai loại: Input n có thể lên tới 10^18, bắt buộc phải dùng long long (hoặc unsigned long long). Dùng int sẽ bị tràn số.
• Lỗi truy cập mảng: Nếu dùng mảng quá nhỏ, ví dụ int bin[20] cho n lớn, sẽ gây lỗi tràn bộ nhớ.
• Dấu cách và ký tự thừa: Đề bài yêu cầu in xâu nhị phân liên tục không khoảng trắng và in xuống dòng sau mỗi số.