Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 1)
MỤC LỤC
MỤC LỤC............................................................................................................. 1
CHƢƠNG 1: MỞ ĐẦU........................................................................................ 4
1.1. Giải thuật..................................................................................................... 4
1.1.1 Khái niệm giải thuật.............................................................................. 4
1.1.2. Các đặc trưng của giải thuật................................................................. 4
1.2. Cấu trúc dữ liệu và các vấn đề liên quan .................................................... 5
1.2.1. Cấu trúc dữ liệu và giải thuật............................................................... 5
1.3. Ngôn ngữ diễn đạt giải thuật....................................................................... 6
1.3.1. Đặt vấn đề ............................................................................................ 6
1.3.3. Ký tự và biểu thức................................................................................ 7
1.3.4. Các câu lệnh ......................................................................................... 7
2.1. Từ bài toán đến chương trình.................................................................... 11
2.2. Phân tích giải thuật.................................................................................... 21
2.2.1. Đặt vấn đề .......................................................................................... 24
2.3. Bài tập ....................................................................................................... 26
3.1. Khái niệm về đệ quy ................................................................................. 35
3.3. Thiết kế giải thuật đệ quy.......................................................................... 37
3.3.2. Bài toán Tháp Hà Nội ........................................................................ 38
3.4. Hiệu lực của đệ quy................................................................................... 44
3.5. Đệ quy và quy nạp toán học...................................................................... 45
3.6. Bài tập ....................................................................................................... 48
4.1. Các khái niệm............................................................................................ 50
4.2. Cấu trúc lưu trữ của mảng......................................................................... 51
4.4. Ngăn xếp (Stack)....................................................................................... 55
4.4.1. Định nghĩa.......................................................................................... 55
4.4.2. Lưu trữ Stack kế tiếp.......................................................................... 55
4.4.4. Ứng dụng của Stack ........................................................................... 58
4.5. Hàng đợi (Queue)...................................................................................... 66
4.5.1. Định nghĩa.......................................................................................... 66
4.5.2. Lưu trữ Queue kế tiếp ........................................................................ 66
4.6. Bài tập ....................................................................................................... 69
5.1. Danh sách nối đơn..................................................................................... 73
5.1.1. Nguyên tắc ......................................................................................... 73
5.1.2. Một số giải thuật................................................................................. 74
5.2. Danh sách nối vòng................................................................................... 76
5.2.1. Nguyên tắc ......................................................................................... 76
5.2.2. Một số giải thuật................................................................................. 77
5.3. Danh sách nối kép ..................................................................................... 78
5.3.1. Nguyên tắc ......................................................................................... 78
5.3.2. Một số giải thuật................................................................................. 79
5.4. Ví dụ áp dụng............................................................................................ 77
5.4.1. Biểu diễn đa thức ............................................................................... 81
5.4.2. Giải thuật cộng hai đa thức ................................................................ 82
5.4.3. Biểu diễn tập hợp ............................................................................... 84
5.4.3. Các phép toán..................................................................................... 84
5.5. Ngăn xếp và Hàng đợi móc nối................................................................. 82
5.6. Cấu trúc đa danh sách ............................................................................... 91
5.6.1. Biểu diễn ma trận thưa ....................................................................... 91
5.6.2. Một số giải thuật................................................................................. 92
5.7. Danh sách tổng quát.................................................................................. 96
5.7.1. Định nghĩa.......................................................................................... 96
CHƢƠNG 6 : CÂY .......................................................................................... 103
6.1. Định nghĩa và khái niệm ......................................................................... 103
6.2. Cây nhị phân ........................................................................................... 106
6.2.1. Định nghĩa và tính chất .................................................................... 106
6.2.2. Biểu diễn cây nhị phân..................................................................... 108
6.2.3. Phép duyệt cây nhị phân .................................................................. 110
6.3. Cây nhị phân nối vòng ............................................................................ 115
6.3.1. Khái niệm và lưu trữ ........................................................................ 115
6.3.2. Các giải thuật.................................................................................... 117
6.4. Cây tổng quát .......................................................................................... 115
6.4.1. Biểu diễn cây tổng quát.................................................................... 120
6.4.3. Áp dụng............................................................................................ 123
6.5. Bài tập ..................................................................................................... 127
6.6. Kiểm tra................................................................................................... 129
CHƢƠNG 7 : SẮP XẾP................................................................................... 130
7.1. Đặt vấn đề ............................................................................................... 130
7.2. Một số phương pháp sắp xếp .................................................................. 130
7.3. Phân tích đánh giá các thuật toán............................................................ 143
7.4. Bài tập ..................................................................................................... 145
CHƢƠNG 8: TÌM KIẾM................................................................................ 147
8.1. Bài toán tìm kiếm.................................................................................... 147
8.2. Tìm kiếm tuần tự..................................................................................... 147
8.3. Tìm kiếm nhị phân .................................................................................. 148
8.4. Cây nhị phân tìm kiếm ............................................................................ 150
8.4.1. Định nghĩa........................................................................................ 150
8.4.2. Các giải thuật.................................................................................... 147
CHƢƠNG 1: MỞ ĐẦU
1.1. GIẢI THUẬT
1.1.1 Khái niệm giải thuật
Giải thuật (Algorithms): là một dãy các câu lệnh (statements) chặt chẽ và rõ
ràng xác định một trình tự các thao tác trên một số đối tượng nào đó sao cho sau
một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. Để minh hoạ
cho khái niệm giải thuật ta xét giải thuật giải bài toán tìm phần tử lớn nhất trong
một dãy hữu hạn các số nguyên.
Giải thuật gồm các bước sau:
Bước 1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy.
Bước 2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn
hơn giá trị cực đại tạm thời, thì đặt cực đại tạm thời bằng số nguyên đó.
Bước 3. Lặp lại bước 2 nếu còn các số nguyên trong dãy
Bước 4. Cực đại tạm thời thu được ở bước này chính là số nguyên lớn nhất của
dãy.
1.1.2. Các đặc trƣng của giải thuật
Giải thuật có các đặc trưng sau:
Đầu vào (Input): Giải thuật nhận dữ liệu đầu vào từ một tập nào đó.
Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, giải thuật đưa ra các
dữ liệu tương ứng với lời giải của bài toán.
Tính chính xác: Các bước của một giải thuật phải được xác định một
cách chính xác.
Tính hữu hạn: Một giải thuật cần phải tạo ra các giá trị đầu ra mong
muốn sau một số hữu hạn ( nhưng có thể rất lớn) các bước đối với mọi tập
đầu vào.
Tính hiệu quả: Mỗi bước của giải thuật cần phải thực hiện được một cách
chính xác và trong một khoảng thời gian hữu hạn.
Tính tổng quát: Thủ tục cần phải áp dụng được cho mọi bài toán có dạng
mong muốn, chứ không phải chỉ cho một tập đặc biệt các giá trị đầu vào.
Ví dụ 1.1: Cho 3 số nguyên a, b, c. Mô tả giải thuật tìm số lớn nhất trong 3 số đã
cho.
Giải: Tuy rằng bài toán đặt ra là rất đơn giản, nhưng mục đích của chúng ta là
dùng nó để giải thích khái niệm giải thuật. Giải thuật gồm các bước sau:
Bước 1: Đặt x := a;
Bước 2: Nếu b > x thì đặt x := b;
Bước 3: Nếu c > x thì đặt x := c;
Tư tưởng của giải thuật là duyệt lần lượt giá trị của từng số và giữ lại giá trị lớn
nhất vào biến x. Kết thúc giải thuật x cho số nguyên lớn nhất trong 3 số đã cho.
1.2. CẤU TRÖC DỮ LIỆU VÀ CÁC VẤN ĐỀ LIÊN QUAN
1.2.1. Cấu trúc dữ liệu và giải thuật
Có thể có lúc khi nói đến việc giải quyết bài toán trên máy tính người ta chỉ
chú ý đến giải thuật, tuy nhiên giải thuật chỉ phản ánh các phép xử lý, còn đối
tượng để xử lý trên máy tính điện tử chính là dữ liệu (data), chúng biểu diễn các
thông tin cần thiết cho bài toán: Các dữ kiện đưa vào (input), các kết quả trung
gian,...Bản thân các phần tử của dữ liệu thường có mối quan hệ với nhau: Với
một mô tả kiểu dữ liệu trừu tượng có thể có nhiều cách cài đặt khác nhau để hình
thành nhiều cấu trúc dữ liệu khác nhau. Ngoài ra, nếu lại biết “tổ chức” theo cấu
trúc thích hợp thì việc thực hiện các phép xử lý trên các dữ liệu sẽ càng thuận lợi
hơn, đạt hiệu quả cao hơn. Với một cấu trúc dữ liệu đã chọn ta sẽ có giải thuật
xử lý tương ứng. Cấu trúc dữ liệu thay đổi, giải thuật cũng thay đổi theo.
Như vậy, giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết: Không
thể nói tới giải thuật mà không nghĩ tới giải thuật đó được tác động trên cấu trúc
dữ liệu nào, còn khi xét tới cấu trúc dữ liệu thì cũng phải xét đến dữ liệu đó cần
được tác động giải thuật gì để đưa lại kết quả mong muốn.
1.2.2. Cấu trúc dữ liệu và ngôn ngữ lập trình
Các ngôn ngữ lập trình ngoài việc cung cấp các kiểu dữ liệu cơ bản, nó còn
cung cấp cơ chế hiệu quả và dễ sử dụng cho phép chúng ta định nghĩa các kiểu
dữ liệu mới (kiểu dữ liệu trừu tượng) theo yêu cầu. Việc chọn một ngôn ngữ lập
trình tức là chấp nhận các cấu trúc tiền định của ngôn ngữ ấy và phải biết linh
hoạt vận dụng chúng để mô phỏng các cấu trúc dữ liệu đã cho cho bài toán cần
giải quyết.
Tuy nhiên, trong thực tế việc lựa chọn một ngôn ngữ không phải chỉ xuất phát
từ yêu cầu của bài toán mà còn phụ thuộc vào rất nhiều yếu tố khách quan cũng
như chủ quan của người lập trình nữa. Thoạt đầu, khi ứng dụng của máy tính
điện tử chỉ mới có trong phạm vi các bài toán khoa học kỹ thuật thì ta chỉ gặp các
cấu trúc dữ liệu đơn giản như biến, véctơ, ma trận,...nhưng khi các ứng dụng đó
đã được mở rộng sang các lĩnh vực khác mà ta thường gọi là bài toán phi số
(non-numerical proplems), với đặc điểm thể hiện ở chỗ: khối lượng dữ liệu lớn,
đa dạng, biến động; phép xử lý thường không chỉ là các phép số học..thì các cấu
trúc dữ liệu tiền định do các ngôn ngữ lập trình cung cấp thường không đủ đặc
trưng cho các mối quan hệ mới của dữ liệu mới. Vì vậy, việc đi sâu nghiên cứu
các cấu trúc dữ liệu phức tạp hơn chính là sự quan tâm của chúng ta trong giáo
trình này.
Bài bài toán phi số đi đôi với các cấu trúc dữ liêu mới cũng xuất hiện các phép
toán mới tác động trên các cấu trúc dữ liệu này, các phép toán đó sẽ có những tác
dụng khác nhau đối với từng cấu trúc dữ liệu. Có phép hữu hiệu đối với cấu trúc
này nhưng lại tỏ ra không hữu hiệu trên cấu trúc khác.
Cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ được gọi là cấu trúc lưu trữ.
Đó chính là cách cài đặt cấu trúc ấy trên máy tính điện tử và trên cơ sở các cấu
trúc lưu trữ này mà ta thực hiện các phép xử lý. Có thể có nhiều cấu trúc lưu trữ
khác nhau cho cùng một cấu trúc dữ liệu; cũng như có những cấu trúc dữ liệu
khác nhau mà được thể hiện trong bộ nhớ bởi cùng một kiểu cấu trúc lưu trữ. Khi
đề cập đến cấu trúc lưu trữ ta cũng cần phân biệt cấu trúc lưu trữ tương ứng với
bộ nhớ trong- lưu trữ trong, hay ứng với bộ nhớ ngoài- lưu trữ ngoài.
1.3. NGÔN NGỮ DIỄN ĐẠT GIẢI THUẬT
1.3.1. Đặt vấn đề
Để diễn đạt các giải thuật mà ta sẽ trình bày trong giáo trình, ta cần một ngôn
ngữ diễn đạt. Ta có thể lựa chọn một ngôn ngữ lập trình nào đó như C, Pascal,
v.v... , nhưng như vậy ta sẽ gặp mấy hạn chế sau:
- Phải luôn luôn tuân thủ các quy tắc chặt chẽ về cú pháp của ngôn ngữ đó,
khiến cho việc trình bày về giải thuật và cấu trúc dữ liệu có thiên hướng
nặng nề, gò bó.
- Phải phụ thuộc vào cấu trúc dữ liệu tiền định của ngôn ngữ, nên có lúc
không thể hiện được đầy đủ các ý nghĩa về cấu trúc mà ta muốn biểu đạt.
- Ngôn ngữ nào được chọn cũng không hẳn đã được mọi người ưa thích và
muốn sử dụng.
Vì vậy, ở đây ta sẽ dùng một ngôn ngữ “thô hơn”, có đủ khả năng diễn đạt
được giải thuật trên các cấu trúc đề cập đến (mà ta giới thiệu bằng tiếng Việt),
với một mức độ linh hoạt nhất định, không quá gò bó, không câu nệ nhiều về cú
pháp nhưng cũng gần gũi với các ngôn ngữ chuẩn, để khi cần thiết dễ dàng
chuyển đổi. Ta tạm gọi nó bằng cái tên: “ngôn ngữ tựa PASCAL”.
1.3.2. Quy cách về cấu trúc chƣơng trình
Mỗi chương trình đều được gắn một tên để phân biệt, tên này được viết bằng
chữ in hoa, có thể có thêm dấu gạch nối và bắt đầu bằng từ khoá Program.
Ví dụ 1.2: Program NHAN_MA_TRAN
Độ dài của tên không hạn chế.
Sau tên có thể kèm theo lời thuyết minh (ở đây ta quy ước dùng tiếng Việt) để
giới thiệu tóm tắt nhiệm vụ của giải thuật hoặc một số chi tiết cần thiết. Phần
thuyết minh được đặt giữa hai dấu { …….. }.
Chương trình bao gồm nhiều đoạn (bước), mỗi đoạn được phân biệt bởi số thứ
tự, có thể kèm theo những lời thuyết minh.
1.3.3. Ký tự và biểu thức
Ký tự dùng ở đây cũng giống như trong các ngôn ngữ chuẩn, nghĩa là gồm:
- 26 chữ cái latinh in hoa hoặc in thường.
- 10 chữ số thập phân.
- Các dấu phép toán số học +, -, *, /, (luỹ thừa)
- Các dấu phép toán quan hệ <, =, >, ≤, ≥, ≠
- Giá trị logic: true, false
- Dấu phép toán logic: and, or, not
- Tên biến: dãy chữ cái và chữ số, bắt đầu bằng chữ cái.
- Biến chỉ số có dạng: A[i], B[i, j], v.v...
Còn biểu thức cũng như thứ tự ưu tiên của các phép toán trong biểu thức
cũng theo quy tắc như trong PASCAL hay các ngôn ngữ chuẩn khác.
1.3.4. Các câu lệnh
Các câu lệnh trong chương trình được viết cách nhau bởi dấu ; chúng bao
gồm:
1- Câu lệnh gán
Có dạng V := E;
Với V chỉ tên biến, tên hàm; E chỉ biểu thức. Ở đây cho phép dùng phép gán
chung.
Ví dụ: A :=B := 0.1;
2- Câu lệnh ghép
Có dạng: begin S1; S2; …; Sn; end;
Với Si (i = 1, .., n) là các câu lệnh. Nó cho phép ghép nhiều câu lệnh lại để
được coi như một câu lệnh.
3- Câu lệnh điều kiện
Có dạng: if B then S;
Với B là biểu thức logic, S là một câu lệnh khác.
Có thể diễn tả bởi sơ đồ
true
S
false
hoặc
if B then S1 else S2;
true
S1
S2
false
4- Câu lệnh tuyển
Có dạng: Case
B1: S1;
….
Bn: Sn;
Else:Sn+1;
End case;
Với Bi (i = 1, 2, .., n) là các điều kiện, Si (i = 1, 2, .., n) là các câu lệnh. Câu
lệnh này cho phép phân biệt các tình huống xử lý khác nhau trong các điều kiện
khác nhau mà không phải dùng tới các câu lệnh if- then- else lồng nhau. Có thể
biểu diễn bởi sơ đồ:
false
false
false…
B1
B2
Bn
Sn+1
true
true
true
S1
S2
S2
. Vài điểm linh động
Else có thể không có mặt. Si (i = 1, 2, .., n) có thể được thay bằng một dãy
các câu lệnh thể hiện một dãy xử lý khi có điều kiện Bi mà không cần phải đặt
giữa begin và end.
5- Câu lệnh lặp
. Với số lần lặp biết trước.
For i := m to n do S;
Nhằm thực hiện câu lệnh S với i lấy giá trị nguyên từ m tới n ( n >= m) với
bước nhảy tăng bằng 1;
Hoặc:
For i:= n downto m do S;
Tương tự như câu lệnh trên với bước nhảy giảm bằng 1.
. Với số lần lặp không biết trước
While B do S;
true
S
B
false
Chừng nào mà B có giá trị bằng true thì thực hiện S
Hoặc:
Repeat S until B;
Lặp lại S cho tới khi B có giá trị true (S có thể là một dãy lệnh)
true
S
B
false
6- Câu lệnh chuyển
Goto n; (n là số hiệu của một bước trong chương trình)
Thường người ta hạn chế việc sử dụng goto. Tuy nhiên, với mục đích diễn
đạt cho tự nhiên, trong một chừng mực nào đó ta vẫn sử dụng.
7- Câu lệnh vào, ra
Có dạng:
Read (<danh sách biến>);
Write (<danh sách các biến hoặc dòng ký tự>);
Các biến trong danh sách cách nhau bởi dấu phẩy. Dòng ký tự là một dãy các
ký tự đặt giữa hai dấu nháy „ và „.
8- Câu lệnh kết thúc chương trình.
End.
1.3.4 Chương trình con.
. Chương trình con hàm
Có dạng:
Function <Tên hàm> (<danh sách tham số>)
S1; S2; … ; Sn;
Return <biểu thức>;
Câu lệnh kết thúc chương trình con ở đây là return thay cho end.
. Chương trình con thủ tục
Procedure <Tên thủ tục> (<danh sách tham số>)
S1; S2; … ; Sn;
Return ;
Lời gọi chương trình con hàm thể hiện bằng tên hàm cùng danh sách tham số
thực sự, nằm trong biểu thức. Còn với chương trình con thủ tục lời gọi được thể
hiện bằng câu lệnh call có dạng:
Call <tên thủ tục> (<danh sách tham số thực sự>)
Chú ý: Trong các chương trình diễn đạt một số giải thuật ở đây phần khai báo
dữ liệu được bỏ qua. Nó được thay bởi phần mô tả cấu trúc dữ liệu bằng ngôn
ngữ tự nhiên, mà ta sẽ nêu ra trước khi bước vào giải thuật.
Như vậy, nghĩa là các chương trình được nêu ra chỉ là đoạn thể hiện các phép
xử lý theo giải thuật đã định, trên các cấu trúc dữ liệu được mô tả trước đó, bằng
ngôn ngữ tự nhiên.
CHƢƠNG 2 : THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT
2.1. TỪ BÀI TOÁN ĐẾN CHƢƠNG TRÌNH
2.1.1 Mô - đun hoá và việc giải quyết bài toán
Các bài toán được giải trên máy tính điện tử ngày càng đa dạng và phức tạp.
Các giải thuật và chương trình để giải chúng cũng ngày càng có quy mô lớn và
càng khó khi thiết lập cũng như khi muốn tìm hiểu.
Tuy nhiên, ta cũng thấy rằng mọi việc sẽ đơn giản hơn nếu như có thể phân
chia bài toán lớn của ta thành các bài toán nhỏ. Điều đó cũng có nghĩa là nếu coi
bài toán của ta như một mô-đun chính thì cần chia nó thành các mô-đun con, và
dĩ nhiên, với tinh thần như thế, đến lượt nó, mỗi mô-đun này lại được phân chia
tiếp cho tới những mô-đun ứng với các phần việc cơ bản mà ta đã biết cách giải
quyết. Như vậy, việc tổ chức lời giải của bài toán sẽ được thể hiện theo một cấu
trúc phân cấp, có dạng như hình sau:
A
B
C
D
E
F
G
H
I
Hình 2.1
Chiến thuật giải quyết bài toán theo tinh thần như vậy chính là chiến thuật
“chia để trị” (divide and conquer). Để thể hiện chiến thuật đó, người ta dùng cách
thiết kế “đỉnh- xuống” (top-down design). Đó là cách phân tích tổng quát toàn bộ
vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra, để đề cập đến những công
việc chủ yếu, rồi sau đó mới đi dần vào giải quyết các phần cụ thể một cách chi
tiết hơn (cũng vì vậy mà người ta gọi là cách thiết kế từ khái quát đến chi tiết). Ví
dụ ta nhận được từ chủ tịch hội đồng xét cấp học bổng của trường một yêu cầu
là:
“Dùng máy tính điện tử để quản lý và bảo trì hồ sơ về học bổng của các sinh
viên ở diện được tài trợ, đồng thời thường kỳ phải lập các báo cáo tổng kết để đệ
trình lên bộ”
Như vậy, trước hết ta phải hình dung được cụ thể hơn đầu vào và đầu ra của
bài toán. Có thể coi như ta đã có một tập hồ sơ (mà ta gọi là tệp file) bao gồm các
bản ghi (records) về các thông tin liên quan tới học bổng của sinh viên, Chẳng
hạn: số hiệu sinh viên, điểm trung bình (theo học kỳ), điểm đạo đức, khoản tiền
tài trợ. Và chương trình lập ra phải tạo điều kiện cho người sử dụng giải quyết
được các yêu cầu sau:
1. Tìm lại và hiển thị được bản ghi của bất kỳ sinh viên nào tại thiết bị cuối
(terminal) của người dùng.
2. Cập nhập (update) được bản ghi của một sinh viên cho trước bằng cách
thay đổi điểm trung bình, điểm đạo đức, khoản tiền tài trợ, nếu cần.
3. In bản tổng kết chứa những thông tin hiện thời ( đã được cập nhập mỗi khi
có thay đổi) gồm số liệu, điểm trung bình, điểm đạo đức, khoản tiền tài trợ.
Xuất phát từ những nhận định nêu trên, giải thuật xử lý sẽ phải giải quyết ba
nhiệm vụ chính như sau:
1. Những thông tin về sinh viên được học bổng, lưu trữ trên đĩa phải được
đọc vào bộ nhớ trong để có thể xử lý ( ta gọi là nhiệm vụ “đọc tệp”).
2. Xử lý các thông tin này để tạo ra kết quả mong muốn (nhiệm vụ ”xử lý
tệp”).
3. Sao chép những thông tin đã được cập nhập vào tệp trên đĩa để lưu trữ cho
việc xử lý sau này (nhiệm vụ ”ghi tệp”)
Có thể hình dung, cách thiết kế này theo sơ đồ cấu trúc ở hình 2.2.
Hệ hỗ trợ quản lý học
bổng
Đọc tệp
Xử lý tệp
Ghi tệp
Hình 2.2
Các nhiệm vụ ở mức đầu này thường tương đối phức tạp, cần phải chia thành
các nhiệm vụ con. Chẳng hạn nhiệm vụ “xử lý tệp” sẽ được phân thành ba, tương
ứng với việc giải quyết ba yêu cầu chính đã được nêu ở trên:
1) Tìm lại bản ghi của một sinh viên cho trước
2) Cập nhập thông tin trong bản ghi sinh viên
3) In bản tổng kết những thông tin về các sinh viên được học bổng.
Những nhiệm vụ con này cũng có thể được chia thành những nhiệm vụ nhỏ
hơn. Có thể hình dung theo sơ đồ cấu trúc như sau:
Xử lý tệp
Tìm bản ghi
Cập nhật bản ghi
In bản tổng
Tìm kiếm
Hiển thị bản ghi
Tìm kiếm
Cập nhật
Hình 2.3
Cách thiết kế giải thuật theo kiểu top-down như trên giúp cho việc giải quyết
bài toán được định hướng rõ ràng, tránh sa đà ngay vào các chi tiết phụ. Nó cũng
là nền tảng cho việc lập trình có cấu trúc.
Thông thường đối với các bài toán lớn, việc giải quyết nó phải do nhiều người
cùng làm. Chính phương pháp mô-đun hóa sẽ cho phép tách bài toán ra thành các
phần độc lập tạo điều kiện cho các nhóm giải quyết phần việc của mình mà
không làm ảnh hưởng gì đến nhóm khác. Với chương trình được xây dựng trên
cơ sở của các giải thuật được thiết kế theo cách này thì việc tìm hiểu cũng như
sửa chữa, chỉnh lý sẽ dễ dàng hơn.
Việc phân bài toán thành các bài toán con như thế không phải là một việc làm
dễ dàng. Chính vì vậy mà có những bài toán nhiệm vụ phân tích và thiết kế giải
thuật giải bài toán đó còn mất nhiều thời gian và công sức hơn cả nhiệm vụ lập
trình.
2.1.2. Phƣơng pháp tinh chỉnh từng bƣớc
1) Phƣơng pháp
Tinh chỉnh từng bước là phương pháp thiết kế giải thuật gắn liền với lập trình.
Nó phản ánh tinh thần của quá trình mô-đun hoá bài toán thiết kế kiểu top-down.
Thoạt đầu chương trình thể hiện giải thuật được trình bày bằng ngôn ngữ tự
nhiên phản ánh ý chính của công việc cần làm. Từ các bước sau những lời,
những ý đó sẽ được chi tiết hoá dần dần tương ứng với những công việc nhỏ hơn.
Ta gọi đó là các bước tinh chỉnh, sự tinh chỉnh này sẽ được hướng về phía ngôn
ngữ lập trình mà ta đã chọn. Càng ở các bước sau các lời lẽ đặc tả công việc xử
lý sẽ được thay thế dần bởi các câu lệnh hướng tới câu lệnh của ngôn ngữ lập
trình. Muốn vậy, ở các giai đoạn trung gian người ta thường dùng pha tạp cả
ngôn ngữ tự nhiên lẫn ngôn ngữ lập trình, mà người ta gọi là giả ngôn ngữ
(pseudo-language) hay giả mã (pseudo code). Như vậy, nghĩa là quá trình thiết kế
giải thuật và phát triển chương trình sẽ được thể hiện dần dần từ dạng ngôn ngữ
tự nhiên, qua giả ngôn ngữ rồi đến ngôn ngữ lập trình và đi từ mức “là cái gì”
đến mức “làm thế nào”, ngày càng sát với các chức năng ứng với các câu lệnh
của ngôn ngữ lập trình đã chọn. Trong quá trình này dữ liệu cũng được “tinh
chế” từ dạng cấu trúc đến dạng lưu trữ cài đặt cụ thể.
2) Bài toán sắp xếp
Giả sử ta muốn lập một chương trình sắp xếp một dãy n số nguyên khác
nhau theo thứ tự tăng dần.
Có thể phác thảo giải thuật như sau: “Từ dãy các số nguyên chưa được sắp xếp
chọn ra số nhỏ nhất, đặt nó vào cuối dãy đã được sắp xếp. Cứ lặp lại quy trình đó
cho tới khi dãy chưa được sắp xếp chỉ còn một số”.
Ta thấy phác hoạ trên còn đang rất thô, nó chỉ thể hiện những ý cơ bản. Hình
dung cụ thể hơn một chút ta thấy, thoạt đầu dãy số chưa được sắp xếp chính là
dãy số đã cho. Dãy số đã được sắp xếp còn rỗng, chưa có phần tử nào. Vậy thì
nếu chọn được số nhỏ nhất đầu tiên và đặt vào cuối dãy đã được sắp thì cũng
chính là đặt vào vị trí đầu tiên của dãy này. Nhưng dãy này đặt ở đâu?
Thế thì phải hiểu dãy số mà ta sẽ sắp xếp được đặt tại chỗ cũ hay đặt ở chỗ
khác? Điều đó đòi hỏi phải chi tiết hơn về cấu trúc dữ liệu và cấu trúc lưu trữ của
dãy số cho.
Trước hết ta ấn định: dãy số cho ở đây được coi như dãy các phần tử của một
vectơ (sau này ta nói: nó có cấu trúc của mảng một chiều) và dãy này được lưu
trữ bởi một vectơ lưu trữ gồm n từ máy kế tiếp ở bộ nhớ trong (a1, a2, .., an) mỗi
từ máy ai lưu trữ phần tử thứ i (1 ≤ i ≤ n) của dãy số.
Ta cũng qui ước: dãy số được sắp xếp rồi vẫn để tại chỗ cũ như dãy đã cho.
Vậy thì việc đặt “số nhỏ nhất” vừa được chọn, ở một lượt nào đó, vào cuối dãy
đã được sắp xếp phải thực hiện bằng cách đổi chỗ cho số hiện đang ở vị trí đó
(nếu như nó khác số này).
Giả sử ta đang định hướng chương trình của ta vào vào ngôn ngữ tựa
PASCAL, nêu ở chương 1, thì bước tinh chỉnh đầu tiên sẽ như sau:
For i :=1 to n-1 do
begin
- Xét từ ai đến an để tìm số nhỏ nhất aj
- Đổi chỗ giữa ai và aj nếu ai khác aj
end
Tới đây ta thấy có hai nhiệm vụ con, cần làm rõ thêm.
1. Tìm số nguyên nhỏ nhất aj trong các số từ ai đến an
2. Đổi chỗ giữa aj với ai nếu ai khác aj
Nhiệm vụ đầu có thể thực hiện bằng cách:
“Thoạt tiên coi ai là “số nhỏ nhất” tạm thời; lần lượt so sánh ai với ai+1, ai+2,
v.v…Khi thấy số nào nhỏ hơn thì lại coi đó là “số nhỏ nhất” mới. Khi đã so sánh
với an rồi thì số nhỏ nhất sẽ được xác định”
Nhưng xác định bằng cách nào? Có thể bằng cách chỉ ra chỗ của nó, nghĩa là
nắm được chỉ số của phần tử ấy. Ta có bước tinh chỉnh 2.1:
j := i;
For k :=j +1 to n do
If ak < aj then j := k;
Với nhiệm vụ thứ hai thì có thể giải quyết bằng cách tương tự như khi ta muốn
chuyển hai thứ rượu trong hai ly, từ ly nọ sang ly kia: ta sẽ phải dùng một ly thứ
ba (không đựng gì) để làm ly trung chuyển. Ta có bước tinh chỉnh 2.2:
B := ai ; ai := aj ; aj := B;
Sau khi đã chỉnh lại cách viết biến chỉ số cho đúng với quy ước ta có chương
trình sắp xếp dưới dạng thủ tục như sau:
Procedure SORT (A, n)
1. for i := 1 to n-1 do
begin
2. j := i;{chọn số nhỏ nhất}
for k :=j +1 to n do
if A[k] < A[j] then j := k;
3. if A[i] ≠ A[j] then
begin
B := A[i]; A[i] := A[j]; A[j] := B; {Đổi chỗ}
end;
end;
4. Return;
3) Bài toán hiển thị các đƣờng chéo của ma trận
Phát biểu bài toán: Cho một ma trận vuông n x n các số nguyên. Hãy in ra các
phần tử thuộc đường chéo song song với đường chéo chính.
Ví dụ: Cho ma trận vuông với n = 3
3
4
9
5
11
0
7
2
8
Giả sử ta chọn cách in từ phải sang trái, thì có kết quả:
11
5
3
4
9
0
7
2
8
Ta sẽ hướng việc thể hiện giải thuật về một chương trình PASCAL. Giải thuật
có thể phác hoạ như sau:
1- Nhập n
2- Nhập các phần tử của ma trận
3- In các đường chéo song song với đường chéo chính
Hai nhiệm vụ 1 và 2 có thể diễn đạt dễ dàng bằng PASCAL:
1. readln (n);
2. for i := 1 to n do
for j := 1 to n do readln(a[i, j]);
Nhiệm vụ 3 cần phân tích kỹ hơn. Ta thấy về đường chéo, có thể phân làm
hai loại:
- Đường chéo ứng với cột từ n đến 1
- Đường chéo ứng với hàng từ 2 đến n
Vì vậy, ta tách thành hai nhiệm vụ con:
3.1. for j := n down to 1 do { in đường chéo ứng với cột j }
3.2. for i := 2 to n do { in đường chéo ứng với hàng i }
Tới đây ta lại phải chi tiết hơn công việc: “in đường chéo ứng cột j”
Với j = n thì in một phần tử hàng 1 cột j
j = n - 1 thì in 2 phần tử hàng 1 cột j và hàng 2 cột j + 1
j = n - 2 thì in 3 phần tử hàng 1 cột j, hàng 2 cột j + 1 và hàng 3 cột j + 2
Ta thấy số lượng các phần tử được in chính là (n- j + 1), còn phần tử được in
chính là A[i, j + i-1], với i lấy giá trị từ 1 tới (n- j + 1)
Vậy 3.1 có thể tinh chỉnh tiếp tác vụ “in đường chéo ứng với cột j” thành:
for i := 1 to (n-j +1) do Write (a[i, j + i - 1] : 8);
Writeln;
Ở đây, ta tận dụng khả năng của PASCAL để in mỗi phần tử trong một quãng
8 và mỗi đường chéo sẽ được in trên một dòng, sau đó để cách một dòng trống.
Với 3.2 cũng tương tự
for j := 1 to n- i + 1 do Write (a[i + j - 1, j)]:8);
Writeln;
Để có một chương trình Pascal hoàn chỉnh tất nhiên ta phải tuân thủ mọi quy
định của PASCAL: chẳng hạn trước khi bước vào phần câu lệnh thể hiện phần xử
lý, phải có phần khai báo dữ liệu.
Ngoài ra có thể thêm vào phần thuyết minh cho các bước (với một ngoại lệ là
ta viết bằng tiếng Việt).
Sau đây là chương trình hoàn chỉnh:
Program INCHEO;
Const
max = 30;
Type matran = array [1…max, 1…max] of integer;
Var
a: matran; n, i, j:integer;
Begin
Repeat
Write („nhập kích thước n của ma trận‟); Readln (n);
Until (0 < n) and (n <= max);
Writeln („Nhập phần tử ma trận‟);
For i := 1 to n do
For j := 1 to n do readln (a[i, j]);
Writeln („In các đường chéo‟)
For j := n downto 1 do
Begin
For i := 1 to n- j + 1 do Write (a[i, j + i - 1] : Writeln;
End;
For i := 2 to n do
Begin
For j := 1 to n- i + 1 do Write(a[i + j - 1, j] : 8);
Writeln;
End;
End.
4) Bài toán thiết lập quy trình điều khiển đèn giao thông
Phát biểu bài toán: Giả sử ta cần thiết lập một quy trình đèn giao thông ở một
chốt giao thông phức tạp, có nhiều giao lộ.
Như vậy nghĩa là điều khiển đèn báo sao cho trong một khoảng thời gian ấn
định một số tuyến đường được thông, trong khi một số tuyến khác bị cấm, tránh
xảy ra đụng độ.
Đối với bài toán này ta thấy: Ta nhận ở đầu vào một số tuyến đường cho phép
(tại chốt giao thông đó) và phải phân hoạch tập này thành một số ít nhất các
nhóm, sao cho mọi tuyến trong một nhóm đều có thể cho thông đồng thời mà
không xảy ra đụng độ. Ta sẽ gắn mỗi pha của việc điều khiển đèn giao thông với
một nhóm trong phân hoạch này và việc tìm một phân hoạch với số pha ít nhất.
Điều đó có nghĩa là thời gian chờ đợi tối đa để được thông cũng ít nhất.
Ví dụ như ở đầu mối sau
D
E
C
B
A
Hình 2.4
Ở đây C và E là đường một chiều (1 tuyến) còn các đường khác đều hai chiều
(2 tuyến). Như vậy, sẽ có 13 tuyến có thể thực hiện qua đầu mối này. Những
tuyến như AB (từ A tới B), EC có thể thông đồng thời. Những tuyến như AD và
EB thì không thể thông đồng thời được vì chúng giao nhau, có thể gây ra đụng độ
( ta sẽ gọi là các tuyến xung khắc). Như vậy đèn tín hiệu phải báo sao cho AD và
EB không thể được thông cùng một lúc, trong khi đó lại phải cho phép AB và EC
chẳng hạn được thông đồng thời.
Ta có thể mô hình hoá bài toán của ta dựa vào một khái niệm, vốn đã được đề
cập tới trong toán học, đó là đồ thị (graph).
Đồ thị bao gồm một tập các điểm gọi là đỉnh (vetices) và các đường nối các
đỉnh gọi là cung (edges). Như vậy đối với bài toán “điều khiển hướng đèn giao
thông”của ta thì có thể hình dung một đồ thị mà các đỉnh biểu thị cho các tuyến
đường, còn cung là một cặp đỉnh ứng với hai tuyến đường xung khắc.
Với một đầu mối giao thông như ở hình 2.4 đồ thị biểu diễn nó sẽ như sau:
AB
BA
DA
EA
AC
BC
DB
EB
AD
BD
DC
ED
EC
Hình 2.5
Bây giờ ta sẽ tìm lời giải cho bài toán của ta dựa trên mô hình đồ thị đã nêu.
Ta sẽ thêm vào khái niệm “tô màu cho đồ thị”. Đó là việc gán màu cho mỗi đỉnh
của đồ thị sao cho không có hai đỉnh nào nối với nhau bởi một cung lại tô một
màu.
Với khái niệm này, nếu ta hình dung mỗi màu đại diện cho một pha điều khiển
đèn báo (cho thông một số tuyến và cấm một số tuyến khác) thì bài toán đang đặt
ra chính là bài toán: tô màu cho đồ thị ứng với các tuyến đường ở một đầu mối,
như đã quy ước ở trên ( xem hình 2.5) sao cho phải dùng ít mầu nhất.
Bài toán tô màu cho đồ thị được nghiên cứu từ nhiều thập kỷ nay. Tuy nhiên,
bài toán tô màu cho một đồ thị bất kỳ, với số màu ít nhất lại thuộc vào một lớp
khá rộng các bài toán, được gọi là “Bài toán N-P đầy đủ”, mà đối với chúng thì
những bài giải hiện có chủ yếu thuộc loại “cố hết mọi khả năng”. Trong trường
hợp bài toán tô màu của ta thì “cố hết mọi khả năng” nghĩa là cố gán màu cho
các đỉnh, trước hết bằng một màu đã, không thể được nữa thì mới dùng màu thứ
hai, thứ ba v.v… Cho tới khi đạt được mục đích, nghe ra thì có vẻ tầm thường,
nhưng đối với bài toán loại này, đây lại chính là một giải thuật có hiệu lực thực
tế. Vấn đề gay cấn nhất ở đây vẫn là khả năng tìm được lời giải tối ưu cho bài
toán.
Nếu đồ thị nhỏ, ta có thể cố gắng theo mọi phương án, để có thể đi tới một lời
giải tối ưu. Nhưng với đồ thị lớn thì cách làm này sẽ tổn phí rất nhiều thời gian,
trên thực tế khó chấp nhận được. Cũng có thể có trường hợp do dựa vào một số
thông tin phụ của bài toán mà việc tìm lời giải tối ưu không cần phải thử tới mọi
khả năng. Nhưng đó chỉ là “những dịp may hiếm có”. Còn một cách khác nữa là
thay đổi cách nhìn nhận về lời giải của bài toán đi đôi chút: Thay vì đi tìm lời
giải tối ưu, ta đi tìm một lời giải “tốt” theo nghĩa là: nó đáp ứng được yêu cầu,
trong một thời gian ngắn mà thực tế chấp nhận được. Một giải thuật “tốt” như
vậy (tuy lời giải không phải là tối ưu) được gọi là giải thuật heuristic.
Một giải thuật heuristic hợp lý đối với bài toán tô màu cho đồ thị đã nêu là giải
thuật sau đây, mà nó được gán cho một cái tên khá ngộ nghĩnh là giải thuật “háu
ăn” (greedy algorithm). Đầu tiên, ta cố tô màu cho các đỉnh nhiều hết mức có thể,
bằng một màu. Với các đỉnh còn lại (chưa được tô) lại làm hết mức có thể với
màu thứ hai, và cứ như thế.
Để tô màu cho các đỉnh với màu mới, ta sẽ thực hiện các bước sau:
1- Chọn một đỉnh chưa được tô màu nào đó và tô cho nó bằng màu mới.
2- Tìm trong danh sách các đỉnh chưa được tô màu, với mỗi đỉnh đó xác
định xem có một cung nào nối nó với một đỉnh đã được tô bằng màu mới chưa.
Nếu chưa có thì tô đỉnh đó bằng màu mới.
3
1
5
2
4
Hình 2.6
Cách tiếp cận này có tên là “háu ăn” vì nó thực hiện tô màu một đỉnh nào đó
mà nó có thể tô được, không hề chú ý gì đến tình huống bất lợi có thể xuất hiện
khi làm điều đó. Chẳng hạn, với đồ thị (hình 2.6) thì như sau:
Nếu nó tô màu xanh cho đỉnh thì theo thứ tự nó sẽ tìm đến và cũng tô
luôn màu xanh. Như vậy thì , sẽ phải tô đỏ, rồi sẽ phải tô tím chẳng hạn,
Tải về để xem bản đầy đủ
102 trang
21160
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_1.pdf
