MỘT
SỐ DẠNG TOÁN ĐIỂN HÌNH
I.
Dạng
1: Lớp bài toán di chuyển
1.
Mô
hình:
Một người may mắn gặp một ma
trận kim cương gồm MxN ô. Giá trị A[i,j] (A[i,j] là một số nguyên dương) là lượng
kim cương có ở ô dòng i cột j. Người này chỉ được xuất phát từ một ô mép bên trái
của ma trận và di chuyển sang mép bên phải. Từ ô (i,j) người này chỉ có thể di
chuyển sang 1 trong 3 ô (i-1,j+1), (i,j+1) hoặc (i+1, j+1). Di chuyển qua ô nào
thì người đó được phép mang theo lượng kim cương ở ô đó. Em hãy giúp người này
di chuyển theo đường đi nào có thể nhận được nhiều kim cương nhất.
Inputdata: file văn bản vanmay.inp:
Ø Dòng thứ nhất gồm 2 số nguyên M, N (0<=M, N<=5000)
cách nhau 1 khoảng trắng
Ø M dòng tiếp theo mỗi dòng ghi một hàng các số nguyên của
ma trận (các số nguyên có giới hạn từ 109).
Outputdata: file văn bản vanmay.out:
ghi tổng lượng kim cương nhiều nhất có thể có được.
|
VANMAY.INP
|
VANMAY.OUT
|
|
2 3
1 2 5
3 4 6
|
13
|
+
Hãy tìm qui tắc đi.
(i-1,j-1) (i-1,j+1)
(i,j-1) (i,j) (i,j+1)
(i+1,j-1) (i+1,j+1)
+
Tìm công thức truy hồi
Gọi F[i,j] là giá trị lớn nhất có được khi di
chuyển đến ô (i,j). Như vậy, có 3 ô có thể di chuyển đến ô (i,j) là ô (i,j-1),
ô(i-1,j-1) và ô (i+1, j-1). Vậy chúng ta có công thức truy hồi sau:
·
F[1,1]=A[1,1] ( i=1, j=1);
·
F[i,j]=max
(F(i,j-1), F(i-1,j-1), F(i+1,j-1))+a[i,j] với i>1
+
Xây dựng bảng phương án
 i j |
0
|
1
|
2
|
3
|
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
1
|
5
|
12
|
|
2
|
0
|
3
|
7
|
13
|
+
Truy vết
Xuất phát từ ô kết quả ( ô đạt giá
trị lớn nhất ở bìa phải ma trận). Tại ô (i,j) đi qua trái chọn ô lớn nhất trong
3 ô
+
Cài đặt
Bài
toán 1: Tam giác số (đã có tài liệu)
II.
Dạng
bài toán biến đổi xâu
1. Bài toán: Tìm xâu con chung dài nhất
Xâu
ký tự A được gọi là xâu con của xâu ký tự B nếu ta có thể xoá đi một số ký tự
trong xâu B để được xâu A.
Cho
biết hai xâu ký tự X(X=<x1, x2, ..., xn>)
và Y(Y=<y1, y2, ...,ym>), hãy tìm xâu ký
tự Z có độ dài lớn nhất và là con của cả X và Y.
-
DL vào: File LCS.INP gồm:
Dòng 1: chứa xâu X
Dòng 2: chứa xâu Y
-
DL ra: File LCS.OUT: chứa độ dài xâu z
tìm được
|
LCS.INP
|
LCS.OUT
|
|
ALGORITHM
LOGARITHM
|
7
|
-
Tìm công thức truy hồi
-
Lập bảng phương án và truy vết
Hướng
dẫn
-
Ta thấy dộ dài dãy con chung phụ thuộc
vào vị trí i đang xét của xâu X và vị trí j đang xét của xâu Y. Do đó hàm mục
tiêu sẽ phụ thuộc vào hai tham số biến thiên là i và j. Vì thế để cài đặt cho bảng
phương án ta cần sử dụng mảng 2 chiều.
Giả sử F[i,j] là độ dài lớn nhất của dãy
con chung của 2 dãy sau:
+
x1, x2,..., xn
+
y1,
y2,..., yn
Công
thức truy hồi để tính F[i,j]:
+ Nếu i=0 hay j=0 thì F[i,j]=0
+ Nếu i>0 và j>0 và xi
= yj thì F[i,j]=1+F[i-1,j-1];
+ Nếu i>0 và j>0 và xi<>
yj thì F[i,j]= max (F[i-1,j], F[i,j-1]);
Khi đó F[n,m] chính là độ dài xâu con
chung dài nhất của hai xâu X và Y.
Bảng
phương án và truy vết
|
|
|
A
|
L
|
G
|
O
|
R
|
I
|
T
|
H
|
M
|
|
|
0
|
 0 |
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
L
|
 0 |
0
|
 1 |
 1 |
1
|
1
|
1
|
1
|
1
|
1
|
|
O
|
0
|
0
|
 1 |
1
|
2
|
2
|
2
|
2
|
2
|
2
|
|
G
|
0
|
0
|
1
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
|
A
|
0
|
1
|
1
|
2
|
 2 |
2
|
2
|
2
|
2
|
2
|
|
R
|
0
|
1
|
1
|
2
|
2
|
 3 |
3
|
3
|
3
|
3
|
|
I
|
0
|
1
|
1
|
2
|
2
|
3
|
 4 |
4
|
4
|
4
|
|
T
|
0
|
1
|
1
|
2
|
2
|
3
|
4
|
 5 |
5
|
5
|
|
H
|
0
|
1
|
1
|
2
|
2
|
3
|
4
|
5
|
 6 |
6
|
|
M
|
0
|
1
|
1
|
2
|
2
|
3
|
4
|
5
|
6
|
7
|
+ Cài đặt:
