CC THUT TON C BN V X Lí MNG TRONG
PASCAL.
Sơ lợc về các chủ đề
Sau đây là sơ lợc về các chủ đề sẽ đợc đề cập trong phần này của chơng trình:
+ Phần cơ sở: là các công cụ và phơng pháp đợc dùng xuyên suốt cho tất cả các chơng sau của phần
này. Nó gồm một phần bàn luận ngắn về Pascal, theo sau là giới thiệu về các cấu trúc dữ liệu cơ bản
gồm mảng, xâu liên kết, ngăn xếp, hàng đợi và cây. Chúng ta sẽ bàn luận về công dụng thực tiễn đệ
quy và bắt đầu hớng tới việc phân tích và tiếp cận thực toán.
+ Sắp xếp: Các phơng pháp sắp xếp sẽ đợc phát triển, đợc mô tả, đợc so sánh với nhau. Các thuật
toán cho nhiều vấn đề có liên quan sẽ đợc xem xét gồm có hàng đợi u tiên, phép chọn và phép trộn.
Một vài nền tảng trong số này đợc dùng nh là nền tảng cho các thuật toán khác tiếp sau trong phần
này.
+ Xử lý chuỗi: gồm một loạt các phơng pháp để phân tích câu. Các ky thuật nén tập và mật mã
cũng sẽ đợc khảo sát. Cũng vậy, một giới thiệu về các chủ đề nâng cao cùng đợc cung cấp qua việc
xem xét một vài bài toán cơ bản quan trọng trong phạm vi của chúng.
+ Hình học: là một sự tập hợp có chọn lọc các phơng pháp để giải quyết các bài toán liên quan đến
điểm và đờng ( và các đối tợng hình học đơn giản khác ). Chúng ta sẽ xem xét các thuật toán để tìm
bao lồi của một tập điểm, phần giao của các đối tợng, để giải bài toán điểm gần nhất, tìm kiếm
nhiều chiều ...
+ Đồ thị: Một chiến lợc tổng quát để tìm kiếm trên các đồ thị sẽ đợc phát triển và đợc áp dụng cho
các bài toán liên thông cơ bản, gồm có đờng đi ngắn nhất, cây liên thông tối thiểu, mạng và so
khớp. Một sự xem xét thống nhất đối với các thuật toán này chứng tỏ rằng tất cả đều dựa vào một
thủ tục và thủ tục này phụ thuộc vào một cấu trúc dữ liệu cơ bản đã phát triển trớc đó.
+ Các thuật toán toán học: gồm các phơng pháp cơ bản từ số học và các số nguyên, đa thức, và ma
trận cũng nh các thuật toán để giải quyết cac vấn đề toán học mà nó phát sinh trong nhiều ngữ
cảnh : việc tạo số ngẫu nhiên, lỡi giải của các chơng trình đồng thời, xấp xỉ dữ liệu, và lấy tích phân.
Sự nhấn mạnh thiên về các khía cạnh thuật toán của phơng pháp, chứ không phải trên nền tảng của
toán học
+ Các chủ đề cao cấp: đợc thảo luận nhằm mục đích liên hệ các chủ đề trong tập sách này với nhiều
lĩnh vực nghiên cứu cao cấp khác. Phần cứng chuyên dụng, quy hoạch động, quy hoạch tuyến tính,
tìm kiếm- vét cạn ...

End;
Var
A : Array[1..n] of Item;
Khoá của phần tử có thể là chữ hoặc số.
Yêu cầu giải thích là dùng ít vùng nhớ và thời gian thực hiện nhanh.
b) Phơng pháp đếm (Counting sort)
* Giải thích:
Nội dung của phơng pháp này là đếm các phần tử có khoá nhỏ hơn hay bằng khoá của các phần tử
A[i]. Nếu có j phần tử có khoá nhỏ hơn khoá của phần tử A[i] thì phần tử A[i] sẽ có vị trí theo thứ tự
(j+1) trong dãy đã có thứ tự.
Trong giải thuật, ta dùng mảng Count[i] ( i = 1, 2, .. n ) với Count[i] cho biết số phần tử có khoá
nhỏ hơn khoá của phần tử A[i]. Nh vậy Count[i+1] là vị trí của phần tử A[i] trong dãy đã có thứ tự.
* Ví dụ:
Sắp xếp dãy 2 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
Count: 2 0 4 1 6 5 7 3
Nh vậy phần tử có khoá 9 ở vị trí 8 vì Count[9]=7.
* Thể hiện bằng Pascal:
Procedure Count_Sort;
Var
Count : Array[1..n] of Integer;
A : Array[1..n] of Item;
i,j : Integer;
Begin
For i := 1 to n do Count[i] := 0;
For i := n downto 2 do
For j := i-1 downto 1 do
If A[i].Key < A[j].Key Then
Count[j] := Count[j] + 1
Else Count[i] := Count[i] + 1;

j := j - 1;
While x.Key < A[j].Key do
Begin
A[j+1] := A[j];
j := j - 1;
End;
A[j+1] := x;
End;
End;
d) Phơng pháp chọn (Selection Sort)
* Giải thích:
Nội dung của phơng pháp này là ở bớc thứ i (i = 1, 2, 3, ..., n-1 ) ta lựa chọn phần tử nhỏ nhất trong
dãy A[i]..A[n] rồi đổi chổ phần tử này với phần tử A[i]. Cuối cùng ta sẽ có dãy A[1]..A[n] có thứ tự.
* Ví dụ:
Ta phải sắp xếp dãy số :
39 50 7 37 89 13 1 62
i=1 39 50 7 37 89 13 1 62
i=2 1 50 7 37 89 13 39 62
i=3 1 7 50 37 89 13 39 62
i=4 1 7 13 37 89 50 39 62
i=5 1 7 13 37 89 50 39 62
i=6 1 7 13 37 50 50 39 62
i=7 1 7 13 37 39 50 89 62
1 7 13 37 39 50 89 62
* Thể hiện bằng Pascal:
Procedure Selection_Sort;
Var
x : Item;
i,j ,k : Integer;
min : Integer;

trên khi đun nớc. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ đợc đặ vào đúng một vị trí. Vì vậy sắp xếp
nổi bột thao tác nh một kiểu sắp xếp chọn, mặc dù nó không làm nhiều việc hơn để đa từng phần tử
vào đúng vị trí.
* Ví dụ:
Ta phải sắp xếp dãy số:
39 50 7 37 89 13 1 62
Bớc 0 1 2 3 4 5 6 7
50 1 1 1 1 13 1 62
39 39 7 7 7 7 7 7
7 50 39 13 13 13 13 13
37 7 50 39 37 37 37 37
89 37 13 50 39 39 39 39
13 89 37 37 50 50 50 50
1 13 89 62 62 62 62 62
62 62 62 89 89 89 89 89
* Thể hiện bằng Pascal:
Procedure Bubble_Sort;
Var
x : Item;
i,j : Integer;
Begin
For i := 2 to n do
For j := n downto i do
If A[j-1].Key > A[j].Key Then
Begin
x := A[j-1];
A[j-1] := A[j];
A[j-1] := x;
End;
End;

* Ví dụ:
Sắp xếp dãy số:
39 50 7 37 89 13 1 62
d = 2 3 3 4 4
c = 8 8 7 7 4
39 1 1 1 1
50 39 39 7 7
7 50 7 39 13
37 7 37 13 37
89 37 50 37 39
13 89 13 50 50
1 13 62 62 62
62 62 89 89 89
* Thể hiện bằng Pascal:
Procedure Shake_Sort;
Var
x : Item;
i,k,d,c : Integer;
Begin
d := 2;
c := n;
k := n;
Repeat
For i := c downto d do
If A[i-1].Key > A[i].Key Then
Begin
x := A[i-1];
A[i-1] := A[i];
A[i-1] := x;
k := i;

Bớc 2: 2-Sort
39 13 1 37 89 50 7 62
1 13 7 37 39 50 89 62
Bớc 3: 1-Sort
1 13 7 37 39 50 89 62
1 7 13 37 39 50 89 62
* Thể hiện bằng Pascal:
Chú ý:
- Ta dùng dãy phụ chứa dộ tăng h[i], ..., h[t] để điều khiển quá trình sắp xếp thứ tự với h[t]=1. Việc
chộn các độ tăng thích hợp sẽ làm giảm thời gian sắp thứ tự.
- Dặt h1 = h[1] ta phải khai báo dãy a nh sau:
A : Array[1..n] of Item;
các phần tử A[i] (i<=0) là các lính canh. Sau đây ta chọn:
h[1] = 9, h[2] = 5, h[3] = 3, h[4] = 1
Procedure Shell_Sort;
Const
t = 4;
Var