Tính lũy thừa ma trận trong C/C++

Hướng dẫn cách tính lũy thừa ma trận - Ma trận là một chủ đề quan trọng trong ngành lập trình và có ứng dụng rộng rãi trong nhiều lĩnh vực như web, game, AI và lập trình thi đấu. Trong bài viết này, chúng ta sẽ tìm hiểu về phép lũy thừa ma trận, cách tối ưu và tầm quan trọng của nó.

Phép nhân ma trận

Phép nhân ma trận là bước tiền đề cho phép lũy thừa ma trận. Khi hai ma trận có cùng kích thước, chúng có thể được cộng hoặc trừ phần tử tương ứng. Tuy nhiên, phép nhân ma trận chỉ có thể thực hiện được khi số cột của ma trận đầu tiên bằng số hàng của ma trận thứ hai.

Ví dụ, cho hai ma trận A và B: A = [[1, 2], [2, 3], [2, 5]] B = [[1, 2, 3, 4], [1, 3, 5, 7]]

Kết quả của phép nhân A và B (A * B) sẽ là ma trận C có kích thước 3x4. Các phần tử của ma trận C được tính theo công thức:

C[i][j] = A[i][1] B[1][j] + A[i][2] B[2][j] + A[i][3] B[3][j] + A[i][4] B[4][j]

Phép lũy thừa ma trận

Để tính lũy thừa bậc n của một ma trận, ta sử dụng phép nhân ma trận. Kết quả của phép nhân ma trận chính là ma trận thu được khi nhân ma trận gốc với chính nó n lần.

Lưu ý rằng chỉ ma trận vuông mới có thể thực hiện được phép lũy thừa. Ví dụ, cho ma trận A: A = [[1, 2], [2, 3]]

Kết quả của A^2 (A * A) là ma trận C: C = [[5, 8], [8, 13]]

Ứng dụng: Tìm số Fibonacci thứ N

Một trong những ứng dụng quan trọng của lũy thừa ma trận là tìm số Fibonacci thứ N. Số Fibonacci được tính dựa trên quy luật:

F(1) = 1, F(2) = 1 F(n) = F(n-1) + F(n-2)

Ví dụ, để tìm số Fibonacci thứ 4, ta sử dụng ma trận Fibonacci: Fibonacci = [[1, 1], [1, 0]]

Kết quả là ma trận C: C = [[3], [2]]

Để tính toán số Fibonacci thứ N, ta sử dụng công thức lũy thừa ma trận: C = Fibonacci^N

Dưới đây là một ví dụ về cách tính số Fibonacci thứ N sử dụng lũy thừa ma trận trong C++:

#include 
#include 

typedef std::vector> matrix;

matrix matrix_multiply(matrix a, matrix b) {
    int m = a.size(); // Chiều dài 1 cạnh của ma trận
    matrix c(m, std::vector(m)); // Khởi tạo ma trận kết quả
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            c[i][j] = 0; // Đưa phần tử của ma trận kết quả về 0 trước khi tính toán
            for (int k = 0; k < m; k++) {
                c[i][j] += a[i][k] * b[k][j]; // Cộng vào kết quả
            }
        }
    }
    return c;
}

matrix power(matrix a, int b) {
    if (b == 1) {
        return a;
    } else {
        return matrix_multiply(a, power(a, b - 1));
    }
}

int main() {
    matrix fibonacci = {{1, 1}, {1, 0}};
    std::cout << "Nhap so Fibonacci ma ban muon tim kiem: ";
    int n;
    std::cin >> n;
    matrix answer = power(fibonacci, n);
    std::cout << "So Fibonacci thu " << n << " la: " << answer[1][0] << std::endl;
}

Với đoạn code trên, bạn có thể tìm số Fibonacci bất kỳ chỉ trong O(logn) thay vì O(n) như phương pháp truyền thống. Ngoài ra, bạn cũng có thể thử các bài tập thực hành về lũy thừa ma trận để nâng cao kỹ năng lập trình của mình.

Hãy thử áp dụng lũy thừa ma trận vào các bài toán của bạn và khám phá những ứng dụng mới của nó.