1. BÀI TOÁN XÂU TRONG CỰC ĐẠI
Xâu con:
S là xâu con của T nếu S nhận được bằng cách xoá đi một số ký tự nào đó trong T.
Ví dụ: ‘EAC’ là xâu con của ‘CEAEEC’
Xâu con chung:
Nếu xóa một số ký tự của hai xâu thì hai xâu con còn lại của chúng bằng nhau
Ví dụ: S1=‘ABCDAE’ và S2=‘XYACADK’ có xâu ‘ACD’ là xâu con chung có độ
dài cực đại.
Bài toán đặt ra:
Cho 2 xâu A, B. Tìm một xâu S là xâu con chung của A và B có độ dài cực đại.
- Input: File Input.doc có cấu trúc:
+ Dòng thứ nhất chứa xâu A
+ Dòng thứ hai chứa xâu B
- Output: File output.doc có cấu trúc:
Nếu bài toán vô nghiệm thì ghi số 0, ngược lại ghi như sau:
+ Dòng thứ nhất ghi số K là số kí tự của xâu chung S
+ Dòng thứ hai là xâu S gồm K kí tự.
BÀI GIẢI:
B1: Phân tích bài toán
Gọi M= length(A); N= length(B);
* Cần xây dựng mảng L[0 M, 0 N] với ý nghĩa: L[I,j] là độ dài của xâu chung dài
nhất của 2 xâu: A[0 i] và B[0 j].
* Bài toán ban đầu là: L[M,N].
Đương nhiên nếu một xâu là rỗng (số kí tự là 0) thì xâu con chung cũng là rỗng, vì
vậy:
L[0,j]=0 ∀ j, j=1 N.
L[i,0]=0 ∀ i, i=1 M.
B2: Giải pháp đệ quy
Với M ≥ I > 0 và N ≥ j > 0 thì:
+ Nếu A[i]=B[j] thì L[I,j] = L[i-1,j-1] +1
+ Nếu A[i] < > B[j] thì:

S:=A[i]+S;
i:=i-1;
j:=j-1;
End;
End;
* CÀI ĐẶT:
USES CRT;
CONST FI='INPUT.DOC'; FO='OUTPUT.DOC';
VAR F: TEXT; M,N: BYTE; A,B,S: STRING; CH:CHAR;
L: ARRAY[0 100,0 100] OF BYTE;
PROCEDURE DOC_INPUT;
VAR F: TEXT;
BEGIN
M:=0; N:=0;A:=''; B:='';
ASSIGN(F,FI); RESET(F);
WHILE NOT EOLN(F) DO
BEGIN
INC(M); READ(F,CH); A:=A+CH;
END;
READLN(F);
WHILE NOT EOLN(F) DO
BEGIN
INC(N); READ(F,CH); B:=B+CH;
END;
CLOSE(F);
END;
FUNCTION MAX(I,J: INTEGER) : INTEGER;
VAR P: INTEGER;
BEGIN
IF I>J THEN MAX:=I ELSE MAX:=J;

IF L[I,J]=L[I-1,J] THEN DEC(I)
ELSE
BEGIN
S:=A[I]+S;
DEC(I); DEC(J);
END;
END;
WRITE(F,S);
CLOSE(F);
END;
BEGIN
CLRSCR;
DOC_INPUT; LAPBANG; TONGHOP;
END.
2. BÀI TOÁN DU LỊCH
* Phát biểu bài toán:
Một người đi từ thành phố 0 đến thành phố n và có thể đi qua n-1 thành phố
khác 1, 2, . . ., n-1, theo lộ trình: 0 -> i
1
-> i
2
. . . -> i
k
-> n, trong đó: 0 < i
1
< i
2
<
i
k

for s:= 0 to n do
if (s= 0) then Tính l[0] và u[0]
else Tính l[s] và u[s]
End;
Cụ thể:
Procedure lapbang;
var s,k,ke: byte;
min,tam: integer;
begin
for s:=0 to n do
if (s=0) then
begin
l[0]:=0;
u[0]:=-1;
end
else
begin
ke:=0;
min:=max;
for k:=r to s-1 do
if (c[k,s]>0) then
begin
tam:=l[k]+c[k,s];
if (tam<min) then
begin
ke:=k;
min:=tam;
end;
end;
l[s]:=min;

close(f);
end;
procedure lapbang;
var s,k,ke:byte;
min,tam:integer;
begin
for s:=0 to n do
if (s=0) then
begin
l[0]:=0;
u[0]:=-1;
end
else
begin
ke:=0;
min:=max;
for k:=0 to s-1 do
if (c[k,s]>0) then
begin
tam:=l[k]+c[k,s];
if (tam<min) then
begin
ke:=k;
min:=tam;
end;
end;
l[s]:=min;
u[s]:=ke;
end;
end;

nếu ôn môn j trong i ngày thì được điểm là a[i,j]. Giả sử cho biết các a[i,j] (với
a[i,j] ≤ a[i+1,j]).
Tìm bộ x[j] (số ngày ôn môn j, j = 1 n) sao cho Σx[j] = m và sinh viên đạt
tổng điểm lớn nhất. (Σa[x[j], j] → max).
 Input:
- m ∈ N: số ngày ôn thi
- n ∈ N* : số môn ôn thi
- a[i,j] ∈ R: điểm đạt được khi ôn thi môn j trong i ngày. (i=0 m, j=1 n)
 Output:
x[j]: số ngày ôn thi môn j (j=1 n) sao cho Σx[j]=n và Σa[x[j],j] đạt max
b. Phân tích bài toán
Gọi P(r,s) là bài toán ôn thi, với:
• r ∈N là số ngày ôn thi.
• s ∈ N* là số môn ôn thi.
(Bài toán ban đầu là P(m,n))
Các giá trị cần tìm:
• diem[r,s]: tổng điểm lớn nhất Σa[x[j],j] của bài toán P(r,s).
• ngay[r,s]: số ngày ôn thi môn s (tức là x[s]) của bài toán P(r,s).
c. Giải pháp đệ quy
• Trường hợp suy biến: s=1 (chỉ có 1 môn)
- ngay[r,s]=ngay[r,1]=r (vì chỉ có 1 môn nên tận dụng hết tất cả r ngày để
ôn thi)
- diem[r,s]=diem[r,1]=a[r,1]
• Trường hợp đệ quy (s>1):
- diem[r,s] = max (a[k,s]+diem[r-k,s-1]) (k: số ngày ôn, 0≤k≤ r thi môn
s)
= a[k’,s]+diem[r-k’,s-1]
Trong đó:
 a[k,s] là điểm thi môn thứ s với k ngày ôn
 diem[r-k,s-1] là tổng điểm tối ưu của s-1 môn thi với r-k ngày ôn

diem[r,s]:=tam;
ngay[r,s]:=k1;
End;
e. Tổng hợp kết quả
Procedure TongHop;
Begin
r:=m;
For s:=n downto 1 do
begin
x[s]:=ngay[r,s];
r:=r-x[s];
end;
End;
• Độ phức tạp tính toán: O(n)
f. Cài đặt chương trình (bằng Turbo Pascal)
Program Sinh_vien_on_thi;
Uses crt;
Type Mang=array[1 50,1 50] of integer;
Var i,j,r,s,k,n,m,tam,k1:Integer;
A,ngay,diem:Mang;
X:Array[1 2500] of integer;
f:Text;
ch:Char;
{Tao file Input.txt de luu du lieu}
Procedure NhapDL;
Begin
Assign(f,'Input.txt');
Rewrite(f);
Write('Nhap so ngay on thi: ');
Readln(m);

End;
{Buoc lap bang}
Procedure Lap_bang;
Begin
DocDL;
For r:=0 to m do
begin
For s:=1 to n do
begin
If s=1 then
begin
ngay[r,1]:=r;
diem[r,1]:=A[r,1];
end
Else
begin
tam:=a[0,s]+diem[r,s-1];
k1:=0; {k1 la k'}
For k:=1 to r do
If tam<a[k,s]+diem[r-k,s-1] then
begin
tam:=a[k,s]+diem[r-k,s-1];
k1:=k;
end;
diem[r,s]:=tam;
ngay[r,s]:=k1;
end;
Write(diem[r,s]:5,'/',ngay[r,s],' ');
end;
Writeln;

Readln(ch);
If upcase(ch)<>'K' then
NhapDL;
Writeln;
Writeln('* DU LIEU VAO: ');
HienthiDL;
Readln;
Writeln('* LAP BANG');
Lap_bang;
Writeln;
Writeln('* KET QUA: ');
Tong_hop;
Write('Tong diem: ',diem[m,n]);
Readln;
END.