Hiểu bài toán

Viết chương trình nhập vào 2 ký tự chữ cái viết thường (a-z). Yêu cầu in ra tất cả các chữ cái viết hoa tương ứng nằm trong đoạn từ ký tự đầu đến ký tự thứ hai theo thứ tự bảng chữ cái tiếng Anh, cách nhau bởi 1 dấu cách. Chữ cái thứ nhất luôn có thứ tự không đứng sau chữ cái thứ hai (tức là a <= b). Ví dụ: nhập 'a' và 'c' thì in ra 'A B C'.

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

Cách Sử dụng mảng ánh xạ (Lookup Table)

#include <stdio.h>

int main() {
    char a, b;
    scanf("%c %c", &a, &b);
    char lower[] = "abcdefghijklmnopqrstuvwxyz";
    char upper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int start = 0, end = 0;

    // Tìm vị trí của ký tự đầu tiên
    for (int i = 0; i < 26; i++) {
        if (lower[i] == a) {
            start = i;
            break;
        }
    }

    // Tìm vị trí của ký tự thứ hai
    for (int i = 0; i < 26; i++) {
        if (lower[i] == b) {
            end = i;
            break;
        }
    }

    // In các ký tự hoa tương ứng
    for (int i = start; i <= end; i++) {
        printf("%c ", upper[i]);
    }

    return 0;
}

• Time Complexity: O(1) (vì độ dài bảng chữ cái cố định là 26)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng hai mảng chuỗi: một cho chữ cái thường và một cho chữ cái hoa. Đầu tiên, ta tìm chỉ số (vị trí) của hai ký tự nhập vào trong mảng chữ cái thường. Sau đó, dùng chính chỉ số đó để lấy các ký tự hoa tương ứng từ mảng chữ cái hoa và in ra. Phương pháp này mô phỏng việc tra bảng trực tiếp.

Cách Sử dụng tính chất ASCII và hàm library

#include <stdio.h>
#include <ctype.h>

void upper(int a, int b) {
    // Đảm bảo a nhỏ hơn b (mặc dù đề bài nói a không đứng sau b, nhưng đây là thói quen tốt)
    if (a > b) {
        int temp = a;
        a = b;
        b = temp;
    }

    for (int i = a; i <= b; i++) {
        printf("%c ", toupper(i));
    }
}

int main() {
    char a, b;
    scanf("%c %c", &a, &b);
    upper(a, b);
    return 0;
}

• Time Complexity: O(k) (k là số lượng ký tự trong đoạn a đến b)
• Space Complexity: O(1)

Cách tiếp cận này dựa trên bảng mã ASCII. Ký tự 'a' có mã số 97 và 'A' có mã số 65, chênh lệch là 32. Tương tự cho các ký tự khác. Ta có thể lặp từ ký tự 'a' đến 'b', và sử dụng hàm toupper() có sẵn trong thư viện <ctype.h> để chuyển đổi từng ký tự sang dạng hoa. Hàm này sẽ tự động cộng trừ 32 vào mã ASCII để ra ký tự hoa/thường tương ứng.

Cách Tính toán trực tiếp dựa trên offset ASCII

#include <stdio.h>

int main() {
    char a, b;
    scanf("%c %c", &a, &b);

    // Chuyển ký tự thường thành hoa bằng cách trừ đi giá trị offset
    // 'a' - 'a' = 0, cộng với 'A' => 'A'
    // Hoặc đơn giản hơn: a - 32 là mã ASCII của chữ hoa

    for (int i = a; i <= b; i++) {
        printf("%c ", i - 32);
    }

    return 0;
}

• Time Complexity: O(k)
• Space Complexity: O(1)

Đây là cách tối ưu nhất về mặt hiệu năng và ngắn gọn. Ta biết rằng khoảng cách giữa một chữ cái thường và chữ hoa tương ứng của nó là hằng số 32 trong bảng mã ASCII. Do đó, ta chỉ cần lặp từ giá trị byte của a đến b, và tại mỗi bước, in ra giá trị byte trừ đi 32. Ví dụ: a (97) - 32 = 65 ('A').

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

Bài học kinh nghiệm

• Bảng chữ cái tiếng Anh có thứ tự tuần tự trong bảng mã ASCII: 'a' đến 'z' và 'A' đến 'Z'.
• Có thể chuyển đổi giữa chữ hoa và chữ thường bằng cách cộng/trừ một hằng số (32) vào mã ASCII của ký tự.
• Vòng lặp for là công cụ phù hợp nhất để duyệt qua một đoạn liên tục các ký tự.

Lỗi thường gặp

• Quên nhập ký tự cách nhau bởi dấu cách trong lệnh scanf (ví dụ: scanf("%c%c") sẽ gây lỗi khi nhập 'a' và 'c' vì khoảng trắng giữa chúng).
• In thừa dấu cách ở cuối cùng của kết quả (Output yêu cầu cách nhau 1 dấu cách, thường các bài tập dạng này sẽ kiểm tra chặc chẽ khoảng trắng).
• Lỗi biên dịch nếu khai báo biến lồng trong vòng lặp for mà không dùng trình biên dịch C99 hoặc mới hơn.