Hiểu bài toán

Cho hai số nguyên a và b (a ≤ b). Yêu cầu in ra tất cả các số chia hết cho 3 nằm trong khoảng (a, b), tức là các số x thỏa mãn a < x < b và x % 3 == 0. Các số phải được in theo thứ tự giảm dần, cách nhau bởi một dấu cách. Nếu không có số nào thỏa mãn, in ra 'NOT FOUND'.

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

Cách Brute Force - Duyệt từ b-1 về a+1

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int found = 0;
    // Duyệt ngược từ b-1 về a+1
    for (int i = b - 1; i > a; i--) {
        if (i % 3 == 0) {
            printf("%d ", i);
            found = 1;
        }
    }
    if (!found) {
        printf("NOT FOUND");
    }
    return 0;
}

• Time Complexity: O(b - a)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Ta duyệt qua tất cả các số nguyên từ b-1 giảm dần về a+1. Với mỗi số, ta kiểm tra xem nó có chia hết cho 3 không (số đó % 3 == 0). Nếu có, ta in nó ra. Biến cờ found dùng để ghi nhận xem có tìm thấy số nào không, từ đó quyết định in 'NOT FOUND' hay không. Cách này đơn giản và dễ hiểu.

Cách Tối ưu - Bắt đầu từ số chia hết cho 3 gần b-1 nhất

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int found = 0;

    // Tìm số chia hết cho 3 lớn nhất nhỏ hơn b
    // Bắt đầu từ b-1, nếu không chia hết thì trừ thêm 1 hoặc 2 để được bội của 3
    int start = b - 1;
    while (start > a && start % 3 != 0) {
        start--;
    }

    // In các số chia hết cho 3 từ start trở xuống
    for (int i = start; i > a; i -= 3) {
        printf("%d ", i);
        found = 1;
    }

    if (!found) {
        printf("NOT FOUND");
    }
    return 0;
}

• Time Complexity: O((b - a) / 3)
• Space Complexity: O(1)

Thay vì duyệt qua tất cả các số, ta chỉ cần duyệt qua các số chia hết cho 3.

1. Xác định số chia hết cho 3 lớn nhất nhỏ hơn b: Lấy start = b - 1. Nếu start không chia hết cho 3, ta trừ đi 1 hoặc 2 để được số chia hết cho 3 (hoặc dùng công thức (start / 3) * 3).
2. In ra các số: Bắt đầu từ số đó, in ra và giảm đi 3 ở mỗi bước lặp (i -= 3) cho đến khi số đó nhỏ hơn hoặc bằng a. Cách này bỏ qua các số không cần thiết, giúp chạy nhanh hơn đáng kể với khoảng cách a và b lớn.

Cách Xử lý số âm và cận biên

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

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

    // Tìm số chia hết cho 3 lớn nhất nhỏ hơn b
    // Công thức này hoạt động chính xác với số âm
    // (b - 1) / 3 * 3
    int start = (b - 1) / 3 * 3;

    if (start <= a) {
        printf("NOT FOUND");
    } else {
        for (int i = start; i > a; i -= 3) {
            printf("%d ", i);
        }
    }
    return 0;
}

• Time Complexity: O((b - a) / 3)
• Space Complexity: O(1)

Đây là phiên bản cải tiến của Approach 2, tập trung vào độ chính xác với số âm. Vấn đề của start % 3 != 0 khi xử lý số âm trong một số ngôn ngữ/phiên bản C là nó có thể trả về số âm. Sử dụng công thức int start = (b - 1) / 3 * 3; là cách an toàn và hiệu quả nhất:

• Với số dương: Ví dụ b=10, b-1=9, 9/3=3, 3*3=9 (đúng).
• Với số âm: Ví dụ b=-1, b-1=-2, -2/3=0 (chia số nguyên), 0*3=0. Số 0 lớn hơn a (giả sử a=-5). Ta in 0, -3. Đây là kết quả đúng. Cách này loại bỏ hoàn toàn vòng lặp while để tìm điểm bắt đầu và đảm bảo xử lý đúng mọi trường hợp.

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

Bài học kinh nghiệm

• Vấn đề yêu cầu in theo thứ tự giảm dần, do đó vòng lặp for nên chạy từ lớn xuống nhỏ.
• Có thể tối ưu hóa bằng cách chỉ duyệt các số chia hết cho 3 thay vì duyệt toàn bộ khoảng (a, b).
• Công thức (limit / 3) * 3 là cách hiệu quả để tìm số chia hết cho 3 gần nhất.

Lỗi thường gặp

• Bỏ qua số a và b: Đề bài yêu cầu khoảng (a, b) nên chỉ xét các số x lớn hơn a và nhỏ hơn b. Trong các giải pháp mẫu, vòng lặp for (int i = b - 1; i > a; i--) là chính xác.
• Xử lý trường hợp 'NOT FOUND': Cần kiểm tra xem có số nào được in ra hay không để in thông báo này. Các giải pháp mẫu dùng biến đếm hoặc cờ (count, k, s, found).
• Lỗi tràn số nguyên hoặc sai dấu với số âm khi dùng modulo: Trong một số ngôn ngữ, -1 % 3 có thể là -1 (không bằng 0), trong khi -1 không chia hết cho 3. Giải pháp dùng i % 3 == 0 trong C thường đúng cho số dương và số âm, nhưng cẩn thận hơn có thể dùng abs(i) % 3 == 0 hoặc công thức số học như trong Approach 3.