Hiểu bài toán

Bài toán yêu cầu tính tổng các phần tử nằm trên đường chéo chính của một ma trận vuông. Đường chéo chính bao gồm các phần tử tại vị trí có chỉ số hàng và cột bằng nhau (A[i][i]). Input gồm số nguyên n (kích thước ma trận) và n*n số nguyên là các phần tử của ma trận. Output là tổng của các phần tử trên đường chéo chính.

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

Cách Duyệt ma trận 2 chiều

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    int A[n][n];

    int i, j;
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            scanf("%d", &A[i][j]);
        }
    }

    int tong = 0;
    for (i = 0; i < n; i++){
        tong += A[i][i];
    }

    printf("%d", tong);

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Cách tiếp cận này sử dụng ma trận 2 chiều để lưu trữ dữ liệu. Đầu tiên, chương trình đọc vào kích thước n và sau đó sử dụng hai vòng lặp lồng nhau để đọc tất cả các phần tử của ma trận. Sau đó, nó duyệt qua các phần tử trên đường chéo chính (với i = j) và cộng chúng lại. Phương pháp này dễ hiểu và mô phỏng đúng cách nhìn trực quan về ma trận.

Cách Duyệt mảng 1 chiều

#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main(){
    int n;
    scanf("%d",&n);
    int a[n*n];
    for(int i=0;i<n*n ; i++){
        scanf("%d",&a[i]);
    }
    int s=0;
    for(int i=0;i<n*n;i+=n+1){
        s+=a[i];
    }
    printf("%d",s);



    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Cách tiếp cận này lưu trữ tất cả các phần tử của ma trận vào một mảng 1 chiều. Để tính tổng đường chéo chính, nó nhận thấy rằng các phần tử nằm ở các vị trí chỉ số 0, n + 1, 2*(n + 1), ... trong mảng 1 chiều. Do đó, vòng lặp cộng dồn các phần tử tại các vị trí này với bước nhảy là n + 1. Phương pháp này tiết kiệm bộ nhớ hơn một chút so với việc khai báo ma trận 2 chiều (trong một số trường hợp) và có thể tối ưu hóa việc nhập dữ liệu.

Cách Tối ưu hóa không gian (Xử lý khi nhập)

#include <stdio.h>

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

    int sum = 0;
    int val;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &val);
            if (i == j) {
                sum += val;
            }
        }
    }

    printf("%d", sum);

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất về bộ nhớ. Thay vì lưu trữ toàn bộ ma trận, ta chỉ cần một biến để lưu tổng. Trong quá trình đọc dữ liệu vào (vòng lặp lồng nhau), ta kiểm tra xem chỉ số hàng i có bằng chỉ số cột j không. Nếu có, ta cộng giá trị đó vào biến tổng. Cách này không cần lưu ma trận, chỉ cần O(1) bộ nhớ phụ.

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

Bài học kinh nghiệm

• Đường chéo chính của ma trận vuông gồm các phần tử A[i][i].
• Trong bộ nhớ, ma trận 2 chiều có thể được mô phỏng bằng mảng 1 chiều với quy tắc tính chỉ số: index = i * n + j.
• Có thể tính tổng ngay khi nhập dữ liệu mà không cần lưu trữ toàn bộ ma trận.

Lỗi thường gặp

• Quên khai báo biến tổng hoặc khởi tạo nó bằng 0 trước khi sử dụng.
• Sai quy tắc tính chỉ số khi sử dụng mảng 1 chiều để mô phỏng ma trận (ví dụ: quên bước nhảy n+1 đúng).
• Lỗi truy cập ngoài biên mảng nếu vòng lặp chạy sai điều kiện (i < n thay vì i <= n).