Giáo trình Cấu trúc dữ liệu và giải thuật - Học viện Công nghệ Bưu chính viễn thông
HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(Dùng cho sinh viên hệ đào tạo đại học từ xa)
Lƣu hành nội bộ
HÀ NỘI - 2007
LỜI NÓI ĐẦU
Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên ngành Công
nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật đƣợc xem nhƣ là 2 yếu tố quan trọng nhất
trong lập trình, đúng nhƣ câu nói nổi tiếng của Niklaus Wirth: Chƣơng trình = Cấu trúc dữ liệu +
Giải thuật (Programs = Data Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải
thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng nhƣ sử dụng các
công cụ lập trình hiện đại.
Cấu trúc dữ liệu có thể đƣợc xem nhƣ là 1 phƣơng pháp lƣu trữ dữ liệu trong máy tính
nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệu một cách hiệu quả
thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là
2 yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau. Việc lựa chọn một cấu trúc
dữ liệu có thể sẽ ảnh hƣởng lớn tới việc lựa chọn áp dụng giải thuật nào.
Tài liệu “Cấu trúc dữ liệu và giải thuật” bao gồm 7 chƣơng, trình bày về các cấu trúc dữ liệu
và các giải thuật cơ bản nhất trong tin học.
Chƣơng 1 trình bày về phân tích và thiết kế thuật toán. Đầu tiên là cách phân tích 1 vấn đề,
từ thực tiễn cho tới chƣơng trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng
máy tính. Tiếp theo, các phƣơng pháp phân tích, đánh giá độ phức tạp và thời gian thực hiện giải
thuật cũng đƣợc xem xét trong chƣơng. Chƣơng 2 trình bày về đệ qui, một khái niệm rất cơ bản
trong toán học và khoa học máy tính. Việc sử dụng đệ qui có thể xây dựng đƣợc những chƣơng
trình giải quyết đƣợc các vấn đề rất phức tạp chỉ bằng một số ít câu lệnh, đặc biệt là các vấn đề
mang bản chất đệ qui.
Chƣơng 3, 4, 5, 6 trình bày về các cấu trúc dữ liệu đƣợc sử dụng rất thông dụng nhƣ mảng
và danh sách liên kết, ngăn xếp và hàng đợi, cây, đồ thị. Đó là các cấu trúc dữ liệu cũng rất gần
gũi với các cấu trúc trong thực tiễn. Chƣơng 7 trình bày về các thuật toán sắp xếp và tìm kiếm.
Các thuật toán này cùng với các kỹ thuật đƣợc sử dụng trong đó đƣợc coi là các kỹ thuật cơ sở
cho lập trình máy tính. Các thuật toán đƣợc xem xét bao gồm các lớp thuật toán đơn giản và cả
các thuật toán cài đặt phức tạp nhƣng có thời gian thực hiện tối ƣu.
Cuối mỗi phần đều có các câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm tra kiến thức
của mình. Cuối tài liệu có các phụ lục hƣớng dẫn trả lời câu hỏi, mã nguồn tham khảo và tài liệu
tham khảo.
Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể đƣợc biểu diễn và cài đặt bằng
bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có đƣợc các phân tích sâu sắc hơn và có kết
quả thực tế hơn, tác giả đã sử dụng ngôn ngữ lập trình C để minh hoạ cho các cấu trúc dữ liệu và
thuật toán. Do vậy, ngoài các kiến thức cơ bản về tin học, ngƣời đọc cần có kiến thức về ngôn ngữ
lập trình C.
Cuối cùng, mặc dù đã hết sức cố gắng nhƣng chắc chắn không tránh khỏi các thiếu sót. Tác
giả rất mong nhận đƣợc sự góp ý của bạn đọc và đồng nghiệp để tài liệu đƣợc hoàn thiện hơn.
Hà Nội, tháng 10/2007
CHƢƠNG 1
PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT
Chƣơng 1 trình bày các khái niệm về giải thuật và phƣơng pháp tinh chỉnh từng bƣớc
chƣơng trình đƣợc thể hiện qua ngôn ngữ diễn đạt giải thuật. Chƣơng này cũng nêu phƣơng pháp
phân tích và đánh giá một thuật toán, các khái niệm liên quan đến việc tính toán thời gian thực
hiện chƣơng trình.
Trong mỗi phần đều có các minh hoạ cụ thể. Phần đầu đƣa ra ví dụ về bài toán nút giao
thông và phƣơng pháp giải quyết bài toán từ phân tích vấn đề cho đến thiết kế giải thuật, tinh
chỉnh từng bƣớc cho tới mức cụ thể hơn. Phần 2 đƣa ra một ví dụ về phân tích và tính toán thời
gian thực hiện giải thuật sắp xếp nổi bọt.
Để học tốt chƣơng này, sinh viên cần nắm vững phần lý thuyết và tìm các ví dụ tƣơng tự để
thực hành phân tích, thiết kế, và đánh giá giải thuật.
1.1 GIẢI THUẬT VÀ NGÔN NGỮ DIỄN ĐẠT GIẢI THUẬT
1.1.1 Giải thuật
Trong thực tế, khi gặp phải một vấn đề cần phải giải quyết, ta cần phải đƣa ra 1 phƣơng
pháp để giải quyết vấn đề đó. Khi muốn giải quyết vấn đề bằng cách sử dụng máy tính, ta cần
phải đƣa ra 1 giải pháp phù hợp với việc thực thi bằng các chƣơng trình máy tính. Thuật ngữ
“thuật toán” đƣợc dùng để chỉ các giải pháp nhƣ vậy.
Thuật toán có thể đƣợc định nghĩa nhƣ sau:
Thuật toán là một chuỗi hữu hạn các lệnh. Mỗi lệnh có một ngữ nghĩa rõ ràng và có thể
được thực hiện với một lượng hữu hạn tài nguyên trong một khoảng hữu hạn thời gian.
Chẳng hạn lệnh x = y + z là một lệnh có các tính chất trên.
Trong một thuật toán, một lệnh có thể lặp đi lặp lại nhiều lần, tuy nhiên đối với bất kỳ bộ dữ
liệu đầu vào nào, thuật toán phải kết thúc sau khi thực thi một số hữu hạn lệnh.
Nhƣ đã nói ở trên, mỗi lệnh trong thuật toán phải có ngữ nghĩa rõ ràng và có thể đƣợc thực
thi trong một khoảng thời gian hữu hạn. Tuy nhiên, đôi khi một lệnh có ngữ nghĩa rõ ràng đối với
ngƣời này nhƣng lại không rõ ràng đối với ngƣời khác. Ngoài ra, thƣờng rất khó để chứng minh
một lệnh có thể đƣợc thực hiện trong 1 khoảng hữu hạn thời gian. Thậm chí, kể cả khi biết rõ ngữ
nghĩa của các lệnh, cũng khó để có thể chứng minh là với bất kỳ bộ dữ liệu đầu vào nào, thuật
toán sẽ dừng.
Tiếp theo, chúng ta sẽ xem xét một ví dụ về xây dựng thuật toán cho bài toán đèn giao
thông:
Giả sử ngƣời ta cần thiết kế một hệ thống đèn cho một nút giao thông có nhiều đƣờng giao
nhau phức tạp. Để xây dựng tập các trạng thái của các đèn giao thông, ta cần phải xây dựng một
chƣơng trình có đầu vào là tập các ngã rẽ đƣợc phép tại nút giao thông (lối đi thẳng cũng đƣợc
xem nhƣ là 1 ngã rẽ) và chia tập này thành 1 số ít nhất các nhóm, sao cho tất cả các ngã rẽ trong
nhóm có thể đƣợc đi cùng lúc mà không xảy ra tranh chấp. Sau đó, chúng ta sẽ gắn trạng thái của
các đèn giao thông với mỗi nhóm vừa đƣợc phân chia. Với cách phân chia có số nhóm ít nhất, ta
sẽ xây dựng đƣợc 1 hệ thống đèn giao thông có ít trạng thái nhất.
3
Chẳng hạn, ta xem xét bài toán trên với nút giao thông đƣợc cho nhƣ trong hình 1.1 ở
dƣới. Trong nút giao thông trên, C và E là các đƣờng 1 chiều, các đƣờng còn lại là 2 chiều. Có tất
cả 13 ngã rẽ tại nút giao thông này. Một số ngã rẽ có thể đƣợc điđồng thời, chẳng hạn các ngã rẽ
AB (từ A rẽ sang B) và EC. Một số ngã rẽ thì không đƣợc đi đồng thời (gây ra các tuyến giao
thông xung đột nhau), chẳng hạn AD và EB. Hệ thống đèn tại nút giao thông phải hoạt động sao
cho các ngã rẽ xung đột (chẳng hạn AD và EB) không đƣợc cho phép đi tại cùng một thời điểm,
trong khi các ngã rẽ không xung đột thì có thể đƣợc đi tại cũng 1 thời điểm.
E
D
C
B
A
Hình 1.1 Nút giao thông
Chúng ta có thể mô hình hóa vấn đề này bằng một cấu trúc toán học gọi là đồ thị (sẽ đƣợc
trình bày chi tiết ở chƣơng 5). Đồ thị là một cấu trúc bao gồm 1 tập các điểm gọi là đỉnh và một
tập các đƣờng nối các điểm, gọi là các cạnh. Vấn đề nút giao thông có thể đƣợc mô hình hóa bằng
một đồ thị, trong đó các ngã rẽ là các đỉnh, và có một cạnh nối 2 đỉnh biểu thị rằng 2 ngã rẽ đó
không thể đi đồng thời. Khi đó, đồ thị của nút giao thông ở hình 1.1 có thể đƣợc biểu diễn nhƣ ở
hình 1.2.
AB
BA
DA
EA
AC
AD
BD
DC
EC
BC
DB
EB
ED
Hình 1.2 Đồ thị ngã rẽ
4
Ngoài cách biểu diễn trên, đồ thị còn có thể đƣợc biểu diễn thông qua 1 bảng, trong đó phần
tử ở hàng i, cột j có giá trị 1 khi và chỉ khi có 1 cạnh nối đỉnh i và đỉnh j.
AB
AC AD BA
BC BD DA DB
DC EA EB EC ED
1
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Bảng 1.1 Biểu diễn đồ thị ngã rẽ bằng bảng
Ta có thể sử dụng đồ thị trên để giải quyết vấn đề thiết kế hệ thống đèn cho nút giao thông
nhƣ đã nói.
Việc tô màu một đồ thị là việc gán cho mỗi đỉnh của đồ thị một màu sao cho không có hai
đỉnh đƣợc nối bởi 1 cạnh nào đó lại có cùng một màu. Dễ thấy rằng vấn đề nút giao thông có thể
đƣợc chuyển thành bài toán tô màu đồ thị các ngã rẽ ở trên sao cho phải sử dụng số màu ít nhất.
Bài toàn tô màu đồ thị là bài toán đã xuất hiện và đƣợc nghiên cứu từ rất lâu. Tuy nhiên, để
tô màu một đồ thị bất kỳ với số màu ít nhất là bài toán rất phức tạp. Để giải bài toán này, ngƣời ta
thƣờng sử dụng phƣơng pháp “vét cạn” để thử tất cả các khả năng có thể. Có nghĩa, đầu tiên thử
tiến hành tô màu đồ thị bằng 1 màu, tiếp theo dùng 2 màu, 3 màu, v.v. cho tới khi tìm ra phƣơng
pháp tô màu thoả mãn yêu cầu.
Phƣơng pháp vét cạn có vẻ thích hợp với các đồ thị nhỏ, tuy nhiên đối với các đồ thị phức
tạp thì sẽ tiêu tốn rất nhiều thời gian thực hiện cũng nhƣ tài nguyên hệ thống. Ta có thể tiếp cận
vấn đề theo hƣớng cố gắng tìm ra một giải pháp đủ tốt, không nhất thiết phải là giải pháp tối ƣu.
Chẳng hạn, ta sẽ cố gắng tìm một giải pháp tô màu cho đồ thị ngã rẽ ở trên với một số màu khá ít,
gần với số màu ít nhất, và thời gian thực hiện việc tìm giải pháp là khá nhanh. Giải thuật tìm các
giải pháp đủ tốt nhƣng chƣa phải tối ƣu nhƣ vậy gọi là các giải thuật tìm theo “cảm tính”.
Đối với bài toán tô màu đồ thị, một thuật toán cảm tính thƣờng đƣợc sử dụng là thuật toán
“tham ăn” (greedy). Theo thuật toán này, đầu tiên ta sử dụng một màu để tô nhiều nhất số đỉnh có
thể, thoả mãn yêu cầu bài toán. Tiếp theo, sử dụng màu thứ 2 để tô các đỉnh chƣa đƣợc tô trong
bƣớc 1, rồi sử dụng đến màu thứ 3 để tô các đỉnh chƣa đƣợc tô trong bƣớc 2, v.v.
5
Để tô màu các đỉnh với màu mới, chúng ta thực hiện các bƣớc:
-
-
Lựa chọn 1 đỉnh chƣa đƣợc tô màu và tô nó bằng màu mới.
Duyệt qua các đỉnh chƣa đƣợc tô màu. Với mỗi đỉnh dạng này, kiểm tra xem có cạnh
nào nối nó với một đỉnh vừa đƣợc tô bởi màu mới hay không. Nếu không có cạnh nào
thì ta tô màu đỉnh này bằng màu mới.
Thuật toán này đƣợc gọi là “tham ăn” vì tại mỗi bƣớc nó tô màu tất cả các đỉnh có thể mà
không cần phải xem xét xem việc tô màu đó có để lại những điểm bất lợi cho các bƣớc sau hay
không. Trong nhiều trƣờng hợp, chúng ta có thể tô màu đƣợc nhiều đỉnh hơn bằng 1 màu nếu
chúng ta bớt “tham ăn” và bỏ qua một số đỉnh có thể tô màu đƣợc trong bƣớc trƣớc.
Ví dụ, xem xét đồ thị ở hình 1.3, trong đó đỉnh 1 đã đƣợc tô màu đỏ. Ta thấy rằng hoàn toàn
có thể tô cả 2 đỉnh 3 và 4 là màu đỏ, với điều kiện ta không tô đỉnh số 2 màu đỏ. Tuy nhiên, nếu ta
áp dụng thuật toán tham ăn theo thứ tự các đỉnh lớn dần thì đỉnh 1 và đỉnh 2 sẽ là màu đỏ, và khi
đó đỉnh 3, 4 sẽ không đƣợc tô màu đỏ.
3
a) Đồ thị ban đầu
2
1
5
4
3
b) Tô màu theo thuật toán tham ăn
c) Một cách tô màu tốt hơn
2
1
1
5
5
4
3
2
4
Hình 1.3 Đồ thị
Bây giờ ta sẽ xem xét thuật toán tham ăn đƣợc áp dụng trên đồ thị các ngã rẽ ở hình 1.2 nhƣ
thế nào. Giả sử ta bắt đầu từ đỉnh AB và tô cho đỉnh này màu xanh. Khi đó, ta có thể tô cho đỉnh
AC màu xanh vì không có cạnh nối đỉnh này với AB. AD cũng có thể tô màu xanh vì không có
cạnh nối AD với AB, AC. Đỉnh BA không có cạnh nối tới AB, AC, AD nên cũng có thể đƣợc tô
màu xanh. Tuy nhiên, đỉnh BC không tô đƣợc màu xanh vì tồn tại cạnh nối BC và AB. Tƣơng tự
nhƣ vậy, BD, DA, DB không thể tô màu xanh vì tồn tại cạnh nối chúng tới một trong các đỉnh đã
tô màu xanh. Cạnh DC thì có thể tô màu xanh. Cuối cùng, cạnh EA, EB, EC cũng không thể tô
màu xanh trong khi ED có thể đƣợc tô màu xanh.
6
AB
BA
DA
EA
AC
BC
DB
EB
AD
BD
DC
EC
ED
Hình 1.4 Tô màu xanh cho các đỉnh của đồ thị ngã rẽ
Tiếp theo, ta sử dụng màu đỏ để tô các đỉnh chƣa đƣợc tô màu ở bƣớc trƣớc. Đầu tiên là
BC. BD cũng có thể tô màu đỏ, tuy nhiên do tồn tại cạnh nối DA với BD nên DA không đƣợc tô
màu đỏ. Tƣơng tự nhƣ vậy, DB không tô đƣợc màu đỏ còn EA có thể tô màu đỏ. Các đỉnh chƣa
đƣợc tô màu còn lại đều có cạnh nối tới các đỉnh đã tô màu đỏ nên cũng không đƣợc tô màu.
AB
BA
DA
EA
AC
BC
DB
EB
AD
BD
DC
EC
ED
Hình 1.5 Tô màu đỏ trong bƣớc 2
Bƣớc 3, các đỉnh chƣa đƣợc tô màu còn lại là DA, DB, EB, EC. Nếu ta tô màu đỉnh DA là
màu lục thì DB cũng có thể tô màu lục. Khi đó, EB, EC không thể tô màu lục và ta chọn 1 màu
thứ tƣ là màu vàng cho 2 đỉnh này.
7
AB
BA
DA
EA
AC
BC
DB
EB
AD
BD
DC
EC
ED
Hình 1.6 Tô màu lục và màu vàng cho các đỉnh còn lại
Nhƣ vậy, ta có thể dùng 4 màu xanh, đỏ, lục, vàng để tô màu cho đồ thị ngã rẽ ở hình 1.2
theo yêu cầu nhƣ đã nói ở trên. Bảng tổng hợp màu đƣợc mô tả nhƣ sau:
Màu
Xanh
Ngã rẽ
AB, AC, AD, BA, DC, ED
BC, BD, EA
Đỏ
Lục
Vàng
DA, DB
EB, EC
Bảng 1.2 Bảng tổng hợp màu
Thuật toán tham ăn không đảm bảo cho ra kết quả tối ƣu là số màu ít nhất đƣợc dùng. Tuy
nhiên, ngƣời ta có thể dùng một số tính chất của đồ thị để đánh giá kết quả thu đƣợc.
Trở lại với vấn đề nút giao thông, từ kết quả tô màu trên, ta có thể thiết kế hệ thống đèn
giao thông theo bảng tổng hợp màu trên, trong đó mỗi trạng thái của hệ thống đèn tƣơng ứng với
1 màu. Tại mỗi trạng thái, các ngã rẽ nằm tại hàng tƣơng ứng với màu đó đƣợc cho phép đi, các
ngã rẽ còn lại bị cấm.
1.1.2 Ngôn ngữ diễn đạt giải thuật và kỹ thuật tinh chỉnh từng bƣớc
Sau khi đã xây dựng đƣợc mô hình toán học cho vấn đề cần giải quyết, tiếp theo, ta có thể
hình thành một thuật toán cho mô hình đó. Phiên bản đầu tiên của thuật toán thƣờng đƣợc diễn tả
dƣới dạng các phát biểu tƣơng đối tổng quát, và sau đó sẽ đƣợc tinh chỉnh dần từng bƣớc thành
chuỗi các lệnh cụ thể, rõ ràng hơn. Ví dụ trong thuật toán tham ăn ở trên, ta mô tả bƣớc thực hiện
ở mức tổng quát là “Lựa chọn 1 đỉnh chƣa đƣợc tô màu”. Với phát biểu nhƣ vậy, ta hy vọng rằng
ngƣời đọc có thể nắm đƣợc ý tƣởng thực hiện thao tác. Tuy nhiên, để chuyển các phát biểu đó
8
thành chƣơng trình máy tính, cần phải qua 1 số bƣớc tinh chỉnh cho tới khi đạt đến mức các phát
biểu đều có thể đƣợc chuyển đổi trực tiếp sang các lệnh của ngôn ngữ lập trình.
Trở lại ví dụ về bài toán tô màu đồ thị bằng thuật toán tham ăn. Ta sẽ xem xét việc mô tả
thuật toán từ mức tổng quát cho tới một số mức cụ thể hơn. Tại bƣớc nào đó, giả sử ta có đồ thị G
có 1 số đỉnh đã đƣợc tô màu theo quy tắc đã nói ở trên. Thủ tục Tham_an dƣới đây sẽ xác định 1
tập các đỉnh chƣa đƣợc tô màu thuộc G mà có thể cùng đƣợc tô bởi 1 màu mới. Thủ tục này sẽ
đƣợc gọi đi gọi lại nhiều lần cho tới khi tất cả các đỉnh của G đã đƣợc tô màu. Ở mức tổng quát,
thủ tục đƣợc mô tả nhƣ sau:
void Tham_an(GRAPH:G, SET: Mau_moi)
{
Mau_moi = Tập rỗng;
For mỗi
đỉnh v chƣa
If v không
đƣợc tô màu thuộc G
đƣợc nối tới đỉnh nào trong tập Mau_moi
{
}
Tô màu mới cho đỉnh v;
Đƣa v vào tập Mau_moi;
}
Trong thủ tục trên, ta sử dụng một ngôn ngữ diễn đạt giải thuật tựa nhƣ ngôn ngữ lập trình
C. Trong ngôn ngữ này, các lệnh đƣợc mô tả dƣới dạng ngôn ngữ tự nhiên nhƣng vẫn tuân theo cú
pháp của ngôn ngữ lập trình.
Ta nhận thấy rằng các phát biểu trong thủ tục trên còn rất tổng quát, và chƣa tƣơng ứng với
các lệnh trong ngôn ngữ lập trình, chẳng hạn các điều kiện kiểm tra trong câu lệnh For và If ở
mức mô tả hiện tại là không thực hiện đƣợc trong C. Để thủ tục có thể thực thi đƣợc, ta cần phải
tinh chỉnh một số bƣớc để có thể chuyển đổi về chƣơng trình trong ngôn ngữ lập trình C thông
thƣờng.
Đầu tiên, ta xem xét lệnh If ở trên. Để kiểm tra xem đỉnh v có nối tới một đỉnh nào đó trong
tập Mau_moi hay không, ta xem xét từng đỉnh w trong Mau_moi và sử dụng đồ thị G để kiểm tra
xem có tồn tại cạnh nối v à w không. Để lƣu giữ kết quả kiểm tra, ta sử dụng một biến ton_tai.
Khi đó, thủ tục đƣợc tinh chỉnh nhƣ sau:
void Tham_an(GRAPH:G, SET: Mau_moi)
{
int ton_tai;
Mau_moi = Tập rỗng;
For mỗi
đỉnh v chƣa
đƣợc tô màu thuộc G
{
ton_tai = 0;
For mỗi
đỉnh w thuộc Mau_moi
If tồn tại cạnh nối v và w trong G
ton_tai = 1;
If ton_tai = = 1
{
9
Tô màu mới cho đỉnh v;
Đƣa v vào tập Mau_moi;
}
}
}
Nhƣ vậy, ta có thể thấy rằng điều kiện kiểm tra trong phát biểu If đã đƣợc mô tả cụ thể hơn
bằng các phát nhỏ hơn,và các phát biểu này có thể dễ dàng chuyển thành các lệnh cụ thể trong C.
Tiếp theo, ta sẽ tinh chỉnh các vòng lặp For để duyệt qua các đỉnh thuộc G và thuộc Mau_moi. Để
làm điều này, tốt nhất là ta thay For bằng một vòng lặp While, biến v ban đầu đƣợc gán là phần tử
đầu tiên chƣa tô màu trong tập G, và tại mỗi bƣớc lặp, biến v sẽ đƣợc thay bằng phần tử chƣa tô
màu tiếp theo trong G. Vòng lặp F bên trong có thể thực hiện tƣơng tự.
Void Tham_an(GRAPH:G, SET: Mau_moi)
{
int ton_tai;
int v, w
Mau_moi = Tập rỗng;
v = đỉnh chƣa tô màu
While v != NULL
{
đầu tiên trong G ;
ton_tai = 0;
w = đỉnh đầu tiên trong Mau_moi;
While w != NULL{
If tồn tại cạnh nối v và w trong G
ton_tai = 1;
w = đỉnh tiếp theo trong Mau_moi ;
}
If ton_tai = = 1
{
Tô màu mới cho đỉnh v;
Đƣa v vào tập Mau_moi;
}
v = đỉnh chƣa tô màu tiếp theo trong G;
}
}
Nhƣ vậy, ta thấy các phát biểu trong thủ tục đã khá cụ thể, tuy nhiên, để chuyển đổi thành
chƣơng trình trong ngôn ngữ C thì cần tới vài bƣớc tinh chỉnh nữa. Bạn đọc hãy xem nhƣ đó là
bài tập và tự giải để hiểu rõ về ngôn ngữ diễn đạt giải thuật cũng nhƣ kỹ thuật tinh chỉnh từng
bƣớc.
1.2 PHÂN TÍCH THUẬT TOÁN
Với mỗi vấn đề cần giải quyết, ta có thể tìm ra nhiều thuật toán khác nhau. Có những thuật
toán thiết kế đơn giản, dễ hiểu, dễ lập trình và sửa lỗi, tuy nhiên thời gian thực hiện lớn và tiêu tốn
10
nhiều tài nguyên máy tính. Ngƣợc lại, có những thuật toán thiết kế và lập trình rất phức tạp,
nhƣng cho thời gian chạy nhanh hơn, sử dụng tài nguyên máy tính hiệu quả hơn. Khi đó, câu hỏi
đặt ra là ta nên lựa chọn giải thuật nào để thực hiện?
Đối với những chƣơng trình chỉ đƣợc thực hiện một vài lần thì thời gian chạy không phải là
tiêu chí quan trọng nhất. Đối với bài toán kiểu này, thời gian để lập trình viên xây dựng và hoàn
thiện thuật toán đáng giá hơn thời gian chạy của chƣơng trình và nhƣ vậy những giải thuật đơn
giản về mặt thiết kế và xây dựng nên đƣợc lựa chọn.
Đối với những chƣơng trình đƣợc thực hiện nhiều lần thì thời gian chạy của chƣơng trình
đáng giá hơn rất nhiều so với thời gian đƣợc sử dụng để thiết kế và xây dựng nó. Khi đó, lựa chọn
một giải thuật có thời gian chạy nhanh hơn (cho dù việc thiết kế và xây dựng phức tạp hơn) là một
lựa chọn cần thiết. Trong thực tế, trong giai đoạn đầu của việc giải quyết vấn đề, một giải thuật
đơn giản thƣờng đƣợc thực hiện trƣớc nhƣ là 1 nguyên mẫu (prototype), sau đó nó sẽ đƣợc phân
tích, đánh giá, và cải tiến thành các phiên bản tốt hơn.
1.2.1 Ƣớc lƣợng thời gian thực hiện chƣơng trình
Thời gian chạy của 1 chƣơng trình phụ thuộc vào các yếu tố sau:
-
Dữ liệu đầu vào
-
-
-
Chất lƣợng của mã máy đƣợc tạo ra bởi chƣơng trình dịch
Tốc độ thực thi lệnh của máy
Độ phức tạp về thời gian của thuật toán
Thông thƣờng, thời gian chạy của chƣơng trình không phụ thuộc vào giá trị dữ liệu đầu vào
mà phụ thuộc vào kích thƣớc của dữ liệu đầu vào. Do vậy thời gian chạy của chƣơng trình nên
đƣợc định nghĩa nhƣ là một hàm có tham số là kích thƣớc dữ liệu đầu vào. Giả sử T là hàm ƣớc
lƣợng thời gian chạy của chƣơng trình, khi đó với dữ liệu đầu vào có kích thƣớc n thì thời gian
chạy của chƣơng trình là T(n). Ví dụ, đối với một số chƣơng trình thì thời gian chạy là an hoặc
2
an, trong đó a là hằng số. Đơn vị của hàm T(n) là không xác định, tuy nhiên ta có thể xem nhƣ
T(n) là tổng số lệnh đƣợc thực hiện trên 1 máy tính lý tƣởng.
Trong nhiều chƣơng trình, thời gian thực hiện không chỉ phụ thuộc vào kích thƣớc dữ liệu
vào mà còn phụ thuộc vào tính chất của nó. Khi tính chất dữ liệu vào thoả mãn một số đặc điểm
nào đó thì thời gian thực hiện chƣơng trình có thể là lớn nhất hoặc nhỏ nhất. Khi đó, ta định nghĩa
thời gian thực hiện chƣơng trình T(n) trong trƣờng hợp xấu nhất hoặc tốt nhất. Đó là thời gian
thực hiện lớn nhất hoặc nhỏ nhất trong tất cả các bộ dữ liệu vào có kích thƣớc n. Ta cũng định
nghĩa thời gian thực hiện trung bình của chƣơng trình trên mọi bộ dữ liệu vào kích thƣớc n. Trong
thực tế, ƣớc lƣợng thời gian thực hiện trung bình khó hơn nhiều so với thời gian thực hiện trong
trƣờng hợp xấu nhất hoặc tốt nhất, bởi vì việc phân tích thuật toán trong trƣờng hợp trung bình
khó hơn về mặt toán học, đồng thời khái niệm “trung bình” không có ý nghĩa thực sự rõ ràng.
Yếu tố chất lƣợng của mã máy đƣợc tạo bởi chƣơng trình dịch và tốc độ thực thi lệnh của
máy cũng ảnh hƣởng tới thời gian thực hiện chƣơng trình cho thấy chúng ta không thể thể hiện
thời gian thực hiện chuơng trình dƣới đơn vị thời gian chuẩn, chẳng hạn phút hoặc giây. Thay vào
2
đó, ta có thể phát biểu thời gian thực hiện chƣơng trình tỷ lệ với n hoặc n v.v. Hệ số của tỷ lệ là 1
hằng số chƣa xác định, phụ thuộc vào máy tính, chƣơng trình dịch, và các nhân tố khác.
Ký hiệu O(n)
Để biểu thị cấp độ tăng của hàm, ta sử dụng ký hiệu O(n). Ví dụ, ta nói thời gian thực hiện
2
2
T(n) của chƣơng trình là O(n), có nghĩa là tồn tại các hằng số duơng c và n
0
sao cho T(n) ≤ cn
với n ≥ n0.
11
2
2
Ví dụ, xét hàm T(n) = (n+1)
.
Ta có thể thấy T(n) là O(n) với n = 1 và c = 4, vì ta có T(n)
0
2
2
3
= (n+1) < 4n với mọi n ≥ 1. Trong ví dụ này, ta cũng có thể nói rằng T(n) là O(n ), tuy nhiên,
2
phát biểu này “yếu” hơn phát biểu T(n) là O(n).
Nhìn chung, ta nói T(n) là O(f(n)) nếu tồn tại các hằng số dƣơng c và n0sao cho T(n) <
c.f(n) với n ≥ n
0
. Một chƣơng trình có thời gian thực hiện là O(f(n)) thì đƣợc xem là có cấp độ
tăng f(n).
Việc đánh giá các chƣơng trình có thể đƣợc thực hiện qua việc đánh giá các hàm thời gian
chạy của chƣơng trình,bỏ qua các hằng số tỷ lệ. Với giả thiết này, một chƣơng trình với thời gian
2
3
thực hiện là O(n) sẽ tốt hơn chƣơng trình với thời gian chạy O(n). Bên cạnh các yếu tố hằng số
xuất phát từ chƣơng trình dịch và máy, còn có thêm hằng số từ bản thân chuơng trình. Ví dụ, trên
2
cùng một chƣơng trình dịch và cùng 1 máy, chƣơng trình đầu tiên có thời gian thực hiện là 100n,
3
3
2
trong khi chuơng trình thứ 2 có thời gian thực hiện là 5n. Với n nhỏ, có thể 5n nhỏ hơn 100n,
3
2
tuy nhiên với n đủ lớn thì 5n sẽ lớn hơn 100nđáng kể.
Một lý do nữa để xem xét cấp độ tăng về thời gian thực hiện của chƣơng trình là nó cho
phép ta xác định độ lớn của bài toán mà ta có thể giải quyết. Mặc dù máy tính có tốc độ ngày càng
2
cao, tuy nhiên, với những chƣơng trình có thời gian thực hiện có cấp độ tăng lớn (từ n trở lên),
thì việc tăng tốc độ của máy tính tạo ra sự khác biệt không đáng kể về kích thƣớc bài toán có thể
xử lý bởi máy tính trong một khoảng thời gian cố định.
1.2.2 Tính toán thời gian thực hiện chƣơng trình
Để tính toán đƣợc thời gian thực hiện chƣơng trình, ta cần chú ý một số nguyên tắc cộng và
nhân cấp độ tăng của hàm nhƣ sau :
Giả sử T1(n) và T2(n) là thời gian chạy của 2 đoạn chƣơng trình P1 và P2, trong đó T1(n) là
O(f(n)) và T2(n) là O(g(n)). Khi đó, thời gian thực hiện của 2 đoạn chƣơng trình trình nối tiếp P1,
P
2
là O(max(f(n), g(n))).
Nguyên tắc cộng trên có thể sử dụng để tính thời gian thực hiện của chƣơng trình bao gồm
1 số tuần tự các bƣớc, mỗi bƣớc có thể là 1 đoạn chƣơng trình bao gồm 1 số vòng lặp và rẽ nhánh.
2
3
Ví dụ, giả sử ta có 3 bƣớc thực hiện chƣơng trình lần lƣợt có thời gian chạy là O(n), O(n),
2
3
3
O(nlog n). Khi đó, thời gian chạy của 2 đoạn chƣơng trình đầu là O(max(n, n)) = O(n), còn thời
3
3
gian chạy của cả 3 đoạn chƣơng trình là O(max(n, nlog n)) = O(n).
Nguyên tắc nhân cấp độ tăng của hàm nhƣ sau: Với giả thiết về T
1
(n) và T (n) nhƣ trên, nếu
2
2 đoạn chƣơng trình P1 và P2 không đƣợc thực hiện tuần tự mà lồng nhau thì thời gian chạy tổng
thể sẽ là T1(n).T2(n) = O(f(n).(g(n)).
Để minh hoạ cho việc phân tích và tính toán thời gian thực hiện của 1 chƣơng trình, ta sẽ
xem xét một thuật toán đơn gian để sắp xếp các phần tử của một tập hợp, đó là thuật toán sắp xếp
nổi bọt (bubble sort).
Thuật toán nhƣ sau :
void buble (int a[n]){
int i, j, temp;
1.
2.
3.
for (i = 0; i < n-1; i++)
for (j = n-1; j>= i+1; j--)
if (a[j-1] > a[j]{
// Đổi chỗ cho a[j] và a[j-1]
temp = a[j-1];
4.
5.
a[j-1] = a[j];
12
6.
}
a[j] = temp;
}
Trong thuật toán này, mỗi lần duyệt của vòng lặp trong (biến duyệt j) sẽ làm “nổi” lên trên
phần tử nhỏ nhất trong các phần tử đƣợc duyệt.
Dễ thấy rằng kích thƣớc dữ liệu vào chính là số phần tử đƣợc sắp, n. Mỗi lệnh gán sẽ có
thời gian thực hiện cố định, không phụ thuộc vào n, do vậy, các lệnh 4, 5, 6 sẽ có thời gian thực
hiện là O(1), tức thời gian thực hiện là hằng số. Theo quy tắc cộng cấp độ tăng thì tổng thời gian
thực hiện cả 3 lệnh là O(max(1, 1, 1)) = O(1).
Tiếp theo ta sẽ xem xét thời gian thực hiện của các lệnh lặp và rẽ nhánh. Lệnh If kiểm tra
điều kiện để thực hiện nhóm lệnh gán 4, 5, 6. Việc kiểm tra điều kiện sẽ có thời gian thực hiện là
O(1). Ngoài ra, chúng ta chƣa biết đƣợc là điều kiện có thoả mãn hay không, tức là không biết
đƣợc nhóm lệnh gán có đƣợc thực hiện hay không. Do vậy, ta giả thiết trƣờng hợp xấu nhất là tất
cả các lần kiểm tra điều kiện đều thoả mãn, và các lệnh gán đƣợc thực hiện. Nhƣ vậy, toàn bộ lệnh
If sẽ có thời gian thực hiện là O(1).
Tiếp tục xét từ trong ra ngoài, ta xét đến vòng lặp trong (biến duyệt j). Trong vòng lặp này,
tại mỗi bƣớc lặp ta cần thực hiện các thao tác nhƣ kiểm tra đã gặp điều kiện dừng chƣa và tăng
biến duyệt lên 1 nếu chƣa dừng. Nhƣ vậy, mỗi bƣớc lặp có thời gian thực hiện là O(1). Số bƣớc
lặp là n-i, do đó theo quy tắc nhân cấp độ tăng thì tổng thời gian thực hiện của vòng lặp này là
O((n-i)x1) = O(n-i).
Cuối cùng, ta xét vòng lặp ngoài cùng (biến duyệt i). Vòng lặp này đƣợc thực hiện (n-1) lần,
do đó, tổng thời gian thực hiện của chƣơng trình là:
2
2
∑ (n-i) = n(n-1)/2 = n/2- n/2 = O(n)
2
Nhƣ vậy, thời gian thực hiện giải thuật sắp xếp nổi bọt là tỷ lệ với n.
Một số quy tắc chung trong việc phân tích và tính toán thời gian thực hiện chƣơng trình
-
-
Thời gian thực hiện các lệnh gán, đọc, ghi .v.v, luôn là O(1).
Thời gian thực hiện chuỗi tuần tự các lệnh đƣợc xác định theo quy tắc cộng cấp độ tăng.
Có nghĩa là thời gian thực hiện của cả nhóm lệnh tuần tự đƣợc tính là thời gian thực
hiện của lệnh lớn nhất.
-
-
Thời gian thực hiện lệnh rẽ nhánh If đƣợc tính bằng thời gian thực hiện các lệnh khi
điều kiện kiểm tra đƣợc thoả mãn và thời gian thực hiện việc kiểm tra điều kiện. Thời
gian thực hiện việc kiểm tra điều kiện luôn là O(1).
Thời gian thực hiện 1 vòng lặp đƣợc tính là tổng thời gian thực hiện các lệnh ở thân
vòng lặp qua tất cả các bƣớc lặp và thời gian để kiểm tra điều kiện dừng (thƣờng là
O(1)). Thời gian thực hiện này thƣờng đƣợc tính theo quy tắc nhân cấp độ tăng số lần
thực hiện bƣớc lặp và thời gian thực hiện các lệnh ở thân vòng lặp. Các vòng lặp phải
đƣợc tính thời gian thực hiện một cách riêng rẽ.
1.3 TÓM TẮT CHƢƠNG 1
Các kiến thức cần nhớ trong chƣơng 1:
-
Thuật toán là một chuỗi hữu hạn các lệnh. Mỗi lệnh có một ngữ nghĩa rõ ràng và có thể
đƣợc thực hiện với một lƣợng hữu hạn tài nguyên trong một khoảng hữu hạn thời gian.
13
-
-
-
-
Thuật toán thƣờng đƣợc mô tả bằng các ngôn ngữ diễn đạt giải thuật gần với ngôn ngữ
tự nhiên. Các mô tả này sẽ đƣợc tỉnh chỉnh dần dần để đạt tới mức ngôn ngữ lập trình.
Thời gian thực hiện thuật toán thƣờng đƣợc coinhƣ là 1 hàm của kích thƣớc dữ liệu đầu
vào.
Thời gian thực hiện thuật toán thƣờng đƣợc tính trong các trƣờng hợp tốt nhất, xấu nhất,
hoặc trung bình.
Để biểu thị cấp độ tăng của hàm, ta sử dụng ký hiệu O(n). Ví dụ, ta nói thời gian thực
2
hiện T(n) của chƣơng trình là O(n), có nghĩa là tồn tại các hằng số duơng c và n0 sao
2
cho T(n) ≤ cn với n ≥ n.
0
-
-
Cấp độ tăng về thời gian thực hiện của chƣơng trình cho phép ta xác định độ lớn của bài
toán mà ta có thể giải quyết.
Quy tắc cộng cấp độ tăng: Giả sử T1(n) và T2(n) là thời gian chạy của 2 đoạn chƣơng
trình P1 và P2, trong đó T1(n) là O(f(n)) và T2(n) là O(g(n)). Khi đó, thời gian thực hiện
của 2 đoạn chƣơng trình trình nối tiếp P1, P2 là O(max(f(n), g(n))).
-
Quy tắc nhân cấp độ tăng: Với giả thiết về T1(n) và T2(n) nhƣ trên, nếu 2 đoạn chƣơng
trình P1 và P2 không đƣợc thực hiện tuần tự mà lồng nhau thì thời gian chạy tổng thể sẽ
là T1(n).T2(n) = O(f(n).(g(n)).
1.4 CÂU HỎI VÀ BÀI TẬP
1. Trình bày khái niệm thuật toán? Các đặc điểm của thuật toán?
2. Trong một giải vô địch bóng đá có 6 đội bóng đá vòng tròn. Các đội là A, B, C, D, E, F.
Đội A đã đá với B và C. Đội B đã đá với D và F. Đội E đã đá với C và F. Mỗi đội đá
mỗi tuần 1 trận. Hãy lập 1 lịch cho các đội bóng sao cho tất cả các đội đều đá đủ số trận
quy định trong 1 số tuần vừa phải. Thực hiện phân tích, thiết kế thuật toán. Biểu diễn
thuật toán bằng ngôn ngữ diễn đạt giải thuật, sau đó tinh chỉnh về dạng ngôn ngữ lập
trình C.
3. Thời gian thực hiện một chƣơng trình thƣờng phụ thuộc vào các yếu tố nào? Phân tích
cụ thể từng yếu tố.
4. Nói thời gian thực hiện chƣơng trình là T(n) = O(f(n)) có nghĩa là gì? Cho ví dụ minh
hoạ.
5. Nêu quy tắc cộng và nhân cấp độ tăng của hàm. Có ví dụ minh hoạ.
6. Nêu các quy tắc chung trong việc phân tích và đánh giá thời gian thực hiện chƣơng
trình.
14
CHƢƠNG 2
ĐỆ QUI
Chƣơng 2 trình bày các khái niệm về định nghĩa đệ qui, chƣơng trình đệ qui. Ngoài việc
trình bày các ƣu điểm của chƣơng trình đệ qui, các tình huống không nên sử dụng đệ qui cũng
đƣợc đề cập cùng với các ví dụ minh hoạ.
Chƣơng này cũng đề cập và phân tích một số thuật toán đệ qui tiêu biểu và kinh điển nhƣ
bài toán tháp Hà nội, các thuật toán quay lui .v.v
Để học tốt chƣơng này, sinh viên cần nắm vững phần lý thuyết. Sau đó, nghiên cứu kỹ các
phân tích thuật toán và thực hiện chạy thử chƣơng trình. Có thể thay đổi một số điểm trong
chƣơng trình và chạy thử để nắm kỹ hơn về thuật toán. Ngoài ra, sinh viên cũng có thể tìm các bài
toán tƣơng tự để phân tích và giải quyết bằng chƣơng trình.
2.1 KHÁI NIỆM
Đệ qui là một khái niệm cơ bản trong toán học và khoa học máy tính. Một đối tƣợng đƣợc
gọi là đệ qui nếu nó hoặc một phần của nó đƣợc định nghĩa thông qua khái niệm về chính nó. Một
số ví dụ điển hình về việc định nghĩa bằng đệ qui là:
1- Định nghĩa số tự nhiên:
- 0 là số tự nhiên.
- Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên.
Nhƣ vậy, bắt đầu từ phát biểu “0 là số tự nhiên”, ta suy ra 0+1=1 là số tự nhiên. Tiếp
theo 1+1=2 là số tự nhiên, v.v.
2- Định nghĩa xâu ký tự bằng đệ qui:
- Xâu rỗng là 1 xâu ký tự.
- Một chữ cái bất kỳ ghép với 1 xâu sẽ tạo thành 1 xâu mới.
Từ phát biểu “Xâu rỗng là 1 xâu ký tự”, ta ghép bất kỳ 1 chữ cái nào với xâu rỗng đều
tạo thành xâu ký tự. Nhƣ vậy, chữ cái bất kỳ có thể coi là xâu ký tự. Tiếp tục ghép 1 chữ
cái bất kỳ với 1 chữ cái bất kỳ cũng tạo thành 1 xâu ký tự, v.v.
3- Định nghĩa hàm giai thừa, n!.
- Khi n=0, định nghĩa 0!=1
- Khi n>0, định nghĩa n!=(n-1)! x n
Nhƣ vậy, khi n=1, ta có 1!=0!x1 = 1x1=1. Khi n=2, ta có 2!=1!x2=1x2=2, v.v.
Trong lĩnh vực lập trình, một chƣơng trình máy tính gọi là đệ qui nếu trong chƣơng trình có
lời gọi chính nó. Điều này, thoạt tiên, nghe có vẻ hơi vô lý. Một chƣơng trình không thể gọi mãi
chính nó, vì nhƣ vậy sẽ tạo ra một vòng lặp vô hạn. Trên thực tế, một chƣơng trình đệ qui trƣớc
khi gọi chính nó bao giờ cũng có một thao tác kiểm tra điều kiện dừng. Nếu điều kiện dừng thỏa
mãn, chƣơng trình sẽ không gọi chính nó nữa, và quá trình đệ qui chấm dứt. Trong các ví dụ ở
trên, ta đều thấy có các điểm dừng. Chẳng hạn, trong ví dụ thứ nhất, nếu k = 0 thì có thể suy ngay
k là số tự nhiên, không cần tham chiếu xem k-1 có là số tự nhiên hay không.
Nhìn chung, các chƣơng trình đệ qui đều có các đặc điểm sau:
15
-
-
Chƣơng trình này có thể gọi chính nó.
Khi chƣơng trình gọi chính nó, mục đích là để giải quyết 1 vấn đề tƣơng tự, nhƣng nhỏ
hơn.
-
Vấn đề nhỏ hơn này, cho tới 1 lúc nào đó, sẽ đơn giản tới mức chƣơng trình có thể tự
giải quyết đƣợc mà không cần gọi tới chính nó nữa.
Khi chƣơng trình gọi tới chính nó, các tham số, hoặc khoảng tham số, thƣờng trở nên nhỏ
hơn, để phản ánh 1 thực tế là vấn đề đã trở nên nhỏ hơn, dễ hơn. Khi tham số giảm tới mức cực
tiểu, một điều kiện so sánh đƣợc kiểm tra và chƣơng trình kết thúc, chấm dứt việc gọi tới chính
nó.
Ƣu điểm của chƣơng trình đệ qui cũng nhƣ định nghĩa bằng đệ qui là có thể thực hiện một
số lƣợng lớn các thao tác tính toán thông qua 1 đoạn chƣơng trình ngắn gọn (thậm chí không có
vòng lặp, hoặc không tƣờng minh để có thể thực hiện bằng các vòng lặp) hay có thể định nghĩa
một tập hợp vô hạn các đối tƣợng thông qua một số hữu hạn lời phát biểu. Thông thƣờng, một
chƣơng trình đƣợc viết dƣới dạng đệ qui khi vấn đề cần xử lý có thể đƣợc giải quyết bằng đệ qui.
Tức là vấn đề cần giải quyết có thể đƣa đƣợc về vấn đề tƣơng tự, nhƣng đơn giản hơn. Vấn đề này
lại đƣợc đƣa về vấn đề tƣơng tự nhƣng đơn giản hơn nữa .v.v, cho đến khi đơn giản tới mức có
thể trực tiếp giải quyết đƣợc ngay mà không cần đƣa về vấn đề đơn giản hơn nữa.
2.1.1 Điều kiện để có thể viết một chƣơng trình đệ qui
Nhƣ đã nói ở trên, để chƣơng trình có thể viết dƣới dạng đệ qui thì vấn đề cần xử lý phải
đƣợc giải quyết 1 cách đệ qui. Ngoài ra, ngôn ngữ dùng để viết chƣơng trình phải hỗ trợ đệ qui.
Để có thể viết chƣơng trình đệ qui chỉ cần sử dụng ngôn ngữ lập trình có hỗ trợ hàm hoặc thủ tục,
nhờ đó một thủ tục hoặc hàm có thể có lời gọi đến chính thủ tục hoặc hàm đó. Các ngôn ngữ lập
trình thông dụng hiện nay đều hỗ trợ kỹ thuật này, do vậy vấn đề công cụ để tạo các chƣơng trình
đệ qui không phải là vấn đề cần phải xem xét. Tuy nhiên, cũng nên lƣu ý rằng khi một thủ tục đệ
qui gọi đến chính nó, một bản sao của tập các đối tƣợng đƣợc sử dụng trong thủ tục này nhƣ các
biến, hằng, các thủ tục con, .v.v. cũng đƣợc tạo ra. Do vậy, nên hạn chế việc khai báo và sử dụng
các đối tƣợng này trong thủ tục đệ qui nếu không cần thiết nhằm tránh lãng phí bộ nhớ, đặc biệt
đối với các lời gọi đệ qui đƣợc gọi đi gọi lại nhiều lần. Các đối tƣợng cục bộ của 1 thủ tục đệ qui
khi đƣợc tạo ra nhiều lần, mặc dù có cùng tên, nhƣng do khác phạm vi nên không ảnh hƣởng gì
đến chƣơng trình. Các đối tƣợng đó sẽ đƣợc giải phóng khi thủ tục chứa nó kết thúc.
Nếu trong một thủ tục có lời gọi đến chính nó thì ta gọi đó là đệ qui trực tiếp. Còn trong
trƣờng hợp một thủ tục có một lời gọi thủ tục khác, thủ tục này lại gọi đến thủ tục ban đầu thì
đƣợc gọi là đệ qui gián tiếp. Nhƣ vậy, trong chƣơng trình khi nhìn vào có thể không thấy ngay sự
đệ qui, nhƣng khi xem xét kỹ hơn thì sẽ nhận ra.
2.1.2 Khi nào không nên sử dụng đệ qui
Trong nhiều trƣờng hợp, một chƣơng trình có thể viết dƣới dạng đệ qui. Tuy nhiên, đệ qui
không hẳn đã là giải pháp tốt nhất cho vấn đề. Nhìn chung, khi chƣơng trình có thể viết dƣới dạng
lặp hoặc các cấu trúc lệnh khác thì không nên sử dụng đệ qui.
Lý do thứ nhất là, nhƣ đã nói ở trên, khi một thủ tục đệ qui gọi chính nó, tập các đối tƣợng
đƣợc sử dụng trong thủ tục này nhƣ các biến, hằng, cấu trúc .v.v sẽ đƣợc tạo ra. Ngoài ra, việc
chuyển giao điều khiển từ các thủ tục cũng cần lƣu trữ các thông số dùng cho việc trả lại điều
khiển cho thủ tục ban đầu.
Lý do thứ hai là việc sử dụng đệ qui đôi khi tạo ra các tính toán thừa, không cần thiết do
tính chất tự động gọi thực hiện thủ tục khi chƣa gặp điều kiện dừng của đệ qui. Để minh họa cho
16
điều này, chúng ta sẽ xem xét một ví dụ, trong đó cả đệ qui và lặp đều có thể đƣợc sử dụng. Tuy
nhiên, ta sẽ phân tích để thấy sử dụng đệ qui trong trƣờng hợp này gây lãng phí bộ nhớ và các tính
toán không cần thiết nhƣ thế nào.
Xét bài toán tính các phần tử của dãy Fibonaci. Dãy Fibonaci đuợc định nghĩa nhƣ sau:
-
-
F(0) = 0
F(1) =1
-
Với n >1 thì F(n) = F(n-1) + F(n-2)
Rõ ràng là nhìn vào một định nghĩa đệ qui nhƣ trên, chƣơng trình tính phần tử của dãy
Fibonaci có vẻ nhƣ rất phù hợp với thuật toán đệ qui. Phƣơng thức đệ qui để tính dãy này có thể
đƣợc viết nhƣ sau:
int Fibonaci(int i){
if (i==0) return 0;
if (i==1) return 1;
return Fibonaci(i-1) + Fibonaci (i-2)
}
Kết quả thực hiện chƣơng trình không có gì sai. Tuy nhiên, chú ý rằng một lời gọi đệ qui
Fibonaci (n) sẽ dẫn tới 2 lời gọi đệ qui khác ứng với n-1 và n-2. Hai lời gọi này lại gây ra 4 lời gọi
nữa .v.v, cứ nhƣ vậy số lời gọi đệ qui sẽ tăng theo cấp số mũ. Điều này rõ ràng là không hiệu quả
vì trong số các lời gọi đệ qui đó có rất nhiều lời gọi trùng nhau. Ví dụ lời gọi đệ qui Fibonaci (6)
sẽ dẫn đến 2 lời gọi Fibonaci (5) và Fibonaci (4). Lời gọi Fibonaci (5) sẽ gọi Fibonaci (4) và
Fibonaci (3). Ngay chỗ này, ta đã thấy có 2 lời gọi Fibonaci (4) đƣợc thực hiện. Hình 2.1 cho thấy
số các lời gọi đƣợc thực hiện khi gọi thủ tục Fibonaci (6).
6
5
4
4
3
2
3
1
1
0
2
2
1
3
2
1
0
1
0
2
1
1
0
1
0
Hình 2.1 Các lời gọi đệ qui đƣợc thực hiện khi gọi thủ tục Fibonaci (6)
Trong hình vẽ trên, ta thấy để tính đƣợc phần tử thứ 6 thì cần có tới 25 lời gọi ! Sau đây, ta
sẽ xem xét việc sử dụng vòng lặp để tính giá trị các phần tử của dãy Fibonaci nhƣ thế nào.
Đầu tiên, ta khai báo một mảng F các số tự nhiên để chứa các số Fibonaci. Vòng lặp để tính
và gán các số này vào mảng rất đơn giản nhƣ sau:
F[0]=0;
F[1]=1;
for (i=2; i<n-1; i++)
17
F[i] = F[i-1] + F [i-2];
Rõ ràng là với vòng lặp này, mỗi số Fibonaci (n) chỉ đƣợc tính 1 lần thay vì đƣợc tính toán
chồng chéo nhƣ ở trên.
Tóm lại, nên tránh sử dụng đệ qui nếu có một giải pháp khác cho bài toán. Mặc dù vậy, một
số bài toán tỏ ra rất phù hợp với phƣơng pháp đệ qui. Việc sử dụng đệ qui để giải quyết các bài
toán này hiệu quả và rất dễ hiểu. Trên thực tế, tất cả các giải thuật đệ qui đều có thể đƣợc đƣa về
dạng lặp (còn gọi là “khử” đệ qui). Tuy nhiên, điều này có thể làm cho chƣơng trình trở nên phức
tạp, nhất là khi phải thực hiện các thao tác điều khiển stack đệ qui (bạn đọc có thể tìm hiểu thêm
kỹ thuật khử đệ qui ở các tài liệu tham khảo khác), dẫn đến việc chƣơng trình trở nên rất khó hiểu.
Phần tiếp theo sẽ trình bày một số thuật toán đệ qui điển hình.
2.2 THIẾT KẾ GIẢI THUẬT ĐỆ QUI
2.2.1 Chƣơng trình tính hàm n!
Theo định nghĩa đã trình bày ở phần trƣớc, n! = 1 nếu n=0, ngƣợc lại, n! = (n-1)! * n.
int giaithua (int n){
if (n==0) return 1;
else return giaithua(n-1) * n;
}
Trong chƣơng trình trên, điểm dừng của thuật toán đệ qui là khi n=0. Khi đó, giá trị của
hàm giaithua(0) có thể tính đƣợc ngay lập tức mà không cần gọi hạm đệ qui khác. Nếu điều kiện
dừng không thỏa mãn, sẽ có một lời gọi đệ qui hàm giai thừa với tham số là n-1, nhỏ hơn tham số
ban đầu 1 đơn vị (tức là bài toán tính n! đã đƣợc qui về bài toán đơn giản hơn là tính (n-1)!).
2.2.2 Thuật toán Euclid tính ƣớc số chung lớn nhất của 2 số nguyên dƣơng
Ƣớc số chung lớn nhất (USCLN) của 2 số nguyên dƣơng m, n là 1 số k lớn nhất sao cho m
và n đều chia hết cho k. Một phƣơng pháp đơn giản nhất để tìm USCLN của m và n là duyệt từ số
nhỏ hơn trong 2 số m, n cho đến 1, ngay khi gặp số nào đó mà m và n đều chia hết cho nó thì đó
chính là USCLN của m, n. Tuy nhiên, phƣơng pháp này không phải là cách tìm USCLN hiệu quả.
Cách đây hơn 2000 năm, Euclid đã phát minh ra một giải thuật tìm USCLN của 2 số nguyên
dƣơng m, n rất hiệu quả. Ý tƣởng cơ bản của thuật toán này cũng tƣơng tự nhƣ ý tƣởng đệ qui, tức
là đƣa bài toán về 1 bài toán đơn giản hơn. Cụ thể, giả sử m lớn hơn n, khi đó việc tính USCLN
của m và n sẽ đƣợc đƣa về bài toán tính USCLN của m mod n và n vì USCLN(m, n) = USCLN(m
mod n, n).
Thuật toán đƣợc cài đặt nhƣ sau:
int USCLN(int m, int n){
if (n==0) return m;
else return USCLN(n, m % n);
}
Điểm dừng của thuật toán là khi n=0. Khi đó đƣơng nhiên là USCLN của m và 0 chính là
m, vì 0 chia hết cho mọi số. Khi n khác 0, lời gọi đệ qui USCLN(n, m% n) đƣợc thực hiện. Chú ý
rằng ta giả sử m >= n trong thủ tục tính USCLN, do đó, khi gọi đệ qui ta gọi USCLN (n, m% n)
để đảm bảo thứ tự các tham số vì n bao giờ cũng lớn hơn phần dƣ của phép m cho n. Sau mỗi lần
gọi đệ qui, các tham số của thủ tục sẽ nhỏ dần đi, và sau 1 số hữu hạn lời gọi tham số nhỏ hơn sẽ
bằng 0. Đó chính là điểm dừng của thuật toán.
18
Ví dụ, để tính USCLN của 108 và 45, ta gọi thủ tục USCLN(108, 45). Khi đó, các thủ tục
sau sẽ lần lƣợt đƣợc gọi:
USCLN(108, 45) 108 chia 45 dư 18, do đó tiếp theo gọi
USCLN(45, 18) 45 chia 18 dư 9, do đó tiếp theo gọi
USCLN(18, 9) 18 chia 9 dư 0, do đó tiếp theo gọi
USCLN(9, 0) tham số thứ 2 = 0, do đó kết quả là tham số thứ nhất, tức là 9.
Nhƣ vậy, ta tìm đƣợc USCLN của 108 và 45 là 9 chỉ sau 4 lần gọi thủ tục.
2.2.3 Các giải thuật đệ qui dạng chia để trị (divide and conquer)
Ý tƣởng cơ bản của các thuật toán dạng chia để trị là phân chia bài toán ban đầu thành 2
hoặc nhiều bài toán con có dạng tƣơng tự và lần lƣợt giải quyết từng bài toán con này. Các bài
toán con này đƣợc coilà dạng đơn giản hơn của bài toán ban đầu, do vậy có thể sử dụng các lời
gọi đệ qui để giải quyết. Thông thƣờng, các thuật toán chia để trị chia bộ dữ liệu đầu vào thành 2
phần riêng rẽ, sau đó gọi 2 thủ tục đệ qui để với các bộ dữ liệu đầu vào là các phần vừa đƣợc chia.
Một ví dụ điển hình của giải thuật chia để trị là Quicksort, một giải thuật sắp xếp nhanh. Ý
tƣởng cơ bản của giải thuật này nhƣ sau:
Giải sử ta cần sắp xếp 1 dãy các số theo chiều tăng dần. Tiến hành chia dãy đó thành 2 nửa
sao cho các số trong nửa đầu đều nhỏ hơn các số trong nửa sau. Sau đó, tiến hành thực hiện sắp
xếp trên mỗi nửa này. Rõ ràng là sau khi mỗi nửa đã đƣợc sắp, ta tiến hành ghép chúng lại thì sẽ
có toàn bộ dãy đƣợc sắp. Chi tiết về giải thuật Quicksort sẽ đƣợc trình bày trong chƣơng 7 - Sắp
xếp và tìm kiếm.
Tiếp theo, chúng ta sẽ xem xét một bài toán cũng rất điển hình cho lớp bài toán đƣợc giải
bằng giải thuật đệ qui chia để trị.
Bài toán tháp Hà nội
Có 3 chiếc cọc và một bộ n chiếc đĩa. Các đĩa này có kích thƣớc khác nhau và mỗi đĩa đều
có 1 lỗ ở giữa để có thể xuyên chúng vào các cọc. Ban đầu, tất cả các đĩa đều nằm trên 1 cọc,
trong đó, đĩa nhỏ hơn bao giờ cùng nằm trên đĩa lớn hơn.
Cọc B
Cọc C
Cọc A
Hình 2.2 Bài toán tháp Hà nội
Yêu cầu của bài toán là chuyển bộ n đĩa từ cọc ban đầu A sang cọc đích C (có thể sử dụng
cọc trung gian B), với các điều kiện:
-
Mỗi lần chuyển 1 đĩa.
-
Trong mọi trƣờng hợp, đĩa có kích thƣớc nhỏ hơn bao giờ cũng phải nằm trên đĩa có
kích thƣớc lớn hơn.
Với n=1, có thể thực hiện yêu cầu bài toán bằng cách chuyển trực tiếp đĩa 1 từ cọc A sang
cọc C.
19
Với n=2, có thể thực hiện nhƣ sau:
-
-
Chuyển đĩa nhỏ từ cọc A sang cọc trung gian B.
Chuyển đĩa lớn từ cọc A sang cọc đích C.
-
Cuối cùng, chuyển đĩa nhỏ từ cọc trung gian B sang cọc đích C.
Nhƣ vậy, cả 2 đĩa đã đƣợc chuyển sang cọc đích C và không có tình huống nào đĩa lớn nằm
trên đĩa nhỏ.
Với n > 2, giả sử ta đã có cách chuyển n-1 đĩa, ta thực hiện nhƣ sau:
-
-
Lấy cọc đích C làm cọc trung gian để chuyển n-1 đĩa bên trên sang cọc trung gian B.
Chuyển cọc dƣới cùng (cọc thứ n) sang cọc đích C.
-
Lấy cọc ban đầu A làm cọc trung gian để chuyển n-1 đĩa từ cọc trung gian B sang cọc
đích C.
Có thể minh họa quá trình chuyển này nhƣ sau:
Trạng thái ban đầu:
Cọc C
Bƣớc 1: Chuyển n-1 đĩa bên trên từ cọc A sang cọc B, sử dụng cọc C làm cọc trung gian.
Cọc A
Cọc B
Cọc C
Cọc B
Bƣớc 2: Chuyển đĩa dƣới cùng từ cọc A thẳng sang cọc C.
Cọc A
Cọc C
Bƣớc 3: Chuyển n-1 đĩa từ cọc B sang cọc C sử dụng cọc A làm cọc trung gian.
Cọc A
Cọc B
20
Tải về để xem bản đầy đủ
145 trang
22800
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 - Học viện Công nghệ Bưu chính viễn thông", để 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_hoc_vien_cong_nghe.pdf
