Cấu trúc dữ liệu và giải thuật – Lê Minh Hoàng

VÀ GIẢI THUẬT ĐỆ QUY …………………………………………………………………………….. 50
3.1. KHÁI NIỆM VỀ ĐỆ QUY…………………………………………………………………………………………………………50
3.2. GIẢI THUẬT ĐỆ QUY……………………………………………………………………………………………………………..50
3.3. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY …………………………………………………………………………………………….51
3.4. HIỆU LỰC CỦA ĐỆ QUY ………………………………………………………………………………………………………..55
§4. CẤU TRÚC DỮ LIỆU BIỂU DIỄN DANH SÁCH………………………………………………………….. 58
4.1. KHÁI NIỆM DANH SÁCH ……………………………………………………………………………………………………….58
4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH …………………………………………………………………………58
§5. NGĂN XẾP VÀ HÀNG ĐỢI………………………………………………………………………………………….. 64
5.1. NGĂN XẾP (STACK)……………………………………………………………………………………………………………….64
5.2. HÀNG ĐỢI (QUEUE)……………………………………………………………………………………………………………….66
§6. CÂY (TREE)…………………………………………………………………………………………………………………. 70
6.1. ĐỊNH NGHĨA…………………………………………………………………………………………………………………………..70
6.2. CÂY NHỊ PHÂN (BINARY TREE) ……………………………………………………………………………………………71
6.3. BIỂU DIỄN CÂY NHỊ PHÂN ……………………………………………………………………………………………………73
6.4. PHÉP DUYỆT CÂY NHỊ PHÂN………………………………………………………………………………………………..74
6.5. CÂY K_PHÂN …………………………………………………………………………………………………………………………76
6.6. CÂY TỔNG QUÁT…………………………………………………………………………………………………………………..77
§7. KÝ PHÁP TIỀN TỐ, TRUNG TỐ VÀ HẬU TỐ …………………………………………………………….. 79
7.1. BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN ……………………………………………………………………………..79
7.2. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC…………………………………………………………………………79
7.3. CÁCH TÍNH GIÁ TRỊ BIỂU THỨC…………………………………………………………………………………………..79
7.4. CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ………………………………………………………….83
7.5. XÂY DỰNG CÂY NHỊ PHÂN BIỂU DIỄN BIỂU THỨC…………………………………………………………….86
§8. SẮP XẾP (SORTING) …………………………………………………………………………………………………… 87
8.1. BÀI TOÁN SẮP XẾP………………………………………………………………………………………………………………..87
8.2. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTIONSORT)………………………………………………………89
8.3. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLESORT)…………………………………………………………………90
8.4. THUẬT TOÁN SẮP XẾP KIỂU CHÈN………………………………………………………………………………………90
8.5. SHELLSORT……………………………………………………………………………………………………………………………92
8.6. THUẬT TOÁN SẮP XẾP KIỂU PHÂN ĐOẠN (QUICKSORT)……………………………………………………93
8.7. THUẬT TOÁN SẮP XẾP KIỂU VUN ĐỐNG (HEAPSORT) ……………………………………………………….99
8.8. SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI (DISTRIBUTION COUNTING)………………………………..102
8.9. TÍNH ỔN ĐỊNH CỦA THUẬT TOÁN SẮP XẾP (STABILITY) …………………………………………………103
8.10. THUẬT TOÁN SẮP XẾP BẰNG CƠ SỐ (RADIX SORT)………………………………………………………..104
8.11. THUẬT TOÁN SẮP XẾP TRỘN (MERGESORT)……………………………………………………………………109
8.12. CÀI ĐẶT ……………………………………………………………………………………………………………………………..112
8.13. ĐÁNH GIÁ, NHẬN XÉT……………………………………………………………………………………………………….119
§9. TÌM KIẾM (SEARCHING) …………………………………………………………………………………………. 124
9.1. BÀI TOÁN TÌM KIẾM……………………………………………………………………………………………………………124
9.2. TÌM KIẾM TUẦN TỰ (SEQUENTIAL SEARCH) …………………………………………………………………….124
9.3. TÌM KIẾM NHỊ PHÂN (BINARY SEARCH)…………………………………………………………………………….124
9.4. CÂY NHỊ PHÂN TÌM KIẾM (BINARY SEARCH TREE – BST)…………………………………………………125

Bạn đang đọc: Cấu trúc dữ liệu và giải thuật – Lê Minh Hoàng

1999-2004
Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng
Dữ liệu vào (Input): nhập từ file văn bản BSTR.INP chứa số nguyên dương n ≤ 30
Kết quả ra (Output): ghi ra file văn bản BSTR.OUT các dãy nhị phân độ dài n.
BSTR.INP
3
BSTR.OUT
000
001
010
011
100
101
110
111
P_1_02_1.PAS * Thuật toán sinh liệt kê các dãy nhị phân độ dài n
program Binary_Strings;
const
InputFile = ‘BSTR.INP’;
OutputFile = ‘BSTR.OUT’;
max = 30;
var
x: array[1..max] of Integer;
n, i: Integer;
f: Text;
begin
Assign(f, InputFile); Reset(f);
ReadLn(f, n);
Close(f);
Assign(f, OutputFile); Rewrite(f);
FillChar(x, SizeOf(x), 0); {Cấu hình ban đầu x=00..0}
repeat {Thuật toán sinh}
for i := 1 to n do Write(f, x[i]); {In ra cấu hình hiện tại}
WriteLn(f);
i := n; {x[i] là phần tử cuối dãy, lùi dần i cho tới khi gặp số 0 hoặc khi i = 0 thì dừng}
while (i > 0) and (x[i] = 1) do Dec(i);
if i > 0 then {Chưa gặp phải cấu hình 11…1}
begin
x[i] := 1; {Thay x[i] bằng số 1}
FillChar(x[i + 1], (n – i) * SizeOf(x[1]), 0); {Đặt x[i+1] = x[i+2] = … = x[n] := 0}
end;
until i = 0; {Đã hết cấu hình}
Close(f);
end.
2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ
Ta sẽ lập chương trình liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điền
Ví dụ: với n = 5, k = 3, ta phải liệt kê đủ 10 tập con:
1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5}
6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10.{3, 4, 5}
Như vậy tập con đầu tiên (cấu hình khởi tạo) là {1, 2, …, k}.
Cấu hình kết thúc là {n – k + 1, n – k + 2, …, n}.
Nhận xét: Ta sẽ in ra tập con bằng cách in ra lần lượt các phần tử của nó theo thứ tự tăng dần.
Biểu diễn mỗi tập con là một dãy x[1..k] trong đó x[1] < x[2] < … < x[k]. Ta nhận thấy giới

kê 21
Lê Minh Hoàng
QUEENS.INP
5
QUEENS.OUT
(1, 1); (2, 3); (3, 5); (4, 2); (5, 4);
(1, 1); (2, 4); (3, 2); (4, 5); (5, 3);
(1, 2); (2, 4); (3, 1); (4, 3); (5, 5);
(1, 2); (2, 5); (3, 3); (4, 1); (5, 4);
(1, 3); (2, 1); (3, 4); (4, 2); (5, 5);
(1, 3); (2, 5); (3, 2); (4, 4); (5, 1);
(1, 4); (2, 1); (3, 3); (4, 5); (5, 2);
(1, 4); (2, 2); (3, 5); (4, 3); (5, 1);
(1, 5); (2, 2); (3, 4); (4, 1); (5, 3);
(1, 5); (2, 3); (3, 1); (4, 4); (5, 2);
P_1_03_5.PAS * Thuật toán quay lui giải bài toán xếp hậu
program n_Queens;
const
InputFile = ‘QUEENS.INP’;
OutputFile = ‘QUEENS.OUT’;
max = 12;
var
n: Integer;
x: array[1..max] of Integer;
a: array[1..max] of Boolean;
b: array[2..2 * max] of Boolean;
c: array[1 – max..max – 1] of Boolean;
f: Text;
procedure Init;
begin
Assign(f, InputFile); Reset(f);
ReadLn(f, n);
Close(f);
FillChar(a, SizeOf(a), True); {Mọi cột đều tự do}
FillChar(b, SizeOf(b), True); {Mọi đường chéo Đông Bắc – Tây Nam đều tự do}
FillChar(c, SizeOf(c), True); {Mọi đường chéo Đông Nam – Tây Bắc đều tự do}
end;
procedure PrintResult;
var
i: Integer;
begin
for i := 1 to n do Write(f, ‘(‘, i, ‘, ‘, x[i], ‘); ‘);
WriteLn(f);
end;
procedure Try(i: Integer); {Thử các cách đặt quân hậu thứ i vào hàng i}
var
j: Integer;
begin
for j := 1 to n do
if a[j] and b[i + j] and c[i – j] then {Chỉ xét những cột j mà ô (i, j) chưa bị khống chế}
begin
x[i] := j; {Thử đặt quân hậu i vào cột j}
if i = n then PrintResult
else
begin
a[j] := False; b[i + j] := False; c[i – j] := False; {Đánh dấu}
Try(i + 1); {Tìm các cách đặt quân hậu thứ i + 1}
a[j] := True; b[i + j] := True; c[i – j] := True; {Bỏ đánh dấu}
end;
end;
end;
begin