Editorial for ptit002: Tìm định thức của ma trận vuông

Hiểu bài toán

Bài toán yêu cầu tính định thức của một ma trận vuông kích thước 3x3. Ma trận đầu vào gồm 9 số nguyên, được nhập theo thứ tự hàng. Định thức (determinant) của ma trận 3x3 có thể tính theo công thức: det = a(ei − fh) − b(di − fg) + c(dh − eg) hoặc công thức Sarrus: det = aei + bfg + cdh − ceg − bdi − afh Trong đó ma trận: [a b c] [d e f] [g h i] Đầu ra là một số nguyên duy nhất là giá trị định thức.

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

Cách Công thức trực tiếp với biến riêng lẻ

#include <stdio.h>
int main(){
    long long a,b,c,d,e,f,g,h,i,k;
    scanf("%lld %lld %lld\n", &a, &b, &c);
    scanf("%lld %lld %lld\n", &d, &e, &f);
    scanf("%lld %lld %lld", &g, &h, &i);
    k = a*e*i + b*g*f + d*h*c - c*e*g - d*b*i - h*f*a;
    printf("%lld", k);
    return 0;
}

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

Sử dụng công thức Sarrus để tính định thức. Khai báo 9 biến riêng cho từng phần tử ma trận, nhập dữ liệu bằng scanf, rồi tính kết quả theo công thức:

• Cộng các tích theo đường chéo chính: aei + bfg + cdh
• Trừ các tích theo đường chéo phụ: ceg + afh + bdi Cách này ngắn gọn, dễ hiểu nhưng cần khai báo nhiều biến.

Cách Mảng 2 chiều và công thức ma trận con

#include <stdio.h>
int main() {
    long long a[3][3];
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            scanf("%lld", &a[i][j]);
    long long det = a[0][0]*(a[1][1]*a[2][2] - a[1][2]*a[2][1])
                  - a[0][1]*(a[1][0]*a[2][2] - a[1][2]*a[2][0])
                  + a[0][2]*(a[1][0]*a[2][1] - a[1][1]*a[2][0]);
    printf("%lld\n", det);
    return 0;
}

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

Sử dụng mảng 2 chiều để lưu ma trận, tính định thức theo công thức: det = a00(a11a22 - a12a21) - a01(a10a22 - a12a20) + a02(a10a21 - a11*a20) Cách này có cấu trúc dữ liệu rõ ràng, dễ mở rộng nếu cần xử lý ma trận lớn hơn và dễ kiểm tra chéo.

Cách Tách thành tổng và hiệu các tích (công thức Sarrus có biến)

#include <stdio.h>
#define ll long long
int main(){
    ll n = 3;
    ll a[3][3];
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < n; j++){
            scanf("%lld", &a[i][j]);
        }
    }
    ll res = a[0][0] * a[1][1] * a[2][2] + a[1][0] * a[0][2] * a[2][1] + a[2][0] * a[0][1] * a[1][2];
    ll sum = a[2][0] * a[1][1] * a[0][2] + a[1][0] * a[0][1] * a[2][2] + a[0][0] * a[2][1] * a[1][2];
    printf("%lld", res - sum);
    return 0;
}

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

Thực chất vẫn dùng công thức Sarrus nhưng tách riêng tổng các tích theo đường chéo chính (res) và đường chéo phụ (sum), sau đó trả về res - sum. Cách này cũng dễ kiểm tra tính đúng đắn từng nhóm tích, nhưng cần lưu ý thứ tự các phần tử trong công thức.

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

Bài học kinh nghiệm

• Định thức của ma trận 3x3 có công thức cố định, có thể dùng Sarrus hoặc khai triển theo hàng/cột.
• Nên dùng kiểu dữ liệu long long để tránh tràn số nếu các phần tử lớn.

Lỗi thường gặp

• Nhập sai thứ tự các phần tử do nhập từng dòng hoặc nhập trộn thứ tự hàng.
• Sai dấu trong công thức Sarrus, đặc biệt là các tích theo đường chéo phụ.
• Quên ký hiệu \n trong scanf có thể gây lỗi nhập liệu.