Hiểu bài toán

Cho một ma trận số nguyên A có m dòng, n cột. Nhiệm vụ là tìm và liệt kê tất cả các số chính phương (số nguyên không âm là bình phương của một số nguyên) xuất hiện trong ma trận đó. Yêu cầu:

1. Danh sách phải được sắp xếp theo thứ tự tăng dần.
2. Mỗi số chính phương chỉ được liệt kê một lần (loại bỏ trùng lặp).
3. Nếu không có số chính phương nào, in ra 'NOT FOUND'.

Giới hạn: m, n ≤ 100, giá trị tuyệt đối phần tử ≤ 10000.

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

Cách Sử dụng mảng đánh dấu (Frequency Array)

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

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    int count[101] = {0}; // Mảng đánh dấu số chính phương đã xuất hiện
    // Kích thước 101 vì căn lớn nhất của 10000 là 100

    for (int i = 0; i < m * n; i++) {
        int x;
        scanf("%d", &x);
        if (x >= 0) {
            int r = (int)sqrt(x);
            if (r * r == x && r <= 100) {
                count[r] = 1; // Đánh dấu r đã xuất hiện
            }
        }
    }

    int found = 0;
    for (int i = 0; i <= 100; i++) {
        if (count[i]) {
            printf("%d ", i * i);
            found = 1;
        }
    }

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

• Time Complexity: O(m*n)
• Space Complexity: O(1) (mảng kích thước cố định ~100)

Phương pháp này dựa vào quan sát: số chính phương lớn nhất có thể xuất hiện là 100*100 = 10000. Do đó, ta chỉ cần một mảng count kích thước nhỏ (khoảng 100 phần tử) để đánh dấu xem căn bậc hai của số đó có xuất hiện không.

• Mỗi khi đọc một số, ta kiểm tra nó có phải là số chính phương không.
• Nếu có, ta đánh dấu vị trí tương ứng với căn bậc hai của nó trong mảng.
• Cuối cùng, duyệt mảng từ nhỏ đến lớn để in ra các bình phương tương ứng với các giá trị đã đánh dấu.
• Ưu điểm: Rất nhanh, không cần sắp xếp, loại bỏ trùng lặp tự động.

Cách Sử dụng mảng lưu trữ và loại bỏ trùng lặp

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

int cp(int x) {
    if (x < 0) return 0;
    int y = (int)sqrt(x);
    return (y * y == x);
}

void sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

int main() {
    int m, n, a[100][100];
    int result[10005]; // Mảng lưu các số chính phương tìm được
    int count = 0;

    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
            if (cp(a[i][j])) {
                // Kiểm tra xem số này đã có trong danh sách chưa
                int exists = 0;
                for (int k = 0; k < count; k++) {
                    if (result[k] == a[i][j]) {
                        exists = 1;
                        break;
                    }
                }
                if (!exists) {
                    result[count++] = a[i][j];
                }
            }
        }
    }

    if (count == 0) {
        printf("NOT FOUND");
    } else {
        sort(result, count);
        for (int i = 0; i < count; i++) {
            printf("%d ", result[i]);
        }
    }
    return 0;
}

• Time Complexity: O(mn + K^2) (với K là số lượng số chính phương tìm được, nhỏ nhất có thể là 1, lớn nhất là mn)
• Space Complexity: O(m*n)

Phương pháp này lưu trữ trực tiếp các số chính phương vào một mảng phụ.

• Khi gặp một số chính phương, ta kiểm tra xem nó đã tồn tại trong mảng phụ chưa bằng cách duyệt linear search.
• Nếu chưa có, thêm vào mảng.
• Cuối cùng, sắp xếp mảng phụ và in ra.
• Nhược điểm: Cần mảng lưu trữ lớn, và việc kiểm tra trùng lặp bằng duyệt mảng làm chậm chương trình khi có nhiều số chính phương.

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

Bài học kinh nghiệm

• Vì |A_ij| ≤ 10000, nên số chính phương trong ma trận không thể lớn hơn 10000. Điều này cho phép ta tối ưu hóa bằng cách dùng mảng đánh dấu (frequency array) thay vì các cấu trúc dữ liệu phức tạp.
• Sử dụng hàm sqrt() của thư viện <math.h> là cách nhanh nhất để kiểm tra một số có phải là bình phương không: tính căn bậc hai của nó, ép kiểu về số nguyên, rồi nhân lại xem có bằng giá trị ban đầu không.
• Để loại bỏ trùng lặp và tự động sắp xếp tăng dần, mảng đánh dấu (Approach 1) là hiệu quả nhất vì ta duyệt qua các chỉ số i từ 0 đến 100 (tự động tăng dần) và chỉ in ra nếu count[i] khác 0.

Lỗi thường gặp

• Quên kiểm tra số âm: Số âm không bao giờ là số chính phương (trong tập số nguyên thực). Cần kiểm tra if (x < 0) return 0; trước khi tính căn.
• Sai lệch số thực khi dùng sqrt(): Hàm sqrt() trả về số thực double. Khi ép kiểu (int), số thực 3.99999 sẽ thành 3. Cần kiểm tra kỹ bằng cách int r = (int)sqrt(x); if (r*r == x) ... hoặc dùng sai số.
• Tràn số nguyên: Nếu tính bình phương để kiểm tra (ví dụ for(i=0; i*i <= x; i++)), cần đảm bảo i*i không vượt quá giới hạn của kiểu dữ liệu. Với x <= 10000 thì không sao, nhưng với số lớn hơn cần cẩn thận. Dùng sqrt() an toàn hơn.