PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC
MÃ: TI19
Tóm tắt – Chuyên đề trình bày các phép toán trên ma trận như cộng, nhân và lũy thừa. Ứng
dụng các phép toán đó để giải một số bài toán học sinh giỏi môn Tin học.
1.

GIỚI THIỆU
Ma trận và phép toán trên ma trận được ứng dụng rộng rãi trong Toán học, Kinh tế học,

Vật lý học,… và tất nhiên có cả trong Tin học (Đồ họa máy tính, Xử lý ảnh, Lý thuyết trò chơi,
lý thuyết đồ thị,…). Ma trận và phép toán trên ma trận còn thường gặp trong các bài toán học
sinh giỏi Tin học. Khái niệm ma trận có lẽ quen thuộc với học sinh, nhưng khái niệm về phép
toán trên ma trận thì gần như không có trong chương trình Toán phổ thông và chỉ được đề cập
rất ít trong Tài liệu giáo khoa chuyên tin [1]. Chuyên đề “Phép toán ma trận và Ứng dụng giải
một số bài toán Tin học” được viết nhằm bổ sung một phần kiến thức đó cho học sinh.
Trong chuyên đề có sử dụng một số kiến thức cơ bản như dãy Fibonacci, quan hệ đồng dư,
xử lý số lớn và Hash [1].
2.
2.1.

PHÉP TOÁN MA TRẬN
Phép cộng hai ma trận
Phép cộng hai ma trận có cùng kích thước m x n, ma trận tổng C = A+B có cùng kích

thước m x n, phần tử đứng ở hàng i, cột j xác định bởi:
ci,j = ai,j + bi,j, với 1 ≤ i ≤ m và 1 ≤ j ≤ n.
Ví dụ:

Cài đặt:
Function Add(a,b:matrix):matrix;
var

begin
for i:= 1 to m do
for j:= 1 to p do
begin
c[i,j]:=0;
for k:= 1 to n do
c[i,j]:=c[i,j]+a[i,k]*b[k,j];
end;

2


PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC
exit(c);
end;

2.3. Phép lũy thừa bậc k của ma trận A
Phép lũy thừa bậc k của ma trận A tức là thực hiện nhân ma trận A với chính nó k lần.
Ví dụ:

Cài đặt: O(logK):
Function Power(a:matrix; k:longint):matrix;
var
c:matrix;
begin
if k=1 then exit(a);
c:=power(a,k div 2);
c:=mul(c,c);
if k mod 2=1 then
c:=mul(c,a);


3


PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC

f1 = 1, f2 = 2, f3 = f1 + f2 và fn = fn-1 + fn-2.
Nếu tính fn bằng vòng lặp chạy từ 1 đến N sẽ có độ phức tạp O(N).
Cải tiến:
⎡0 1⎤
A=⎢
⎥
⎣1 1⎦

⎡f ⎤ ⎡f ⎤
⎡f ⎤ ⎡f ⎤
⎡f ⎤ ⎡f ⎤
A .⎢ 1 ⎥ = ⎢ 2 ⎥ ; A .⎢ 2 ⎥ = ⎢ 3 ⎥ => A2 .⎢ 1 ⎥ = ⎢ 3 ⎥ ; Quy nạp ta được:
⎣ f 2 ⎦ ⎣ f3 ⎦
⎣ f2 ⎦ ⎣ f4 ⎦
⎣ f3 ⎦ ⎣ f 4 ⎦
⎡f ⎤ ⎡ f ⎤
An−1.⎢ 1 ⎥ = ⎢ n ⎥
⎣ f 2 ⎦ ⎣ f n+1 ⎦

fn được tính dựa trên An-1 mà ma trận lũy thừa này như đã trình bày ở trên có độ phức tạp là
O(logN), như vậy tính fn sẽ có cùng độ phức tạp là O(logN).
Mở rộng bài toán: Hãy đếm tổng số cách lát của tất cả các hình chữ nhật có kích thước 2x1,
2x2,…, 2 x n?
Câu hỏi này tương đương với tính Sn = f1 + f2 +…+ fn.


f6 – f4

fn-1

=

fn – fn-2

fn

=

fn+1 – fn

….

Tổng hai vế:
Sn

=

fn+1 – f3 + f1 (*)
⎡f ⎤

⎡ f ⎤

⎣ 2⎦

⎣

2015);
Kết quả: Đưa ra file văn bản LOCO.OUT một số nguyên là phần dư của K chia M.
Ví dụ:
LOCO.INP
LOCO.OUT
5 100
13
Ghi chú:
• Có 20% số test ứng với 20% số điểm có n ≤ 20;
• Có 40% số test ứng với 40% số điểm có n ≤ 106;
• Có 40% số test còn lại ứng với 40% số điểm có n ≤ 1015.
Tóm tắt:
Cho dãy F được xác định như sau:
f1 = 1, f2 = 2, f3 = 4, fn = fn-3 + fn-2 + fn-1
Thuật toán: Tương tự như bài trên, chỉ khác A là ma trận kích thước 3x3
⎡0 1 0 ⎤
A = ⎢⎢0 0 1⎥⎥.
⎢⎣1 1 1⎥⎦
⎡ f1 ⎤ ⎡ f 2 ⎤
⎡ f 2 ⎤ ⎡ f3 ⎤
⎡ f1 ⎤ ⎡ f 3 ⎤
⎡ f 1⎤ ⎡ f n ⎤
⎢
⎥
⎢
⎥
⎢
⎥
⎢
⎥

close(f);
end;
var

function Mul(a,b:matrix):matrix;
var c:matrix;
k,u,v:longint;
begin
for u:=1 to 3 do
for v:=1 to 3 do
begin
c[u,v]:=0;
for k:=1 to 3 do
c[u,v]:=(c[u,v]+a[u,k]*b[k,v])mod m;
end;
exit(c);
end;
function Power(a:matrix;k:int64):matrix;
var b:matrix;
begin
if k=1 then exit(a)
else
begin
b:=Power(a,k div 2);
b:=Mul(b,b);
if k mod 2 =1 then b:=Mul(b,a);
end;
exit(b);
end;
procedure solve;

END.

CÁC BÀI TOÁN TỰ LUYỆN
http://vn.spoj.com/problems/VMATRIX/ [3]

(Ma trận, Hash)

http://vn.spoj.com/problems/LATGACH/ [3]

(Ma trận A 2x2)

http://vn.spoj.com/problems/ONE4EVER/ [3] (Tìm ma trận A)
http://vn.spoj.com/problems/VOSTRIBO/ [3] (Làm giống bài mở rộng của LATGACH4, lúc
này sẽ dùng ma trận A3x3, hoặc phân tích Sn = Sn-1 + fn lúc này tìm A4x4)
4.

KẾT LUẬN
Chuyên đề đã trình bày về phép toán trên ma trận và ứng dụng các phép toán đó để giải

một số bài toán học sinh giỏi Tin học. Giảm độ phức tạp của bài toán từ O(N) xuống còn
O(logN). Để vận dụng được đòi hỏi học sinh phải lý giải thêm cách tìm ra ma trận A, nắm thêm
lý thuyết về đồng dư và xử lý số lớn. Chuyên đề giúp bổ sung thêm một lượng kiến thức nhất
định không chỉ Tin học mà còn cả Toán học, giúp học sinh làm bài tốt hơn.

TÀI LIỆU THAM KHẢO
[1] Hồ Sĩ Đàm và các cộng sự. Tài liệu giáo khoa chuyên Tin tập 1, 2, 3. 2009.
[2] Hội các trường Chuyên Vùng Duyên Hải và Đồng Bằng Bắc Bộ. Đề Thi Chọn HSG Lần

VIII - Tin học 11. 18/04/2015.
[3] Website: http://vn.spoj.com/