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

0
139
88 / 100
Hướng dẫn cách tính lũy thừa ma trận – Ma trận là một chủ đề không còn xa lạ với những người dấn thân vào ngành lập trình. Trong hầu hết tất cả các nhánh của ngành IT như web, game, AI, lập trình thi đấu,… ma trận đều giữ một vị trí đặc biệt quan trọng. Hôm nay chúng ta sẽ tìm hiểu về phép lũy thừa ma trận, cách tối ưu cùng với tầm quan trọng của nó.

Nội dung bài viết gồm 3 phần, đầu tiên chúng ta sẽ đi tìm hiểu về phép nhân ma trận (bởi vì phép lũy thừa được thực hiện dựa trên phép nhân). Sau đó, chúng ta sẽ đi tìm hiểu về phép lũy thừa ma trận. Cuối cùng, chúng ta sẽ sử dụng ứng dụng của phép lũy thừa ma trận trong 1 bài toán rất điển hình là tính số fibonacci thứ N. Chúng ta cùng bắt đầu nhé.

Để có thể nắm rõ bài viết này, độc giả cần có kiến thức lập trình căn bản, bao gồm kiến thức cấu trúc điều khiển, vòng lặp, hàm đệ quy và mảng 2 chiều. Các kiến thức trên đều có trong khóa học C căn bản của LTKK.

Phép nhân ma trận

Trong toán học, ma trận (tiếng anh: Matrix) là một mảng chữ nhật– các số, ký hiệu, hoặc biểu thức, sắp xếp theo hàng và cột – mà mỗi ma trận tuân theo những quy tắc định trước. Từng ô trong ma trận được gọi là các phần tử hoặc mục.

Lũy thừa ma trận

Khi các ma trận có cùng kích thước (chúng có cùng số hàng và cùng số cột) thì có thể thực hiện phép cộng hoặc trừ hai ma trận trên các phần tử tương ứng của chúng.

Tuy vậy, quy tắc áp dụng cho phép nhân ma trận chỉ có thể thực hiện được khi ma trận thứ nhất có số cột bằng số hàng của ma trận thứ hai:

Lũy thừa ma trận

Với mỗi phần tử của ma trận đích được tính theo công thức: c[i, j] = \sum_{x = 1}^{n}a[i, x] \times b[x, j] với n là chiều rộng của ma trận a. Nói đơn giản thì, phần tử ô [i, j] của ma trận kết quả là tổng của lần lượt các tích đôi một phần tử hàng i của ma trận thứ nhất và cột j của ma trận thứ hai.

Chú ý: Với hai ma trận A và B, A \times B \neq B \times A

Xét ví dụ nhân một ma trận 3×2 và một ma trận 2×4:

Lũy thừa ma trậnCho ma trận A kích thước 3×2 như sau:

Và một ma trận B kích thước 2×4:

Gọi ma trận kết quả của A \times B là C. Ma trận kết quả sẽ có số hàng bằng số hàng của ma trận đầu tiên và số cột bằng số cột của ma trận thứ hai, nên C sẽ có kích thước là 3×4.

Các phần tử của C sẽ được tính toán như sau:

Code minh họa cho ví dụ trên (Lưu ý từ khóa auto chỉ có từ C++11 hoặc mới hơn):

Kết quả chạy chương trình:

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

Tương tự với số nguyên, kết quả phép lũy thừa bậc n của một ma trận x là ma trận thu được khi nhân x với chính nó n lần.

Lưu ý: Chỉ ma trận vuông mới có thể thực hiện phép lũy thừa.

Code lũy thừa một ma trận (C++11):

Kết quả chạy chương trình:

Tìm số Fibonacci thứ N

Một trong những ứng dụng rộng rãi nhất của lũy thừa ma trận đó là để tìm số Fibonacci thứ n. Để tìm 1 số Fibonacci, chúng ta có thể dựa vào quy luật sau:

Lũy thừa ma trận

Với F(1)=1, F(2) = 1

Chương trình sử dụng lũy thừa ma trận để tính số Fibonacci thứ n (C++ 11):

Giả sử n = 4, đây là output của chương trình:

Bài tập thực hành

Hi mọi người, mình là Nguyễn Thanh Châu, sinh viên Học viện Công Nghệ Bưu Chính Viễn Thông, thành viên của đội tuyển ICPC PTIT. Sở thích của mình là nghe nhạc, chơi game, đọc sách, các bạn có thể liên hệ với mình tại: facebook.com/terrorblade7227.
Theo dõi
Thông báo của
guest
0 Bình luận
Phản hồi nội tuyến
Xem tất cả bình luận