Hiểu bài toán

Viết chương trình đọc một danh sách các số nguyên từ bàn phím cho đến khi gặp giá trị bằng 0 (giá trị 0 dùng để đánh dấu kết thúc và không được coi là phần tử của danh sách). Yêu cầu in ra các số âm trong danh sách theo thứ tự xuất hiện ban đầu, các số cách nhau bởi một dấu cách. Nếu danh sách không chứa số âm nào, in ra 'NOT FOUND'.

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

Cách Đọc và In ngay lập tức (Không lưu trữ)

#include <stdio.h>
int main() {
    int x, ok = 0;
    do {
        scanf("%d", &x);
        if (x < 0) {
            printf("%d ", x);
            ok = 1;
        }
    } while (x != 0);
    if (ok == 0) {
        printf("NOT FOUND");
    }
    return 0;
}

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

Đây là cách tiếp cận đơn giản nhất. Ta sử dụng một vòng lặp để đọc từng số. Nếu số đó âm, ta in ra ngay lập tức và đánh dấu biến ok là 1. Sau khi vòng lặp kết thúc (gặp số 0), ta kiểm tra biến ok. Nếu ok vẫn là 0 nghĩa là không có số âm, ta in 'NOT FOUND'. Ưu điểm là không cần mảng phụ, tiết kiệm bộ nhớ. Tuy nhiên, cách này có thể tạo ra một dấu cách thừa ở cuối cùng nếu in ra nhiều số âm (ví dụ in '-1 -2 -4 ').

Cách Lưu trữ vào Mảng động

#include <stdio.h>
#include <stdlib.h>
int main() {
    int capacity = 10;
    int *a = (int*) malloc(capacity * sizeof(int));
    int n = 0;
    while (1) {
        int x;
        if (scanf("%d", &x) != 1 || x == 0) break;
        if (n == capacity) {
            capacity *= 2;
            a = (int*) realloc(a, capacity * sizeof(int));
        }
        a[n++] = x;
    }
    int found = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            if (found) printf(" ");
            printf("%d", a[i]);
            found = 1;
        }
    }
    if (!found) printf("NOT FOUND");
    free(a);
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này đọc và lưu toàn bộ danh sách (hoặc chỉ các số âm) vào một mảng động. Bằng cách sử dụng realloc, ta có thể xử lý số lượng phần tử không xác định trước. Ưu điểm là tách biệt giai đoạn nhập và xuất, giúp kiểm soát định dạng đầu ra dễ dàng hơn (xử lý dấu cách). Tuy nhiên, nó tốn bộ nhớ hơn và cần quản lý bộ nhớ thủ công (malloc/free).

Cách Sử dụng Mảng tĩnh hoặc Biến đếm

#include <stdio.h>
int main() {
    int n, t = 0;
    while (scanf("%d", &n)) {
        if (n == 0) break;
        if (n < 0) {
            t++;
            printf("%d ", n);
        }
    }
    if (t == 0) printf("NOT FOUND");
    return 0;
}

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

Giải pháp này tương tự như cách 1 nhưng sử dụng biến đếm t để theo dõi số lượng số âm đã in. Cú pháp vòng lặp while(scanf(...)) là cách viết gọn để kiểm tra kết quả đọc input. Logic xử lý tương tự cách 1: in ngay khi gặp số âm, sau đó kiểm tra biến đếm để in 'NOT FOUND' nếu cần. Lưu ý về việc in dấu cách thừa cuối cùng.

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

Bài học kinh nghiệm

• Đề bài cho phép đọc input cho đến khi gặp 0, điều này cho phép xử lý luồng dữ liệu (stream) mà không cần biết trước số lượng phần tử.
• Biến đánh dấu (flag) hoặc biến đếm là cách hiệu quả nhất để kiểm tra sự t tồn tại của số âm mà không cần lưu trữ tất cả các số.
• Giới hạn phần tử (10000) và giá trị (1000) cho phép sử dụng các kiểu dữ liệu cơ bản như int mà không lo tràn số.

Lỗi thường gặp

• In ra dấu cách thừa ở cuối danh sách số âm (ví dụ: '-1 -2 -4 '). Mặc dù một số bộ chấm điểm tự động bỏ qua, nhưng đây là lỗi định dạng thường gặp.
• Quên xử lý trường hợp 'NOT FOUND' nếu chỉ in số mà không kiểm tra biến đếm/flag.
• Sử dụng mảng cố định (static array) với kích thước quá nhỏ so với giới hạn (10000 phần tử) có thể gây tràn bộ nhớ đệm nếu không cẩn thận, hoặc lãng phí bộ nhớ nếu khai báo quá lớn.