Tài liệu bồi dưỡng thường xuyên dành cho giáo viên THCS môn Tin Học

 Đặt trị true cho hàm Next. Next = true có nghĩa là tìm được hoán vị sát sau hoán vị s. 
Chú ý
Khi khởi trị hoán vị đơn vị ta sử dụng phần tử s[0] = 0 làm lính canh. Nhờ vậy, khi duyệt ngược để tìm điểm gãy ta không phải kiểm tra giới hạn mảng. Thay vì viết
i := n-1;
while (i > 0) and (s[i] > s[i+1]) do i:= i-1;
Ta chỉ cần viết
i := n-1;
while (s[i] > s[i+1]) do i := i-1;
Hàm Next được mô tả như sau:
function Next(n: integer): Boolean;
var	i, j, t: integer;
begin 
Next := false; i := n-1;
while (s[i] > s[i+1]) do i:= i-1;
if i = 0 then exit;
{ s[i] < s[i+1], i là điểm gãy }
j := n; { Tìm điểm vượt a[j] > a[i] }
while (s[j] < s[i]) do j := j-1; 
{ Đổi chỗ s[i] , s[j] }
t:= s[i]; s[i]:= s[j]; s[j]:= t;
{ Lật s[i+1..n] } i:= i+1; j:= n; 
while i < j do
begin 
 t:= s[i];s[i]:= s[j]; s[j]:= t; 
 i:= i+1; j:= j-1;
end;
Next:= true;
end;
Thí dụ, với n = 8, giả sử ta đã ghi được hoán vị s = 74286531, khi đó hoán vị sát sau s sẽ được xây dựng như sau:
j
k
w 
m
n
o
{ 
q
S
7
4
2
8
6
5
3
1
Tìm điểm gãy: i = 3, vì s[3] < s[4]
7
4
2
8
6
5
3
1
Tìm điểm vượt: j = 7, vì s[7] > s[3]
7
4
2
8
6
5
3
1
Đổi chỗ điểm gãy và điểm vượt: s[3] « s[7]
7
4
3
8
6
5
2
1
Lật đoạn s[4..8]
7
4
3
1
2
5
6
8
Quy trình hoạt động của hàm Next
74286531 Þ 74312568
Bài 2.10. Đọc dữ liệu từ tệp vào mảng biết hai kích thước 
Đọc dữ liệu kiểu nguyên từ một tệp văn bản vào một mảng hai chiều. Tệp có cấu trúc như sau: 
- Hai số đầu tiên n, m là kích thước của mảng gồm n dòng và m cột. 
- Tiếp đến là các dữ liệu ghi liên tiếp nhau theo từng dòng của mảng. 
- Các số cách nhau ít nhất một dấu cách. 
Thí dụ: 2 3 -1 4 5 3 7 1. cho biết mảng có n = 2 dòng và m = 3 cột với dữ liệu như sau:
-1
4
5
3
7
1
Đặc tả
Ta viết hàm Doc cho giá trị true nếu đọc được dữ liệu. Chú ý rằng dữ liệu vào là đúng do đó không cần kiểm tra tính đúng đắn của chúng. Như vậy Doc sẽ cho giá trị false trong trường hợp không mở được file, do ghi sai đường dẫn hoặc file không được tạo lập từ trước.
Bài 2.11. Đọc dữ liệu từ tệp vào mảng biết một kích thước 
Đọc dữ liệu kiểu nguyên từ một tệp văn bản vào một mảng hai chiều a[n,m] cho biết một kích thước m (số cột). 
Tệp có cấu trúc như sau:
- Số đầu tiên ghi số lượng cột m của mảng tức là số phần tử trên một dòng.
- Tiếp đến là các dữ liệu ghi liên tiếp nhau theo từng dòng của mảng. 
- Các số cách nhau ít nhất một dấu cách. 
Thí dụ:	3 -1 4 5 3 7 1 	sẽ được bố trí vào mảng n = 3 dòng, m = 3 cột như sau:
-1
4
5
3
7
1
Thuật toán
1. Mở tệp.
2. Đọc giá trị đầu tiên vào biến m: số lượng cột của ma trận.
3. Mỗi lần đọc xong một dòng ta tăng con đếm dòng (n) thêm 1.
Chú ý trong lập trình
Do có thể gặp dòng trống nên ta cần sử dụng hàm SeekEof. Hàm SeekEof duyệt tiếp từ vị trí hiện thời của con trỏ tệp, bỏ qua các dấu trắng (gồm dấu cách, dấu kết thúc dòng, dấu đầu dòng, dấu nhảy TAB), nếu gặp dấu hết tệp thì cho giá trị true, ngược lại, nếu sau khi đã bỏ qua các dấu trắng mà chưa gặp dấu hết tệp thì cho giá trị false. 
Bài 2.12. Đọc dữ liệu từ tệp vào mảng đối xứng 
Đọc dữ liệu kiểu nguyên từ một tệp văn bản có tên fn vào một mảng hai chiều đối xứng. 
Tệp có cấu trúc như sau: 
- Số đầu tiên ghi số lượng cột (và đồng thời là số lượng dòng) của mảng.
- Tiếp đến là các dữ liệu ghi liên tiếp nhau theo nửa tam giác trên tính từ đường chéo chính. 
- Các số cùng dòng cách nhau ít nhất một dấu cách.
Thí dụ: 3 1 2 3 4 6 8 sẽ được bố trí vào mảng 3 ´ 3 như sau:
1
2
3
2
4
6
3
6
8
Thuật toán
1. Mở tệp.
2. Đọc giá trị đầu tiên vào biến n: số lượng cột và dòng của ma trận vuông đối xứng.
3. Với mỗi dòng i ta đọc phần tử trên đường chéo chính của dòng đó a[i, i], sau đó ta đọc các phần tử nằm ở bên phải a[i, i], tức là a[i, j] với j = i + 1..n rồi lấy đối xứng bằng phép gán a[j, i]:= a[i, j].
CHƯƠNG 3 
TỔ CHỨC DỮ LIỆU
Bài 3.1. Chuỗi hạt
Trong một tệp văn bản tên CHUOI.DAT có biểu diễn một chuỗi hạt, mỗi hạt có thể nhận một trong số các màu mã số từ 1 đến 30.
	Lập trình thực hiện các việc sau:
	a) Đọc chuỗi hạt từ tệp vào mảng nguyên dương a.
	b) Hiển thị số màu có trong chuỗi.
	c) Tìm một điểm để cắt chuỗi rồi căng thẳng ra sao cho tổng số các hạt cùng màu ở hai đầu là lớn nhất. 
	Chuỗi được thể hiện trong tệp dưới dạng hình thoi, dòng đầu tiên và dòng cuối cùng mỗi dòng có một hạt.
	Mỗi dòng còn lại có hai hạt.
	Các hạt của chuỗi được đánh số bắt đầu từ hạt trên cùng và theo chiều kim đồng hồ.
CHUOI.DAT
Trong thí dụ này, các thông báo trên màn hình sẽ là:
Số màu trong chuỗi: 5
Cắt giữa hạt thứ 7 và thứ 8, tổng số lớn nhất là 7.
 4
4 	7
1 	4
5 	8
5 	8
5 	8
8
Chuỗi hạt
Thuật toán
Khung chương trình được phác thảo như sau:
procedure run;
var i: integer;
begin
Đọc dữ liệu;
Tính và thông bỏo số màu
Xử lý để tìm điểm cắt;
Thông báo điểm cắt
end;
Để đọc chuỗi từ tệp vào mảng a ta dùng thêm một mảng phụ b có cùng cấu trúc như mảng a. Mảng b sẽ chứa các hạt ở nửa trái chuỗi, trong khi mảng a chứa các hạt ở nửa phải. Lúc đầu, do chỉ có 1 hạt tại dòng đầu tiên nên ta đọc hạt đó vào a[1]. Tại các dòng tiếp theo, mỗi dòng n = 2, ta đọc số hiệu màu của 2 hạt, hạt trái vào b[n] và hạt phải vào a[n]. Dấu hiệu kết thúc chuỗi là 1 hạt. Hạt này được đọc vào b[n]. Ta để ý rằng, theo cấu trúc của chuỗi hạt thì số hạt trong chuỗi luôn luôn là một số chẵn. 
Thí dụ dưới đây minh hoạ giai đoạn đầu của thủ tục đọc dữ liệu. Khi kết thúc giai đoạn này ta thu được n = 7 và nửa phải của chuỗi hạt (số có gạch dưới) được ghi trong a[1..(n – 1)], nửa trái được ghi trong b[2..n]. Tổng số hạt trong chuỗi khi đó sẽ là 2*(n – 1).
CHUOI.DAT
4
4 7
1 4
5 8
5 8
5 8
8
 4 a[1]
b[2] 4 7 a[2]
b[3] 1 4 a[3]
b[4] 5 8 a[4]
b[5] 5 8 a[5]
b[6] 5 8 a[6]
b[7] 8
Đọc dữ liệu của chuỗi hạt vào hai mảng a và b
a[1..6]=(4,7,4,8,8,8)
b[2..7]=(4,1,5,5,5,8)
Sau khi đọc xong ta duyệt ngược mảng b để nối nửa trái của chuỗi hạt vào sau nửa phải a.
(*--- Doc du lieu tu file CHUOI.DAT ghi vao mang a -----------------*)
procedure Doc;
var 
f: text;
i: integer;
begin
assign(f,fn); reset(f);
n := 1; read(f,a[n]);
while NOT SeekEof(f) do
begin
inc(n); read(f,b[n]);
if NOT SeekEof(f) then read(f,a[n]);
end;
{noi nua trai b (duyet nguoc) vao nua phai a} 
for i:= 0 to n-2 do a[n+i]:= b[n-i];
n := 2*(n-1); close(f);
end;
Theo thí dụ trên, sau khi nối b[2..n] vào sau a[1..(n – 1)] ta thu được
a[1..12] = (4,7,4,8,8,8,8,5,5,5,1,4)
Để đếm số màu trong chuỗi ta dùng phương pháp đánh dấu. Ta sử dụng mảng b với ý nghĩa như sau: 
b[i] = 0: màu i chưa xuất hiện trong chuỗi hạt;
b[i] = 1: màu i đã xuất hiện trong chuỗi hạt.
Lần lượt duyệt các phần tử a[i], i = 1..n trong chuỗi. Nếu màu a[i] chưa xuất hiện ta tăng trị của con đếm màu d thêm 1, inc(d) và đánh dấu màu a[i] đó trong b bằng phép gán b[a[i]] := 1.
(*---- Dem so mau trong chuoi -----------------------------------*)
function Dem: integer;
var i,d: integer;
begin
d := 0;
fillchar(b,sizeof(b),0);
for i := 1 to n do
if b[a[i]] = 0 then
begin
inc(d);
b[a[i]] := 1;
end;
Dem := d;
end;
Để tìm điểm cắt với tổng chiều dài hai đầu lớn nhất ta thực hiện như sau. Trước hết ta định nghĩa điểm đổi màu trên chuỗi hạt là hạt (chỉ số) mà màu của nó khác với màu của hạt đứng sát nó (sát phải hay sát trái, tùy theo chiều duyệt xuôi từ trái qua phải hay duyệt ngược từ phải qua trái). Ta cũng định nghĩa một đoạn trong chuỗi hạt là một dãy liên tiếp các hạt cùng màu với chiều dài tối đa. Mỗi đoạn đều có điểm đầu và điểm cuối. Vì điểm cuối của mỗi đoạn chỉ lệch 1 đơn vị so với điểm đầu của đoạn tiếp theo, cho nên với mỗi đoạn ta chỉ cần quản lí một trong hai điểm: điểm đầu hoặc điểm cuối của đoạn đó. Ta chọn điểm đầu. Kĩ thuật này được gọi là quản lí theo đoạn. 
Thí dụ, chuỗi hạt a với n = 12 hạt màu như trong thí dụ đã cho:
a[1..12] = (4,7,4,8,8,8,8,5,5,5,1,4)
mới xem tưởng như được tạo từ bảy đoạn là:
a[1..1] = (4)
a[2..2] = (7)
a[3..3] = (4)
a[4..7] = (8,8,8,8)
a[8..10] = (5,5,5)
a[11..11] = (1)
a[12..12] = (4)
Tuy nhiên, do chuỗi là một dãy hạt khép kín và các hạt được bố trí theo chiều quay của kim đồng hồ nên thực chất a chỉ gồm sáu đoạn:
a[2..2] = (7)
a[3..3] = (4)
a[4..7] = (8,8,8,8)
a[8..10] = (5,5,5)
a[11..11] = (1)
a[12..1] = (4,4)
Trong đó a[x..y] cho biết chỉ số đầu đoạn là x, cuối đoạn là y. Nếu x £ y thì các hạt trong đoạn được duyệt theo chiều kim đồng hồ từ chỉ số nhỏ đến chỉ số lớn, ngược lại, nếu x > y thì các hạt trong đoạn cũng được duyệt theo chiều kim đồng hồ từ chỉ số lớn đến chỉ số nhỏ. Các phần tử đầu mỗi đoạn được gạch chân. Có thể có những đoạn chứa cả hạt cuối cùng a[n] và hạt đầu tiên a[1] nên ta cần xét riêng trường hợp này.
Đoạn trình dưới đây xác định các điểm đầu của mỗi đoạn và ghi vào mảng b[1..sdc]. Giá trị sdc cho biết số lượng các đoạn. 
	sdc := 0;
	if a[1]a[n] then
begin
sdc := 1;
b[sdc] := 1;
end;
	for i := 1 to n-1 do
if a[i] a[i+1] then
begin
inc(sdc);
	b[sdc] := i+1;
	end;
Gọi điểm đầu của ba đoạn liên tiếp là d1, d2 và d3. Ta thấy, nếu chọn điểm cắt sát trái hạt d2 thì hiệu d3 - d1 chính là tổng số hạt đồng màu tại hai đầu của chuỗi hạt được căng ra. Từ đó ta phác thảo được sơ đồ cho thủ tục xuly để tìm điểm cắt DiemCat với chiều dài lớn nhất Lmax như sau: 
Khởi trị; 
Duyệt từ bộ ba điểm đầu của ba đoạn liên tiếp d1, d2, d3
Nếu d3-d1 > Lmax thì 
	Đặt lại Lmax := d3-d1
Đặt lại DiemCat := d2
xong nếu
Giả sử chuỗi hạt có m đoạn. Theo phương thức duyệt chuỗi hạt vòng tròn theo chiều kim đồng hồ, ta cần xét riêng hai đoạn đầu và cuối, cụ thể là:
Với đoạn 1 ta phải xét hai đoạn đứng trước và sau đoạn đó là đoạn m và đoạn 2. 
Với đoạn m ta phải xét hai đoạn đứng trước và sau đoạn đó là đoạn 
m – 1 và đoạn 1.
Ta xử lí riêng hai đoạn này ở bước khởi trị như sau:
{xu li diem cat dau}
Lmax := (b[1]+(n-b[sdc]))+(b[2]-b[1]);
DiemCat := b[1];
{xu li diem cat cuoi}
if (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]) > Lmax then
begin
Lmax := (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]);
DiemCat := b[sdc];
	end;
Phương án cuối cùng của thủ tục xuly sẽ như sau:
procedure xuly;
var i,sdc: integer; {sdc: so diem cat}
begin
	sdc:=0;
	if a[1]a[n] then
	begin
	sdc := 1;
	b[sdc]:= 1;
	end;
	for i:=1 to n-1 do
	if a[i] a[i+1] then
	begin
inc(sdc);
	b[sdc] := i+1;
	end;
	if sdc=0 then
	begin
	DiemCat:=0;
	Lmax:=n;
	exit;
	end;
	{xu li diem cat dau}
	Lmax := (b[1]+(n-b[sdc]))+(b[2]-b[1]);
	DiemCat := b[1];
	{xu li diem cat cuoi}
 	if (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]) > Lmax then
	begin
Lmax := (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]);
DiemCat := b[sdc];
	end;
	{xu li cac diem cat giua}
	for i:= 2 to sdc-1 do
 	if b[i+1]-b[i-1] > Lmax then
 	begin
 Lmax := b[i+1]-b[i-1];
 DiemCat := b[i];
end;
end;
Dữ liệu kiểm thử CHUOI.DAT
Kết quả dự kiến
4
4 7
1 4
5 8
5 8
5 8
8
Cắt giữa hạt: 7 và 8
Chiều dài max: 7
Bài 3.2. Sắp mảng rồi ghi tệp 
Sinh ngẫu nhiên n phần tử cho mảng nguyên a. Sắp a theo trật tự tăng dần rồi ghi vào một tệp văn bản có tên tuỳ đặt. 
Gợi ý
Hai phương pháp sắp xếp mảng thường được sử dụng đó là MinSort và QuickSort. Theo phương pháp MinSort với mỗi i ta tìm phần tử nhỏ nhất a[j] trong đoạn a[i..n] sau đó ta đổi chỗ phần tử này với phần tử a[i]. Như vậy mảng được chia thành hai đoạn: đoạn trái, a[1..i] được sắp tăng, còn đoạn phải a[i + 1..n] chưa xử lí. Mỗi bước ta thu hẹp đoạn phải cho đến khi còn một phần tử là xong.
Theo phương pháp QuickSort ta lấy một phần tử x nằm giữa đoạn mảng cần sắp làm mẫu rồi chia mảng thành hai đoạn. Đoạn trái a[1..i] bao gồm các giá trị không lớn hơn x và đoạn phải a[j..n] bao gồm các giá trị không nhỏ thua x. Tiếp đến ta lặp lại thủ tục này với hai đoạn thu được nếu chúng chứa nhiều hơn một phần tử. 
Bài 3.3. Sắp theo chỉ dẫn
Cho xâu S gồm N kí tự tạo từ các chữ cái 'a'..'z'. ta gọi S là xâu mẫu. Từ xâu mẫu S này người ta tạo ra N xâu thứ cấp bằng cách dịch xâu S qua trái i vị trí theo dạng vòng tròn, tức là i kí tự đầu xâu lần lượt được chuyển về cuối xâu, i = 0, 1,, N - 1. Như vậy xâu thứ cấp với i = 0 sẽ trùng với xâu mẫu S. Giả sử ta đã sắp tăng N xâu thu được theo trật tự từ điển. Hãy tìm xâu thứ k trong dãy.
Tên chương trình: abc.pas.
Dữ liệu vào: tệp văn bản abc.inp có cấu trúc như sau:
- Dòng thứ nhất chứa hai số tự nhiên N và k cách nhau qua dấu cách,
6 £ N £ 500, 1 £ k £ N. N cho biết chiều dài xâu S, k cho biết vị trí của xâu thứ cấp trong dãy được sắp tăng theo thứ tự từ điển. 
- Dòng thứ hai: xâu mẫu S.
Dữ liệu ra: tệp văn bản abc.out gồm một dòng chứa xâu thứ k trong dãy được sắp.
Thí dụ:
abc.inp
abc.out
6 3
dabdec
cdabde
Đặc tả:
Ta gọi xâu s ban đầu là xâu mẫu, các xâu được sinh ra bởi phép quay là xâu thứ cấp. Để ý rằng các xâu mẫu cũng là một xâu thứ cấp ứng với phép quay 0 vị trí. Ta có thể nhận được xâu thứ cấp thứ i bằng cách duyệt xâu mẫu theo vòng tròn kể từ vị trí thứ i về cuối, đến vị trí thứ n. Sau đó duyệt tiếp tục từ vị trí thứ 1 đến vị trí thứ i - 1. Ta kí hiệu xâu thứ cấp thứ i là [i]. Thí dụ, nếu xâu mẫu s = 'dabdec' thì xâu thứ cấp thứ 2 sẽ là [2] = 'abdecd'. Để tìm xâu thứ k trong dãy được sắp, trước hết ta cần sắp tăng các xâu đó theo trật tự từ điển sau đó lấy xâu thứ k trong dãy được sắp làm kết quả. Để sắp tăng được các xâu này mà không phải sinh ra các xâu mới ta dùng một mảng phụ id gọi là mảng chỉ dẫn. Trước khi sắp ta gán id[i]:= i. Sau khi sắp thì id[i] sẽ cho biết tại vị trí thứ i trong dãy được sắp là xâu thứ cấp nào. Trong thí dụ trên, id[3] = 6 là xâu thứ cấp [6]. Giá trị 3 cho biết cần tìm xâu thứ k = 3 trong dãy sắp tăng các xâu thứ cấp. Giá trị 6 cho biết xâu cần tìm là xâu thứ 6 trong dãy các xâu thứ cấp được sinh ra lúc đầu, tức là lúc chưa sắp. 
Xâu thứ cấp
Sắp tăng
id[i] = ?
j
[1] = S
dabdec
[2]
2
k
[2]
abdecd
[3]
3
l
[3]
bdecda
[6]
6
m
[4]
decdab
[1]
1
n
[5]
ecdabd
[4]
4
o
[6]
cdabde
[5]
5
Sắp chỉ dẫn các xâu thứ cấp
Thuật toán QuickSort sắp nhanh các xâu thứ cấp do Hoare đề xuất có độ phức tạp N.log2N được trình bày như sau:
Init: for i:=1 to n do id[i]:=i;
procedure idquicksort(d,c: integer);
var i, j, m, y: integer;
begin
i:=d; 
j:=c; 
m:=id[(i+j) div 2]; {phan tu giua}
while i <= j do
begin
	while Sanh(id[i],m)<0 do inc(i); {doan trai}
	while Sanh(m,id[j])<0 do dec(j); {doan phai}
	{doi cho neu can}
	if (i <= j) then 
	begin
	y:= id[i];
	id[i]:= id[j];
	id[j]:= y;
	inc(i); dec(j);
	end;
end;
if d < j then idquicksort(d,j);
if i < c then idquicksort(i,c);
end;
Hàm Sanh(i,j) so sánh hai xâu thứ cấp [i] và [j] theo thứ tự từ điển và cho giá trị -1 nếu xâu thứ cấp [i] nhỏ hơn xâu thứ cấp [j], cho giá trị 1 nếu xâu thứ cấp [i] lớn hơn xâu thứ cấp [j] và 0 nếu hai xâu này giống nhau. Để so sánh hai xâu theo trật tự từ điển ta lần lượt duyệt từng cặp kí tự của mỗi xâu. Nếu hai xâu giống nhau tại mọi vị trí thì ta gán trị 0 cho hàm Sanh. Ngược lại, nếu tìm được vị trí khác nhau đầu tiên thì ta so sánh hai kí tự s[i] và s[j] tại vị trí đó và gán cho hàm Sanh giá trị -1 nếu s[i] s[j] thì gán giá trị 1 cho hàm Sanh. 
Ta chỉ cần lưu ý là việc duyệt xâu phải thực hiện trên vòng tròn theo chiều quay của kim đồng hồ.
function Sanh(i,j: integer): integer;
var k: integer;
begin
for k:=1 to n do
begin
if s[i] s[j] then
begin
if s[i] < s[j] then Sanh:=-1
else Sanh:=1;
exit;
end;
if i=n then i:=1 else inc(i);
if j=n then j:=1 else inc(j);
end;
Sanh:=0;
end;
Hoare cũng cung cấp thêm thuật toán tìm phần tử thứ k trong dãy được sắp với độ phức tạp 2N. Ta vận dụng thuật toán này cho bài toán abc. Bản chất thuật toán này là như sau. Ta cũng sắp tăng các xâu thứ cấp theo thuật toán QuickSort nhưng không sắp hết mà chỉ quan tâm đến đoạn dữ liệu trong mảng có chứa phần tử thứ k. Lưu ý rằng sau một lần chia dữ liệu của đoạn id[d..c] ta thu được ba đoạn: đoạn id[d..j], id[j+1..i-1] và id[i..c], trong đó đoạn giữa là id[j+1..i-1] đã được sắp. Nếu k rơi vào đoạn thứ nhất là id[d..j] hoặc đoạn thứ ba là id[i..c] thì ta chỉ cần sắp tiếp đoạn đó. Hàm Find(k) cho ra vị trí gốc của xâu thứ cấp sẽ đứng thứ k trong dãy đã sắp. Trong thí dụ trên Find(3)=6. 
(*---	Tim phan tu thu k--------------------------------------*)
function Find(k: integer):integer;
var d, c, i, j, m, y: integer;
begin
d:=1 ; 
c:=n;
while d <= c do
begin
	i:=d; 
	j:=c; 
	m:=id[(i+j) div 2]; {phan tu giua}
	while i <= j do
	begin
	while Sanh(id[i],m)<0 do inc(i); {doan trai}
	while Sanh(m,id[j])<0 do dec(j); {doan phai}
	{doi cho neu can}
	if (i <= j) then 
	begin
	y:= id[i];
	id[i]:= id[j];
	id[j]:= y;
	inc(i); dec(j);
	end;
end;
	if j < k then d:=i;
	if k < i then c:=j;
end;
find:=id[k];
end;
Bài 3.4. Xâu mẫu
Một tệp văn bản f có tên STRINGS.INP chứa các xâu kí tự, mỗi dòng ghi một xâu có chiều dài tối đa 250 kí tự. Xâu đầu tiên được gọi là xâu mẫu s. 	
Yêu cầu: Đọc xâu mẫu s từ tệp f, ghi vào tệp văn bản g có tên STRINGS.OUT. Sau đó đọc từng xâu x còn lại của f, với mỗi xâu x cần ghi vào g các thông tin sau:
- Nội dung xâu x;
- Hai số v và d cách nhau qua dấu cách, trong đó v là vị trí xuất hiện và d là chiều dài lớn nhất của khúc đầu của x trong xâu mẫu s. 
- Nếu vô nghiệm thì ghi -1 0.
Thí dụ:
STRINGS.INP
STRINGS.OUT
cabxabcdab
abcd
cdaeh
cabxabcdab
abcd
5 4
cdaeh
7 3
Thuật toán
Với mỗi xâu kí tự w ta kí hiệu w[i..j], i £ j, và gọi là đoạn, là xâu gồm dãy kí tự liên tiếp từ w[i] đến w[j] trong xâu w. Thí dụ, nếu w = 'cabxabcdab' thì w[5..8] = 'abcd'. Gọi s là xâu mẫu, x là xâu cần khảo sát. Ta phải tìm vị trí v và chiều dài lớn nhất d để x[1..d] = s[v..(v + d – 1)]. Ta vận dụng kĩ thuật tổ chức hậu tố như sau. 
Hậu tố của một xâu là đoạn cuối của xâu đó. Như vậy một xâu có chiều dài n sẽ có n hậu tố. Thí dụ, với xâu mẫu s[1..10] = 'cabxabcdab' ta có 10 hậu tố sau đây:
s[1..10] = 'cabxabcdab'
s[2..10] = 'abxabcdab'
s[3..10] = 'bxabcdab'
s[4..10] = 'xabcdab'
s[5..10] = 'abcdab'
s[6..10] = 'bcdab'
s[7..10] = 'cdab'
s[8..10] = 'dab'
s[9..10] = 'ab'
s[10..10] = 'b'
Như vậy, hậu tố sau sẽ nhận được từ hậu tố sát trước nó bằng cách bỏ đi kí tự đầu tiên.
Đầu tiên ta sắp tăng các hậu tố của xâu mẫu s theo trật tự từ điển. Sử dụng một mảng chỉ dẫn id, trong đó id[i] trỏ đến vị trí đầu tiên của hậu tố trong xâu mẫu. Cụ thể là, nếu id[i] = k thì hậu tố tương ứng sẽ là s[k..n]. Sau khi sắp tăng các hậu tố của xâu mẫu s[1..10] = 'cabxabcdab' ta thu được:
i
id[i]
Hậu tố
Xâu
1
9
S[9..10]
ab
2
5
S[5..10]
abcdab
3
2
S[2..10]
abxabcdab
4
10
S[10..10]
b
5
6
S[6..10]
bcdab
6
3
S[3..10]
bxabcdab
7
1
S[1..10]
cabxabcdab
8
7
S[7..10]
cdab
 9
 8
S[8..10]
dab
10
4
S[4..10]
xabcdab
Sắp tăng theo chỉ dẫn các hậu tố của xâu
s[1..10] = 'cabxabcdab'
Sau đó, so sánh xâu x với các hậu tố s[i..j] để tìm khúc đầu chung dài nhất giữa chúng. Thí dụ, với x[1..4]='abcd' thì khúc đầu chung dài nhất tìm được với hậu tố s[5..10] do id[2] trỏ tới. Vị trí v tìm được sẽ là 5 và chiều dài lớn nhất d sẽ là 4. 
Phần chính của chương trình sẽ như sau:
procedure Run;
begin
...
n:= length(s);
for i:=1 to n do id[i]:=i;
IdQuikSort(1,n);
while not seekeof(f) do
begin
	readln(f,x); 
	writeln(g,x);
	Tim; {xac dinh v và d}
	writeln(g,v,BL,d);
end;
end;
Với mỗi xâu x, nếu phần tử đầu tiên của x là x[1] không trùng với phần tử đầu tiên của hậu tố h thì chiều dài của khúc đầu chung của chúng sẽ bằng 0. Nhờ nhận xét này và do dãy các hậu tố đã được sắp tăng nên với mỗi xâu x, trước hết ta gọi hàm Binsearch để thực hiện tìm kiếm nhị phân phần tử x[1] trong dãy gồm các phần tử đầu tiên của các hậu tố, sau đó ta thực hiện việc duyệt tìm.
procedure Tim;
var i,Len: integer;
begin
v:=BinSearch; d := 0;
if v=0 then exit;
Maxlen:=0;
for i:=v to n do
begin
if s[id[i]]x[1] then exit;
Len:=Eqsx(id[i]);
if Len > d then
	begin
	d:=Len;
	v:=id[i];
	end;
end;
end;
Hàm BinSearch cho ra chỉ dẫn tới hậu tố h đầu tiên thoả điều kiện h[1]= x[1].
(*-- Tim xuat hien cua x[1]trong day da sap cac hau to---------*)
function BinSearch:integer;
var 
	d,c,m: integer;
begin
d:=1;
c:=n;
repeat
m:=(d+c) div 2;
if x[1]>s[id[m]] then d:=m+1 
else c:=m;
until d=c;
if x[1]s[id[d]] then Binsearch := -1 
else BinSearch := d;
end;
Hàm Eqsx(i) trả về chiều dài lớn nhất của khúc đầu chung giữa hậu tố s[i..n] và xâu x.
(*-----	Khuc dau dai nhat giua hau to s[i..n] va x------------------*)
function Eqsx(i:integer): integer;
var 
	k,m:integer;
begin
m:=min(length(x),n-i+1);
for k:=1 to m do
	if s[i+k-1]x[k] then
	begin
	Eqsx:=k-1; 
	exit;
	end;
Eqsx:=m;
end;
Dữ liệu kiểm thử
STRINGS.INP
Kết quả dự kiến
STRINGS.OUT
cabxabcdab
abcd
cdaeh
cabxabcdab
abcd
5 4
cdaeh
7 3
CHƯƠNG 4
PHƯƠNG PHÁP THAM LAM
Phương pháp tham lam gợi ý chúng ta tìm một trật tự hợp lí để duyệt dữ liệu nhằm đạt được mục tiêu một cách chắc chắn và nhanh chóng. Thông thường, dữ liệu được duyệt theo một trong hai trật tự là tăng hoặc giảm dần theo một chỉ tiêu nào đó. Một số bài toán đòi hỏi những dạng thức cải biên của hai dạng nói trên.
Bài 4.1. Băng nhạc
Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết thời lượng phát của bài đó. Băng sẽ được lắp vào một máy phát nhạc đặt trong một siêu thị. Khách hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua i – 1 bài ghi trước bài đó. Thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như nhau. Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất.
Dữ liệu vào được ghi trong tệp văn bản tên BANGNHAC.INP. 
- Dòng đầu tiên là số tự nhiên N cho biết số lượng bài hát.
- Tiếp đến là N số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài. Mỗi đơn vị dữ liệu cách nhau qua dấu