MỤC LỤC .1
Chương 1: CẤU TRÚC DỮ LIỆU CƠ BẢN .6
1.1. Mảng .6
1.1.1. Khái niệm .6
1.1.2. Mảng một chiều.6
1.1.3 Mảng hai chiều .6
1.2. Biến động và con trỏ.7
1.2.1. Biến động .7
1.2.2. Con trỏ.7
1.2.3. Sử dụng con trỏ.9
1.3. Danh sách (LIST) .13
1.3.1. Khái niệm .13
1.3.2. Danh sách cài đặt bởi mảng .15
1.3.3. Danh sách liên kết.19
1.3.4. Ngăn xếp (stack).26
1.3.5. Hàng đợi (Queue)
56 trang |
Chia sẻ: phuongt97 | Lượt xem: 595 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Phân tích thiết kế giải thuật và cấu trúc dữ liệu (Phần 1), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
giá trị của g là
ước chung lớn nhất của m và n.
3. Tính xác định. Mỗi bước của thuật toán cần phải được mô tả một
cách chính xác, chỉ có một cách hiểu duy nhất. Hiển nhiên, đây là một đòi hỏi
rất quan trọng. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau,
thì cùng một dữ liệu vào, những người thực hiện thuật toán khác nhau có thể
dẫn đến các kết quả khác nhau. Nếu ta mô tả thuật toán bằng ngôn ngữ thông
thường, không có gì đảm bảo người đọc hiểu đúng ý của người viết thuật
toán. Để đảm bảo đòi hỏi này, thuật toán cần được mô tả trong các ngôn ngữ
lập trình (ngôn ngữ máy, hợp ngữ hoặc ngôn ngữ bậc cao như Pascal, Fortran,
C, ...). Trong các ngôn ngữ này, các mệnh đề được tạo thành theo các qui tắc
cú pháp nghiêm ngặt và chỉ có một ý nghĩa duy nhất.
4. Tính khả thi. Tất cả các phép toán có mặt trong các bước của thuật
toán phải đủ đơn giản. Điều đó có nghĩa là, các phép toán phải sao cho, ít nhất
về nguyên tắc có thể thực hiện được bởi con người chỉ bằng giấy trắng và bút
chì trong một khoảng thời gian hữu hạn. Chẳng hạn trong thuật toán Euclid, ta
chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so
sánh để biết r = 0 hay r 0.
5. Tính dừng. Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ
liệu vào (tức là được lấy ra từ các tập giá trị của các dữ liệu vào), thuật toán
phải dừng lại sau một số hữu hạn bước thực hiện. Chẳng hạn, thuật toán
40
Euclid thoả mãn điều kiện này. Bởi vì giá trị của r luôn nhỏ hơn n (khi thực
hiện bước 1), nếu r 0 thì giá trị của n ở bước 2 là giá trị của r ở bước trước,
ta có n > r = n1 > r1 = n2 > r2 ... Dãy số nguyên dương giảm dần cần phải kết
thúc ở 0, do đó sau một số bước nào đó giá trị của r phải bằng 0, thuật toán
khi đó dừng.
Với một vấn đề đặt ra, có thể có một hoặc nhiều thuật toán giải. Một
vấn đề có thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn,
vấn đề tìm nghiệm của hệ phương trình tuyến tính là vấn đề giải được. Một
vấn đề không tồn tại thuật toán giải gọi là vấn đề không giải được (bằng thuật
toán). Một trong những thành tựu xuất sắc nhất của toán học thế kỷ 20 là đã
tìm ra những vấn đề không giải được bằng thuật toán.
Trên đây chúng ta đã trình bày định nghĩa không hình thức về thuật
toán. Có thể xác định khái niệm thuật toán một cách chính xác bằng cách sử
dụng các hệ hình thức. Có nhiều hệ hình thức mô tả thuật toán : máy Turing,
hệ thuật toán Markôp, văn phạm Chomsky dạng 0, ... Song vấn đề này không
thuộc phạm vi những vấn đề mà chúng ta quan tâm. Đối với chúng ta, chỉ sự
hiểu biết trực quan, không hình thức về khái niệm thuật toán là đủ.
2.1.3. Đánh giá thuật toán
2.1.3.1. Tính hiệu quả của thuật toán.
Khi giải một vấn đề, chúng ta cần chọn trong số các thuật toán, một thuật toán
mà chúng ta cho là "tốt" nhất. Vậy ta cần lựa chọn thuật toán dựa trên cơ sở
nào ? Thông thường ta dựa trên hai tiêu chuẩn sau đây :
1. Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
2. Thuật toán sử dụng tiết kiệm nhất các nguồn tài nguyên của máy
tính, và đặc biệt, chạy nhanh nhất có thể được.
Khi ta viết một chương trình chỉ để sử dụng một số ít lần, và cái giá
của thời gian viết chương trình vượt xa cái giá của chạy chưong trình thì tiêu
chuẩn (1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương
trình (hoặc thủ tục, hàm) để sử dụng nhiều lần, cho nhiều người sử dụng, khi
đó giá của thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các
thủ tục sắp xếp, tìm kiếm được sử dụng rất nhiều lần, bởi rất nhiều người
41
trong các bài toán khác nhau. Trong trường hợp này ta cần dựa trên tiêu chuẩn
(2). Ta sẽ cài đặt thuật toán có thể rất phức tạp, miễn là chương trình nhận
được chạy nhanh hơn các chương trình khác.
Tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán. Tính hiệu quả
của thuật toán bao gồm hai nhân tố cơ bản.
1. Dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, các
kết quả tính toán trung gian và các kết quả của thuật toán.
2. Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy).
Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện thuật toán. Vì vậy,
khi nói đến đánh giá độ phức tạp của thuật toán, có nghĩa là ta nói đến đánh
gia thời gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có
thời gian chạy ít hơn các thuật toán khác.
Ký hiệu ô lớn và đánh giá thời gian thực hiện thuật toán bằng ký
hiệu ô lớn.
Khi đánh giá thời gian thực hiện bằng phương pháp toán học, chúng ta
sẽ bỏ qua nhân tố phụ thuộc vào cách cài đặt chỉ tập trung vào xác định độ lớn
của thời gian thực hiện T(n). Ký hiệu toán học ô lớn được sử dụng để mô tả
độ lớn của hàm T(n).
Giả sử n là số nguyên không âm, T(n) và f(n) là các hàm thực không
âm. Ta viết T(n) = 0(f(n)) (đọc: T(n) là ô lớn của f(n)), nếu và chỉ nếu tồn tại
các hằng số dương c và no sao cho T(n) c f(n), với mọi n no.
Nếu một thuật toán có thời gian thực hiện T(n) = 0(f(n)), chúng ta sẽ
nói rằng thuật toán có thời gian thực hiện cấp f(n). Từ định nghĩa ký hiệu ô
lớn, ta có thể xem rằng hàm f(n) là cận trên của T(n).
Ví dụ : Giả sử T(n) = 3n2 + 5n + 4. Ta có
2 2 2 2 2
3n + 5n + 4 <= 3n + 5n + 4n = 12n , với mọi n 1.
Vậy T(n) = 0(n2). Trong trường hợp này ta nói thuật toán có thời gian
thực hiện cấp n2, hoặc gọn hơn, thuật toán có thời gian thực hiện bình
phương.
42
Dễ dàng thấy rằng, nếu T(n) = 0(f(n)) và f(n) = 0(f1(n)) , thì
T(n)=0(f1(n)). Thật vậy, vì T(n) là ô lớn của f(n) và f(n) là ô lớn của f1(n), do
đó tồn tại các hằng số co, no, c1, n1 sao cho T(n) co f(n) với mọi n no và
f(n) c1f1(n) với mọi n n1. Từ đó ta có T(n) coc1f1(n) với mọi n
max(no,n1).
Khi biểu diễn cấp của thời gian thực hiện thuật toán bởi hàm f(n),
chúng ta sẽ chọn f(n) là hàm số nhỏ nhất, đơn giản nhất có thể được sao cho
T(n) = 0(f(n)). Thông thường f(n) là các hàm số sau đây : f(n) = 1 ; f(n)=logn;
f(n)=n ; f(n) = nlogn ; f(n) = n2, n3, ... và f(n) = 2n.
Nếu T(n) = 0(1) điều này có nghĩa là thời gian thực hiện bị chặn trên
bởi một hằng số nào đó, trong trường hợp này ta nói thuật toán có thời gian
thực hiện hằng.
Nếu T(n) =0(n), tức là bắt đầu từ một no nào đó trở đi ta có T(n)<=cn
với một hằng số c nào đó, thì ta nói thuật toán có thời gian thực hiện tuyến
tính.
Bảng sau đây cho ta các cấp thời gian thực hiện thuật toán được sử
dụng rộng rãi nhất và tên gọi thông thường của chúng.
2.1.3.2 Các qui tắc để đánh giá thời gian thực hiện thuật toán.
Sau đây chúng ta đưa ra một qui tắc cần thiết về ô lớn để đánh giá thời
gian thực hiện một thuật toán.
Qui tắc tổng : Nếu T1(n) = 0(f1(n) và T2(n) = 0(f2(n) thì
T1(n) + T2(n) = 0(max(f1(n), f2(n))).
43
1. Thời gian thực hiện các lệnh đơn : gán, đọc, viết, goto là 0(1).
2. Lệnh hợp thành. Thời gian thực hiện lệnh hợp thành được xác định
bởi luật tổng.
3. Lệnh if. Giả sử thời gian thực hiện các lệnh S1, S2 là 0(f1(n)) và
0(f2(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là 0(max(f1(n), f2(n))).
4. Lệnh case. Được đánh giá như lệnh if.
5. Lệnh while. Giả sử thời gian thực hiện lệnh S (thân của lệnh while)
là 0(f(n)). Giả sử g(n) là số tối đa các lần thực hiện lệnh S, khi thực hiện lệnh
while. Khi đó thời gian thực hiện lệnh while là 0(f(n)g(n).
6. Lệnh repeat. Giả sử thời gian thực hiện khối begin S1, S2, ... Sn end là
0(f(n)). Giả sử g(n) là số tối đa các lần lặp. Khi đó thời gian thực hiện lệnh
repeat là 0(f(n)g(n)).
7. Lệnh for. Được đánh giá tương tự lệnh while và repeat.
2.2. Một số thuật toán đơn giản
2.2.1. Tìm Ước chung lớn nhất của 2 số tự nhiên
Phân tích thuật toán Euclid. Chúng ta biểu diễn thuật toán Euclid bởi
hạm sau.
function Euclid (m, n : integer) : integer ;
var r : integer ;
begin
(1) r : = m mod n ;
(2) while r 0 do
begin
(3) m : = n ;
(4) n : = r ;
(5) r : = m mod n ;
end ;
44
(6) Euclid : = n ;
end ;
Thời gian thực hiện thuật toán phụ thuộc vào số nhỏ nhất trong hai số
m và n. Giả sử m n > 0, do đó cỡ của dữ liệu vào là n. Các lệnh (1) và (6) có
thời gian thực hiện là 0(1). Vì vậy thời gian thực hiện thuật toán là thời gian
thực hiện lệnh while ta đánh giá thời gian thực hiện lệnh while (2). Thân của
lệnh này, là khối gồm ba lệnh (3), (4) và (5). Mỗi lệnh có thời gian thực hiện
là 0(1), do đó khối có thời gian thực hiện là 0(1). Còn phải đánh giá số lớn
nhất các lần thực hiện lặp khối.
Ta có :
m = n.q1 + r1 , 0 r1 < n
n = r1q2 + r2 , 0 r2 < r1
Nếu r1 n/2 thì r2 n/2 thì q2 = 1, tức là n =
r1 + r2 , do đó r2 < n/2. Tóm lại, ta luôn có r2 < n/2
Như vậy, cứ hai lần thực hiện khối thì phần dư r giảm đi một nửa của n.
Gọi k là số nguyên lớn nhất sao cho 2k n. Số lần lặp khối tối đa là
2k+12log2n+1. Do đó thời gian thực hiện lệnh while là 0(log2n). Đó cũng là
thời gian thực hiện thuật toán.
2.2.2. Kiểm tra một số tự nhiên có phải là số nguyên tố không
Thuật toán kiểm tra số nguyên n (n > 2) có là số nguyên tố hay không.
function NGTO (n : integer) : boolean ;
var a : integer ;
begin NGTO : = true ; a : = 2 ;
while a <= sqrt (n) do
if n mod a = 0 then NGTO : = false
else a : = a +1 ;
end ;
45
Chương 3
ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY
3.1. Khái niệm đệ quy
Ta nói một đối tượng là đệ qui nếu đối tượng này bao gồm chính nó
như một bộ phận hoặc đối tượng được định nghĩa dưới dạng của chính nó.
Ví dụ1: Trong toán học ta gặp các định nghĩa đệ quy sau:
+ Số tự nhiên:
- 1 là số tự nhiên.
- n là số tự nhiên nếu n-1 là số tự nhiên.
+ Hàm n giai thừa: n!
- 0! = 1
- Nếu n>0 thì N! = n(n-1)!
Ví dụ 2 : Cấu trúc thư mục là một dạng định nghĩa đệ qui : thư mục
chứa thư mục con.
3.2. Giải thuật đệ quy
Nếu lời giải của bài toán T được thực hiện thông qua lời giải của một
bài toán T’ có kích thước nhỏ hơn T và có dạng giống như T, thì đó là một lời
giải đệ qui. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ qui.
Ở đây T1 có dạng giống T nhưng theo một nghĩa nào đó T1 phải “nhỏ”
hơn T.
Trong thủ tục có lời gọi đến chính nó gọi là thủ tục đệ qui.
Chẳng hạn với bài toán tính n! thì n! là bài toán T còn (n-1)! là bài toán
T1 ta thấy T1 cùng dạng với T nhưng nhỏ hơn (n-1 < n).
Xét bài toán tìm một từ trong quyển từ điển. Có thể nêu giải thuật như
sau:
If từ điển là một trang then
46
tìm từ trong trang này
else begin
Mở từ điển vào trang “giữa”
Xác định xem nửa nào của từ điển chứa từ cần tìm;
if từ đó nằm ở nửa trước then
tìm từ đó ở nửa trước
else tìm từ đó ở nửa sau.
end;
Giải thuật này được gọi là giải thuật đệ quy. Việc tìm từ trong quyển từ
điển được được giải quyết bằng bài toán nhỏ hơn đó là việc tìm từ trong một
nửa thích hợp của quyển từ điển.
Ta thấy có hai điểm chính cần lưu ý:
a) Sau mỗi lần từ điển được tách làm đôi thì một nửa thích hợp sẽ lại
được tìm bằng một chiến thuật như đã dùng trước đó (nửa này lại được tách
đôi).
b) Có một trường hợp đặc biệt, đó là sau nhiều lần tách đôi từ điển chỉ
còn một trang. Khi đó việc tách đôi ngừng lại và bài toán trở thành đủ nhỏ để
ta có thể tìm từ mong muốn bằng cách tìm tuần tự. Trường hợp này gọi là
trường hợp suy biến.
* Cấu trúc chung của một thủ tục đệ quy.
Một thủ tục đệ qui gồm có hai phần chính
1. Phần cố định: gía trị khởi đầu cho hàm, thủ tục đệ qui.
2. Phần hạ bậc:(phần đệ qui): Tác động của hàm đệ qui được thực hiện
thông qua tác động hay giá trị đã được định nghĩa trước.
Thủ tục trên được gọi là thủ thục đệ quy. Nó có những đặc điểm cơ bản
sau:
47
a) Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó. Ở đây trong thủ
tục SEARCH có lời gọi call SEARCH (lời gọi này được gọi là lời gọi đệ
quy).
b) Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu
nhỏ hơn trước. Ở đây khi có lời gọi call SEARCH thì kích từ điển chỉ còn
bằng một nửa so với trước đó.
c) Có một trường hợp đặc biệt, trường hợp suy biến là khi lời gọi call
SEARCH với từ điển dict chỉ còn là một trang. Khi trường hợp này xảy ra thì
bài toán còn lại sẽ được giải quyết theo một cách khác hẳn (tìm từ word trong
trang đó bằng cách tìm kiếm tuần tự) và việc gọi đệ quy cũng kết thúc. Chính
tình trạng kích thước bài toán giảm dần sau mỗi lần gọi đệ quy sẽ đảm bảo
dẫn tới trường hợp suy biến.
Một số ngôn ngữ cấp cao như: Pascal, C, Algol v.v... cho phép viết các
thủ tục đệ quy. Nếu thủ tục đệ quy chứa lời gọi đến chính nó thì gọi là đệ quy
trực tiếp. Cũng có trường hợp thủ chứa lời gọi đến thủ tục khác mà ở thủ tục
này lại chứa lời gọi đến nó. Trường hợp này gọi là đệ quy gián tiếp.
3.3 Một số ứng dụng của giải thuật đệ quy
Khi bài toán đang xét hoặc dữ liệu đang xử lý được định nghĩa dưới
dạng đệ quy thì việc thiết kế các giải thuật đệ quy tỏ ra rất thuận lợi. Hầu như
nó phản ánh rất sát nội dung của định nghĩa đó.
Ta xét một số bài toán sau:
3.3.1. Hàm n!
Hàm này được định nghĩa như sau:
1 nÕu n 0
Factorial(n)
n * Factorial(n - 1) nÕu n 0
Giải thuật đệ quy được viết dưới dạng hàm dưới đây:
Function Factorial(n)
Begin
if n=0 then Factorial:=1
48
else Factorial := n*Factorial(n-1);
End;
Trong hàm trên lời gọi đến nó nằm ở câu lệnh gán sau else.
Mỗi lần gọi đệ quy đến Factorial, thì giá trị của n giảm đi 1. Ví du,
Factorial(4) gọi đến Factorial(3), gọi đến Factorial(2), gọi đến Factorial(1),
gọi đến Factorial(0) đây là trường hợp suy biến, nó được tính theo cách đặc
biệt Factorial(0) = 1.
3.3.2. Bài toán dãy số FIBONACCI.
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp
thỏ. Bài toán được đặt ra như sau:
- Các con thỏ không bao giờ chết.
- Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con.
- Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một
cặp con mới.
Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ n sẽ có bao
nhiêu cặp?
Ví dụ với n = 6, ta thấy.
Tháng thứ 1: 1 cặp (cặp ban đầu)
Tháng thứ 2: 1 cặp (cặp ban đầu vẵn chưa đẻ)
Tháng thứ 3: 2 cặp (đã có thêm 1 cặp con)
Tháng thứ 4: 3 cặp (cặp đầu vẫn đẻ thêm)
Tháng thứ 5: 5 cặp (cặp con bắt đầu đẻ)
Tháng thứ 6: 8 cặp (cặp con vẫn đẻ tiếp)
Đặt F(n) là số cặp thỏ ở tháng thứ n. Ta thấy chỉ những cặp thỏ đã có ở
tháng thứ n-2 mới sinh con ở tháng thứ n do đó số cặp thỏ ở tháng thứ n là:
F(n) = f(n-2) + F(n-1) vì vậy F(n) có thể được tính như sau:
1 nÕu n 2
F(n)
F(n - 2) F(n - 1) nÕu n 2
49
Dãy số thể hiện F(n) ứng với các giá trị của n = 1, 2, 3, 4..., có dạng
1 1 2 3 5 8 13 21 34 55.... nó được
gọi là dãy số Fibonacci. Nó là mô hình của rất nhiều hiện tượng tự nhiên và
cũng được sử dụng nhiều trong tin học.
Sau đây là thủ tục đệ quy thể hiện giải thuật tính F(n).
Function F(n)
Begin
if n<=2 then F:=1
else F := F(n-2) + F(n-1);
End;
Ở đây trường hợp suy biến ứng với 2 giá trị F(1) = 1 và F(2) = 1.
3.3.3. Tìm ước số chung lớn nhất của hai số nguyên dương a va b.
Phát biểu bài toán:
USCLN(a, b) = b , nếu (a mod b)= 0) // trường hợp
suy biến
USCLN(a, b) := USCLN(b, a mod b), nếu (a mod b) 0)
// trường hợp đệ qui
CT đệ qui:
Function uscln(a: integer, b: integer):integer
Begin
if ((a mod b) = 0) then
uscln:=b;
else uscln:=uscln(b, a mod b);
End;
* Chú ý.
50
Đối với hai bài toán nêu trên thì việc thiết kế các giải thuật đệ quy
tương ứng khá thuận lợi vì cả hai đều thuộc dạng tính giá trị hàm mà định
nghĩa của nó xác định được dễ dàng.
Nhưng không phải lúc nào tính đệ quy trong cách giải bài toán cũng thể
hiện rõ nét và đơn giản như vậy. Mà việc thiết kế một giải thuật đệ quy đòi
hỏi phải giải đáp được các câu hỏi sau:
- Có thể định nghĩa được bài toán dưới dạng một bài toán cùng loại,
nhưng nhỏ hơn như thế nào?
- Như thế nào là kích thước của bài toán được giảm đi ở mỗi lần gọi đệ
quy?
- Trường hợp đặc biệt nào của bài toán được gọi là trường hợp suy
biến?
3.3.4 Bài toán “Tháp Hà Nội”.
Bài toán này mang tính chất là một trò chơi, nội dung như sau:
Có n đĩa, kích thước nhỏ dần, mỗi đĩa có lỗ ở giữa. Có thể xếp chồng
chúng lên nhau xuyên qua một cọc, đĩa to ở dưới, đĩa nhỏ ở trên để cuối cùng
có một chồng đĩa dạng như hình tháp như hình dưới đây.
A B C
Hình 1
Yêu cầu đặt ra là:
Chuyển chồng đĩa từ cọc A sang cọc khác, chẳng hạn cọc C, theo
những điều kiện:
- Mỗi lần chỉ được chuyển một đĩa.
- Không khi nào có tình huống đĩa to ở trên đĩa nhỏ (dù là tạm thời).
51
- Được phép sử dụng một cọc trung gian, chẳng hạn cọc B để đặt tạm
đĩa (gọi là cọc trung gian).
Để đi tới cách giải tổng quát, trước hết ta xét vài trường hợp đơn giản.
*) Trường hợp có 1 đĩa:
- Chuyển đĩa từ cọc A sang cọc C.
*) Trường hợp 2 đĩa:
- Chuyển đĩa thứ nhất từ cọc A sang cọc B Chuyển đĩa thứ hai từ cọc
A sang cọc C Chuyển đĩa thứ nhất từ cọc B sang cọc C.
Ta thấy với trường hợp n đĩa (n>2) nếu coi n-1 đĩa ở trên, đóng vai trò
như đĩa thứ nhất thì có thể xử lý giống như trường hợp 2 đĩa được, nghĩa là:
- Chuyển n-1 đĩa trên từ A sang B Chuyển đĩa thứ n từ A sang C
Chuyển n-1 đĩa từ B sang C.
Lược đồ thể hiện 3 bước này như sau:
A B C
Bước 1
A B C
Bước 2
A B C
Bước 3
A B C
52
Như vậy, bài toán “Tháp Hà Nội” tổng quát với n đĩa đã được dẫn đến
bài toán tương tự với kích thước nhỏ hơn, chẳng hạn từ chỗ chuyển n đĩa từ
cọc A sang cọc C nay là chuyển n-1 đĩa từ cọc A sang cọc B và ở mức này thì
giải thuật lại là:
- Chuyển n-2 đĩa từ cọc A sang cọc C.
- Chuyển 1 đĩa tử cọc A sang cọc B.
- Chuyển n-2 đĩa từ cọc B sang cọc C.
và cứ như thế cho tới khi trường hợp suy biến xảy ra, đó là trường hợp ứng
với bài toán chuyển 1 đĩa.
Vậy thì các đặc điểm của đệ quy trong giải thuật đã được xác định và ta
có thểviết giải thuật đệ quy của bài toán “Tháp Hà Nôị” như sau:
Procedure Chuyen(n, A, B, C)
Begin
if n=1 then chuyển đĩa từ A sang C
else begin
call Chuyen(n-1, a, C, B);
call Chuyen(1, A, B, C);
call Chuyen(n-1, B, A, C) ;
end;
End;
3.3.5 Bài toán 8 quân hậu và giải thuật đệ qui quay lui.
Cho bàn cờ vua 8x8. Hãy xếp 8 con hậu lên bàn cờ sao cho không con
nào khống chế con nào. Hai con hậu khống chế nhau nếu chúng ở trên cùng
một hàng, một cột hoặc một đường chéo.
Phân tích bài toán:
Vị trí của mỗi quân hậu được xác định qua số thứ tự của dòng và cột.
Do đó ta coi con hậu thứ i ở hàng i và cột x[i]. Vậy nghiệm của bài toán có
53
thể coi là một vector x gồm 8 thành phần với ý nghĩa:
1. Con hậu thứ i được đặt ở hàng i và cột x[i]. x[i] lấy giá trị trong tập
{1,2n}
2. Ràng buộc: các giá trị x[i] khác nhau từng đôi một và không có 2 con
hậu ở trên cùng một đường chéo.
Dùng thêm các mảng đánh dấu để mô tả rằng một đường chéo chính và
phụ đã có một con hậu khống chế. Tức là khi ta đặc con hậu i ở vị trí (i,j), ta
sẽ đánh dấu đường chéo chính i-j và đường chéo phụ i+j.
Như vậy về cấu trúc dữ liệu, ta dùng 4 mảng:
1. Mảng x với ý nghĩa: x[i] là cột ta sẽ đặt con hậu thứ i.
2. Mảng cot với ý nghĩa: cot[j]=1 nếu cột j đã có một con hậu được đặt,
ngược lại thì cot[j]=0.
3. Mảng dcc với ý nghĩa: dcc[k]=1 nếu đường chéo chính thứ k đã có
một con hậu được đặt, tức là ta đã đặt một con hậu j=k; ngược lại thì
dcc[k]=0.
4. Tương tự ta dùng mảng dcp với ý nghĩa: dcp[k]=1 nếu đường chéo
phụ thứ k đã có một con hậu được đặt.
Giả mã của thuật toán xếp hậu như sau:
procedure Try(i);
var j;
begin
for j := 1 to n do
if (cot[j]=0) and (dcc[i-j]=0) and (dcp[i+j]=0) then
begin
x[i] := j;
cot[j]:=1;
dcc[i-j]:=1;
dcp[i+j]:=1;{ghi nhận trạng thái mới}
54
if i=n then
Update
else
Try(i+1);
cot[j]:=0;
dcc[i-j]:=0;
dcp[i+j]:=0; {phục hồi trạng thái cũ}
end;
end;
procedure Update;
begin
count := count + 1;
print(x);
end;
* Khử đệ quy
Khi thay các giải thuật đệ qui bằng các giải thuật không đệ qui, ta gọi là
khử đệ qui.
Ví dụ 1: n!
Function gt(n:integer):integer;
Var tg,i:integer;
Begin
tg:=1;
If ((n=0) or (n=1) then
gt:=1
Else
Begin
55
For i:=1 to n do
tg:=tg*i;
gt:=tg;
End;
End;
Ví dụ 2: Fibonacci
Function Fibo (n:byte):double;
Begin
If n<=2 then Fibo:=1
Else
Begin
F1:=1;f2:=1;
For i:=3 to n do
begin
fn:=f1+f2; f1:=f2;f2:=fn
end;
Fibo:=fn;
End;
56
Các file đính kèm theo tài liệu này:
- bai_giang_phan_tich_thiet_ke_giai_thuat_va_cau_truc_du_lieu.pdf