Tài liệu Phép toán ma trận và ứng dụng giải một số bài toán tin học

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 c:matrix; i,j:longint; begin for i:= 1 to n do for j:= 1 to n do c[i,j]:=a[i,j]+b[i,j]; 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.2. Phép nhân hai ma trận Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận bên phải. Nếu ma trận A có kích thước m x n và ma trận B có kích thước n x p, thì ma trận tích C = A x B có kích thước m x p, phần tử đứng ở hàng thứ i, cột thứ j xác định bởi: Cij = ai,1b1,j + ai,2b2,j + ... + ai,nbn,j Ví dụ: Phép nhân ma trận có tính chất sau: • Tính chất kết hợp: (A x B) x C = A x (B x C) • Tính chất phân phối: (A + B) x C = A x C + B x C; C x (A + B) = C x A + C x B • Phép nhân ma trận không có tính giao hoán, A x B ≠ B x A, ví dụ: trong khi Cài đặt: Function Mul(a,b:maxtrix):maxtrix; var i,j,k:longint; c:maxtrix; 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); exit(c); end; 3. 3.1. ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC LATGACH4 Nguồn bài: http://vn.spoj.com/problems/LATGACH4/ [3] Cho một hình chữ nhật kích thước 2xN (1<=N<10^9). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát. Input Gồm nhiều test, dòng đầu ghi số lượng test T ( T<=100 ). T dòng sau mỗi dòng ghi một số N. Output Ghi ra T dòng là số cách lát tương ứng lấy phần dư cho 111539786. Example Input Output 3 1 1 2 2 3 3 Thuật toán: Gọi fi là số cách lát gạch cho hình chữ nhật 2 x i. Ta tìm được dãy Fibonacci: 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. Nếu dùng vét cạn, chạy 1 vòng lặp từ đầu đến cuối thì độ phức tạp sẽ là O(N) không khả thi khi N~109. Phân tích như sau: f1 = f1 f2 = f2 f3 = f4 – f2 f4 = f5 – f3 f5 = f6 – f4 fn-1 = fn – fn-2 fn = fn+1 – fn …. Tổng hai vế: Sn = fn+1 – f3 + f1 (*) ⎡f ⎤ ⎡ f ⎤ ⎣ 2⎦ ⎣ Mà: An−1.⎢ 1 ⎥ = ⎢ n ⎥ => Tính fn+1 sẽ có độ phức tạp O(logN), sau khi tính xong fn+1 thế vào (*) f f n+1 ⎦ ta được Sn, vậy độ phức tạp của Sn cũng chỉ là O(logN). 4 PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC 3.2. Trò chơi lò cò Nguồn bài: Đề Thi lần VIII, Tin học 11, chuyên Duyên Hải và Đồng bằng Bắc Bộ, 2015 [2]. http://vn.spoj.com/problems/DHLOCO/ [3] Carnaval Hạ Long 2015 với chủ đề “Hội tụ tinh hoa - Lan tỏa nụ cười”, điểm mới của lễ hội là sự song hành giữa biểu diễn nghệ thuật “Nơi tinh hoa hội tụ” và diễu hành đường phố “Nụ cười Hạ Long” với sự góp mặt của hơn 2000 diễn viên quần chúng. Có rất nhiều chương trình vui chơi được tổ chức, một trong những trò chơi thu hút được nhiều du khách tham gia đó là trò chơi nhảy lò cò, cụ thể: người chơi cần vượt qua một đoạn đường dài n mét, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là 1 mét, 2 mét, 3 mét. Một cách đi chuyển đúng là dãy các bước nhảy có tổng đúng bằng n. Yêu cầu: Cho n và M, gọi K là số cách đi chuyển đúng khác nhau để đi hết đoạn đường n mét, hãy tính phần dư của K chia M. Dữ liệu: Vào từ file văn bản LOCO.INP: gồm một dòng chứa hai số nguyên dương n, M (M ≤ 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 ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ ⎢ ⎥ 2 ⎢ n −1 ⎢ A.⎢ f 2 ⎥ = ⎢ f 3 ⎥ ; A.⎢ f 3 ⎥ = ⎢ f 4 ⎥ => A .⎢ f 2 ⎥ = ⎢ f 4 ⎥ . Quy nạp: A .⎢ f 2⎥⎥ = ⎢⎢ f n+1 ⎥⎥ ⎢⎣ f 3 ⎥⎦ ⎢⎣ f 4 ⎥⎦ ⎢⎣ f 4 ⎥⎦ ⎢⎣ f 5 ⎥⎦ ⎢⎣ f 3 ⎥⎦ ⎢⎣ f 5 ⎥⎦ ⎢⎣ f 3⎥⎦ ⎢⎣ f n+2 ⎥⎦ fn được tính với độ phức tạp O(logN). Cài đặt: type matrix=array[1..3,1..3] of int64; const fi=''; 5 PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC fo=''; f:text; a,b:matrix; n:int64; m:int64; procedure input; begin assign(f,fi); reset(f); readln(f,n,m); 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; begin a[1,1]:=0; a[1,2]:=1; a[1,3]:=0; a[2,1]:=0; a[2,2]:=0; a[2,3]:=1; a[3,1]:=1; a[3,2]:=1; a[3,3]:=1; b:=Power(a,n-1); end; procedure output; begin assign(f,fo); rewrite(f); case n of 1: writeln(f,1); 2: writeln(f,2 mod m); 3: writeln(f,4 mod m); else 6 PHÉP TOÁN MA TRẬN VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TIN HỌC begin solve; writeln(f,(b[1,1]+b[1,2]*2+b[1,3]*4)mod m); end; end; close(f); end; BEGIN input; output; 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/ [4] Website: https://vi.wikipedia.org/wiki/Ma_trận. 7