Nhập môn thuật toán - Công nghệ thông tin | Trường Đại học Quy Nhơn

PHẦN 1
CÁC KHÁI NIỆM CƠ BẢN
Phần này nhắc lại các khái niệm cơ bản liên quan tới thuật toán và một số thuật toán sơ
cấp quen thuộc thường dùng.
1. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP TÍNH TOÁN. 1.1.
Thuật toán, đặc trưng, mô tả thuật toán
Khái niệm thuật toán
Tùy theo từng góc độ mà khái niệm thuật toán có thể được hiểu theo nhiều cách khác nhau, chẳng hạn:
Thuật toán là phương pháp giải quyết vấn đề nào đó theo từng bước
Thuật toán là các quy tắc để tính toán
Thuật toán là phương pháp giải quyết vấn đề thích hợp cho cài đặt trên máy tính
Trong tài liệu này khái niệm thuật toán được định nghĩa như sau:
Thuật toán là một dãy hữu hạn các bước hành động xác định để giải quyết một vấn đề,
quá trình thực hiện các bước hành động này phải dừng và cho kết quả như mong muốn.
Các đặc trưng của thuật toán
 Đầu vào và đầu ra: Một thuật toán phải nhận dữ liệu đầu vào để xử lý và cho kết quả ở đầu ra.
 Tính hữu hạn (hay còn gọi là tính dừng): Một áp dụng của thuật toán sẽ phải cho ra
kết quả sau một số hữu hạn hành động.
 Tính đơn trị: Kết quả của mỗi hành động chỉ phụ thuộc vào kết quả của các hành
động được thực hiện trước đó và dữ liệu đầu vào. Nói một cách khác, với đầu vào như nhau
thuật toán sẽ cho đầu ra như nhau.
 Tính xác định: Mỗi bước hành động phải rõ ràng, không nhập nhằng và (người hoặc
máy) có thể thực hiện được.
 Tính tổng quát: Thuật toán phải áp dụng được cho một lớp các bài toán cùng loại
hoặc một bài toán với các đầu vào cụ thể khác nhau.
Ngoài ra đối với một thuật toán còn có các yêu cầu về tính đúng đắn và tính hiệu quả.
Mô tả thuật toán
Mô tả thuật toán là việc nêu ra các bước hành động cũng như trình tự thực hiện các
bước. Mô tả thuật toán là công việc cực kỳ quan trọng. Một mô tả tốt sẽ giúp người lập trình
hình dung rõ ràng và đúng đắn các việc phải làm.
Để mô tả một thuật toán ta có thể áp dụng một trong các cách sau:
 Dùng lưu đồ: Sử dụng hình vẽ mô tả tiến trình hoạt động của thuật toán. Cách mô tả
này có tính trực quan nhưng chỉ thích hợp với các thuật toán đơn giản.
 Dùng ngôn ngữ tự nhiên: Liệt kê bằng lời trình tự các bước cần thực hiện. Thông
thường cách mô tả này giúp hình dung thuật toán ở mức bao quát.
 Dùng giả mã (hay tựa Ngôn ngữ lập trình): Sử dụng các từ khóa cũng như các cấu
trúc điều khiển của ngôn ngữ lập trình (Pascal hoặc C chẳng hạn) để mô tả. Trong cách mô
tả này ta chỉ sử dụng các từ khóa và cấu trúc với ý nghĩa đã biết của ngôn ngữ lập trình
tương ứng chứ không hoàn toàn tuân thủ cú pháp của ngôn ngữ. Cách mô tả này cho phép
diễn đạt các hành động một cách chi tiết, cụ thể hơn. Khi dùng giả mã, để mô tả gọn ta sẽ bỏ
qua một số thao tác không cần thiết, chẳng hạn như có thể dùng các biến mà không cần khai báo.
Ví dụ để mô tả thuật toán tìm số lớn nhất trong một dãy số ta có thể có các mô tả như sau: - Mô tả 1:
Đầu vào: dãy a1, a2, ..., an 1
Đầu ra: x là giá trị lớn nhất trong dãy
Thuật toán: Xét lần lượt từng phần tử trong dãy kể từ đầu đến cuối dãy, với mỗi phần
tử trong dãy xác định x là giá trị lớn nhất (tạm thời) trong các phần tử đã xét cho tới thời điểm đó - Mô tả 2:
Đầu vào: dãy a[1], a[2], ..., a[n]
Đầu ra: x là giá trị lớn nhất trong dãy Thuật toán: float max(float a[],int n) { int i; float max;
// có thể bỏ qua khai báo này max=a[0]; for(i=1;if max=a[i]; } return max; }
 Dùng ngôn ngữ lập trình: Một chương trình chính là một bản mô tả chi tiết một thuật
toán bằng một ngôn ngữ lập trình cụ thể.
 Kết hợp giả mã với ngôn ngữ tự nhiên.
Ví dụ: Phần lớn các chương trình có dạng tổng quát sau:
Nhập một số dữ liệu đầu vào.
Thực hiện những tính toán nào đó.
Tạo ra một số đầu ra thích hợp.
Khi mô tả thuật toán ta thường coi dữ liệu đầu vào là có sẵn, tức là ta bỏ qua việc mô
tả các thao tác nhập dữ liệu đầu vào.
Trong tài liệu này chúng ta sử dụng cách mô tả các thuật toán bằng giả mã kết hợp với ngôn ngữ tự nhiên. 2
Một điểm cần lưu ý là với một thuật toán ta có thể mô tả nó ở nhiều mức độ khác nhau
tùy theo tình huống. Chẳng hạn ta có thể mô tả một thuật toán bằng một vài hành động mà
mỗi một hành động lại tương ứng với một thuật toán khác nào đó. Thông thường ta sẽ mô tả
một thuật toán qua nhiều mức, ngày càng chi tiết hơn hoặc mô tả chi tiết hơn một số hành
động nào đó nếu cần. Với một bản mô tả thuật toán đủ chi tiết thì việc viết chương trình chỉ
là việc chuyển đổi cách diễn đạt thuật toán hiện có sang một ngôn ngữ lập trình thích hợp.
Cũng cần phân biệt thuật toán và chương trình: Một chương trình sẽ được viết bằng
một ngôn ngữ lập trình cụ thể nào đó, do vậy chương trình phụ thuộc vào ngôn ngữ lập trình
(chẳng hạn giới hạn phạm vi của các kiểu dữ liệu của ngôn ngữ) và phụ thuộc vào các yêu
cầu phần cứng cụ thể (chẳng hạn giới hạn của bộ nhớ có thể sử dụng được, v.v.). Trong khi
đó một thuật toán không quan tâm tới ngôn ngữ lập trình cụ thể nào và chỉ quan tâm tới việc
diễn đạt các hành động cần thực hiện. Chính vì vậy khi cài đặt một thuật toán ta phải lưu ý
tới những hạn chế của ngôn ngữ lập trình được sử dụng. Một chương trình viết bằng một
ngôn ngữ lập trình (chẳng hạn C) chính là một bản mô tả thuật toán chi tiết bằng ngôn ngữ
lập trình đó, hay nói cách khác, lập trình chính là mô tả thuật toán bằng ngôn ngữ lập trình. 1.2.
Độ phức tạp tính toán và phân tích thuật toán.
Có nhiều cách tiếp cận khác nhau để đánh giá hiệu quả của một thuật toán nhằm chọn
lựa thuật toán thích hợp áp dụng trong thực tế. Chẳng hạn có thể xem xét thuật toán đòi hỏi
những gì về tài nguyên hệ thống (bộ nhớ) hoặc thuật toán có thể thực hiện trong một khoảng
thời gian chấp nhận được hay không. Ở đây chúng ta chỉ quan tâm tới độ phức tạp tính toán
tức là đánh giá thời gian thực hiện của thuật toán. Việc đánh giá thời gian thực hiện của
thuật toán được gọi là phân tích thuật toán.
Phân tích thuật toán là cần thiết vì những lý do sau:
 Việc phân tích thuật toán đáng tin cậy hơn là thực nghiệm. Nếu ta thực nghiệm (tức
là chạy thử chương trình), ta chỉ biết hành vi của một chương trình đối với những trường
hợp riêng lẻ, trong khi đó phân tích thuật toán cho ta biết về hiệu quả cho mọi đầu vào.
 Phân tích thuật toán giúp lựa chọn cách giải quyết trong số nhiều cách giải quyết đối
với bài toán. Một bài toán có thể có nhiều cách giải quyết khác nhau. Phân tích và so sánh 3
cẩn thận các thuật toán giúp quyết định thuật toán nào là thích hợp nhất với mục đích của
chúng ta mà không cần phải cài đặt và kiểm thử tất cả.
 Phân tích thuật toán giúp tiên đoán hiệu quả của một chương trình trước khi viết.
Điều này là rất quan trọng đối với những chương trình lớn và giúp chúng ta có thể phát hiện
và tập trung khắc phục những vấn đề làm chương trình kém hiệu quả.
Khi phân tích thuật toán ta sẽ quan tâm tới mối liên hệ giữa dữ liệu đầu vào (mà ta gọi
là kích thước đầu vào) với số lượng các thao tác cần thực hiện của thuật toán.
Kích thước đầu vào thường là một số nguyên dương n. Tuỳ theo tình huống cụ thể mà ta
coi cái gì là kích thước đầu vào. Chẳng hạn n có thể là số lượng các đối tượng của dữ liệu
đầu vào hoặc n có thể là kích thước của miền xác định của một đối tượng, v.v. Chẳng hạn
nếu dữ liệu đầu vào là một dãy n số nguyên thì ta có thể coi n là kích thước đầu vào, nếu
đầu vào là một ma trận 2 chiều mn thì kích thước đầu vào có thể coi là hai số nguyên dương m, n.
Một điều hiển nhiên là thuật toán phải thực hiện càng nhiều thao tác thì thời gian thực
hiện thuật toán càng lớn. Do vậy, ta sẽ coi số lượng các thao tác cơ bản cần thực hiện là
một hàm của kích thước đầu vào, ký hiệu là f(n), gọi là hàm thời gian chạy của thuật toán
(chương trình). Các thao tác cơ bản thường dùng là các phép toán số học và so sánh, phép
gán, thao tác đọc file và ghi file. Tuy nhiên với từng thuật toán, tùy theo tình huống ta sẽ
quan tâm tới một số thao tác cơ bản nhất định.
Việc tính chính xác hàm f(n) trong phần lớn trường hợp là rất khó và thực ra là không
cần thiết. Ta sẽ quan tâm tới tốc độ tăng của hàm f khi n tăng, hay nói khác đi ta muốn biết
mức độ tăng thời gian thực hiện thuật toán khi kích thước đầu vào tăng. Đặc biệt ta quan
tâm tới tình huống trường hợp tồi nhất (khi số lượng các thao tác cơ bản cần thực hiện là nhiều nhất).
Ký pháp O: Giả sử f, g là hai hàm N N, ta nói f có bậc cao nhất là g, và ký hiệu f(n) =
O(g(n)) nếu tồn tại hai hằng số C và k sao cho f(n) < Cg(n) với mọi n > k. Khi đó ta nói hàm
f có bậc (hay tốc độ tăng) không lớn hơn hàm g.
Ví dụ 1: Hàm T(n)=3n3+2n2 là O n
( 3) với k=0 và C=5. 4
Ta cũng có thể nói rằng T(n) = O(n4) nhưng phát biểu này yếu hơn
Ví dụ 2: Ta chứng minh rằng hàm 3n không là O(2n).
Giả sử tồn tại C và k sao cho 3n < C.2n với mọi n > k. Khi đó C>(3/2)n với mọi n>k.
Nhưng ta biết rằng (3/2)n tiến ra vô cùng khi n ra vô cùng. Mâu thuẫn.
Khi sử dụng ký pháp O ta đã bỏ qua các hằng số của bậc, điều này ám chỉ rằng ta quan
tâm tới những trường hợp mà kích thước đầu vào đủ lớn.
Giả sử ta có 2 thuật toán với 2 hàm thời gian chạy là f
1 và f2 tương ứng, và f1(n)=100n,
f2(n)=2n. Cả hai thuật toán của chúng ta giải quyết một trường hợp cụ thể mất 104 giây. Giả
sử nhờ cải thiện phần cứng ta có thể tăng tốc độ máy lên 10 lần. Khi đó với thuật toán f2 ta
có thể giải quyết bài toán với kích thước đầu vào tăng 30% với thời gian như cũ, trong khi
với thuật toán f1 ta có thể giải quyết bài toán với kích thước đầu vào tăng 1000% với thời
gian như cũ. Thực tế là máy tính ngày càng rẻ hơn và nhanh hơn, nhưng nhu cầu thực tế giải
quyết các bài toán với kích thước ngày càng lớn và càng phức tạp cũng tăng lên. Vì vậy việc
tìm ra và sử dụng các thuật toán có độ phức tạp tăng chậm ngày càng trở nên quan trọng hơn.
Một số tính chất của ký pháp O:
Quy tắc cộng: Giả sử T1(n) và T2(n) là thời gian chạy của 2 thuật toán P1 và P2,
T1(n)=O(f(n)) và T2(n)=O(g(n)). Khi đó thời gian chạy tuần tự 2 thuật toán P1 và P2 là
T1(n)+T2(n) = O(max(f(n),g(n))).
Thật vậy. giả sử C1, k1, C2, k2 là các hằng số sao cho với mọi n>k1 ta có T1(n)f(n)
và với mọi n>k2 có T2(n)g(n). Gọi k0=max(k1,k2), khi đó với mọi n>k0 ta có
T1(n)f(n) và T2(n)g(n).
Suy ra T1(n)+T2(n) < (C1+C2) max(f(n),g(n)).
Vậy T1(n) + T2(n) = O(max(f(n),g(n))).
Hay O(f(n))+O(g(n)) = O(max(f(n),g(n))).
Áp dụng quy tắc này khi đánh giá thời gian chạy của một thuật toán gồm các đoạn thực
hiện tuần tự, ta có thể coi thời gian chạy (hay độ phức tạp tính toán) của thuật toán bằng 5
thời gian chạy của đoạn chương trình có thời gian chạy lớn nhất.
Một nhận xét khác là nếu g(n) < f(n) với n đủ lớn thì O(f(n)+g(n))=O(f(n)), ví dụ
O(n3+n2)=O(n3). Vì vậy khi xem xét các hàm đánh giá thời gian chạy của thuật toán ta chỉ
quan tâm tới hạng tử bậc cao nhất.
Quy tắc nhân: Nếu T1(n)=O(f(n)) và T2(n)=O(g(n)) thì T1(n)T2(n)=O(f(n)g(n)). Từ quy tắc
này ta có O(c.f(n))=O(f(n)) với c là một hằng số.
Ví dụ: O(3n2)=O(n2).
Quy tắc này được sử dụng để đánh giá độ phức tạp của 2 đoạn chương trình lồng nhau.
Ví dụ: Giả sử có đoạn chương trình sau: For (i=1;i { For (j=1; j Các lệnh1; }
độ phức tạp của vòng for đầu tiên là O(f(n)) với vòng lặp trong được coi như một câu lệnh,
độ phức tạp của vòng lặp thứ hai là O(g(n)). Khi đó độ phức tạp của đoạn chương trình trên
sẽ là O(f(n).g(n))
Khi xác định hàm thời gian chạy của thuật toán ta thường ước tính số các thao tác cơ
bản như phép gán, thao tác đọc ghi hoặc các tính toán số học, các phép so sánh. Mỗi thao
tác cơ bản này thường được coi là thực hiện mất một đơn vị thời gian (mặc dù trong thực tế
việc thực hiện các thao tác này đòi hỏi thời gian khác nhau, chẳng hạn các thao tác đọc ghi
mất nhiều thời gian hơn cả, thực hiện phép nhân mất nhiều thời gian hơn thực hiện phép cộng,..).
Ví dụ: Đánh giá thời gian chạy của thuật toán sau void Vidu(int n); {
For (i=1; IFor (j=i+1; j<=n;j++) {
For (k=1; k<=j; k++) { printf(i+j+k); } } } } 6
Ta tính số lần thực hiện printf. Với mỗi j chạy từ i+1 đến n, printf được thực hiện j lần, do đó
với mỗi i (chạy từ 1 đến n-1) số lần thực hiện printf là (i+1)+(i+2)+..+n = (n+i+1).(n-i)/2.
Vậy tổng số lần thực hiện printf là :
(n+2).(n-1)/2+(n+3)(n-2)/2+…+2n/2 = O(n3).
Trong một số tình huống khác, khi ta ước lượng được số tối đa các thao tác cơ bản cần
thực hiện trong mỗi bước lặp, thì để cho việc tính độ phức tạp đơn giản hơn, ta có thể tính
hàm thời gian chạy bằng cách đếm số lần lặp. 1.3.
Vấn đề lựa chọn thuật toán để cài đặt.
Với một bài toán có thể áp dụng nhiều thuật toán khác nhau để giải quyết. Khi đó nảy
sinh vấn đề nên lựa chọn sử dụng thuật toán nào.
Có 2 tiêu chuẩn quan trọng để lựa chọn một thuật toán: tính đơn giản và tính hiệu quả.
Thuật toán đơn giản là thuật toán dễ hiểu, dễ cài đặt và dễ bảo trì, tuy vậy các thuật toán đơn
giản thường kém hiệu quả. Ngược lại một thuật toán hiệu quả thường là phức tạp, vì vậy
khó cài đặt cũng như khó bảo trì.
Khi viết một chương trình không đòi hỏi tính hiệu quả hoặc số lần sử dụng ít, người ta
thường ưu tiên chọn những thuật toán đơn giản. Trong những tình huống như thế này lợi ích
thực tế do tính hiệu quả mang lại có thể không đáng kể so với chi phí cài đặt hoặc do số lần sử dụng quá ít.
Một khi chương trình được sử dụng nhiều cũng như yêu cầu thực tế về hiệu quả (chẳng
hạn đòi hỏi về thời gian thực hiện chương trình càng nhỏ càng tốt như thường gặp với các
ứng dụng thời gian thực), thì lúc này các thuật toán hiệu quả được ưu tiên lựa chọn. Khi đó
những chi phí cài đặt sẽ được bù lại bởi lợi ích thu được mỗi lần chạy chương trình nhân với
số lần chạy chương trình (có thể rất lớn).
Ví dụ: Giả sử cần viết một chương trình dùng trong một thời gian ngắn (10 lần trong
10 ngày chẳng hạn). Có hai thuật toán, thuật toán đơn giản có thể cài đặt trong 2 giờ, mỗi
lần thực hiện chương trình tương ứng chạy trong 1 giờ. Thuật toán hiệu quả, do phức tạp
(khó thể hiện thuật toán, mất nhiều thời gian sửa các lỗi phát sinh) nên thời gian cài đặt là 2
ngày (có thể lâu hơn), tuy nhiên mỗi lần chạy chương trình tương ứng mất 1 giây. Xét về 7
thời gian dành cho viết và sử dụng chương trình, đối với thuật toán đơn giản là 12 giờ còn
đối với thuật toán hiệu quả là 2 ngày. Nhìn ở góc độ này thì nên ưu tiên chọn thuật toán đơn
giản. Tuy nhiên nếu như chương trình được sử dụng nhiều hơn, chẳng hạn khoảng 2400 lần
thì lúc này đối với thuật toán đơn giản thời gian dành cho viết và sử dụng chương trình là
khoảng 100 ngày, trong khi đó đối với chương trình hiệu quả chỉ là hơn 2 ngày. Trong tình
huống này nên ưu tiên chọn thuật toán hiệu quả. 1.4 BÀI TẬP
1. Thuật toán sau tính giá trị của một đa thức bậc n với các hệ số a[0], a[1],…, a[n]
ứng với giá trị x cho trước.
float Tinhdt(float a[],int n); { P=0; For (k=0; k<= n;k++) { T=a[k];
For (j=1; j<=k;j++) { T=T*x;} P=P+T; } Return P; }
Thuật toán phải thực hiện bao nhiêu phép cộng? Bao nhiêu phép nhân?
2. Dùng ký pháp O, tính thời gian chạy tồi nhất của các thuật toán sau:
a/ void Dg1(float a[], b[],c[];int n); b/ void Dg2(int n); { For (i=1;i<=n;i++) { { x=0; y=0; For (j=1;j<=n;j++) { For (i=1;i<=n;i++) { c[i,j]=0; If (i % 2 ==1) { For (k=1;k<=n;k++) {
For (j=i;j<=n;j++) {x=x+1;} c[i,j]=c[i,j]+a[i,k]*b[k,j]; } } For (j= ;j<=i;j++) {y=y+1; 1 } } } }
Có thể nói gì về giá trị của các biến x và y
Có thể nói gì về thuật toán này?
khi kết thúc thuật toán? Có cách nào làm
giảm độ phức tạp của thuật toán trên hay không? 8
2. MỘT SỐ THUẬT TOÁN CƠ BẢN. 2.1.
Các thuật toán sắp xếp sơ cấp.
Sắp xếp là một bài toán thường gặp, ngoài ý nghĩa tổ chức lại dữ liệu theo một yêu cầu
nào đó, việc sắp xếp còn tạo thuận lợi cho việc tìm kiế . m
Ta sẽ quan tâm tới việc sắp xếp các bản ghi trong một file có kích thước nhỏ, mỗi bản
ghi chứa một trường khóa key dùng làm tiêu chuẩn để sắp xếp. Các bản ghi sẽ được sắp xếp
sao cho trường khóa của chúng được sắp xếp theo một thứ tự nào đó xác định trước.
Nếu kích thước file nhỏ ta có thể sao nó ra một mảng và thực hiện việc sắp xếp trên
mảng. Sắp xếp mảng còn được gọi là sắp xếp trong. Việc sắp xếp file trên đĩa được gọi là
sắp xếp ngoài. Khi sắp xếp mảng các bản ghi được truy nhập trực tiếp, còn với sắp xếp
ngoài các bản ghi được truy nhập tuần tự nên việc sắp xếp gặp nhiều khó khăn hơn. Ở đây ta
sẽ xem xét các thuật toán sắp xếp mảng. Các phương pháp sắp xếp ngoài sẽ được xem xét
trong giáo trình Cấu trúc dữ liệu.
Kích thước dữ liệu đầu vào cho các phương pháp sắp xếp mảng là kích thước n của
mảng (tức là số phần tử mảng).
Để thuận tiện cho việc trình bày cũng như tập trung vào thuật toán ta sẽ làm việc với
mảng đơn giản gồm các số nguyên.
Các phương pháp sắp xếp mảng cơ bản: Có nhiều phương pháp sơ cấp sắp xếp mảng,
ta sẽ tìm hiểu 3 phương pháp cơ bản là sắp xếp chèn, sắp xếp chọn và sắp xếp đổi chỗ. Một
đặc trưng cần lưu ý của các phương pháp sắp xếp là tính ổn địn .
h Một phương pháp sắp xếp
được gọi là ổn định nếu như nó giữ nguyên thứ tự ban đầu của các phần tử giống nhau.
Đối với các thuật toán được xét ở đây chúng ta sẽ quan tâm tới việc sắp xếp mảng
A[0..n-1] các số nguyên theo thứ tự tăng dần của trường khóa. Việc sắp xếp mảng giảm dần
hoàn toàn tương tự (với một chút thay đổi thích hợp). 9 a/ Sắp xếp chèn
Có thể mô tả ngắn gọn như sau For i=1 to n-1 do
Chèn A[i] vào vị trí thích hợp trong các phần tử A[0],…, A[i-1]
Trong phương pháp này, ở bước thứ i ta có các phần tử từ A[0] đến A[i-1] đã được sắp
thứ tự. Để chèn A[i] vào vị trí thích hợp trong các phần tử A[0],…, A[i-1] ta sẽ tìm vị trí j
nhỏ nhất thỏa mãn A[i] < A[j] và chèn A[i] vào vị trí j. Khi đó các phần tử từ vị trí j đến vị
trí i-1 sẽ dịch sang phải 1 vị trí. Trong quá trình tìm vị trí j ta có thể đồng thời dịch các phần
tử lớn hơn A[i] sang phải một vị trí. Mô tả chi tiết như sau: void SXChen(int a[],int n); { For (i 1;i= x=A[i]; j=i-1;
While ((j>=0) && (x A[j+1] =x; } }
Với mỗi i, vòng lặp While dừng lại khi j<0 hoặc khi j>=0 và x >= A[j]. Nếu j=-1 có
nghĩa là x được xếp vào đầu mảng (vị trí j+1). Nếu j>-1 thì x được xếp vào sau vị trí j.
Ví dụ: Giả sử mảng đã cho là A = (3, 6, 2, 8, 4, 5). Trong quá trình sắp thứ tự theo thuật
toán sắp xếp chèn, mảng biến đổi như sau (j nhận giá trị sau khi kết thúc vòng lặp While): i=1 x=6 j=0 3, 6, 2, 8, 4, 5 i=2 x=2 j=-1 2, 3, 6, 8, 4, 5 i=3 x=8 j=2 2, 3, 6, 8, 4, 5 i=4 x=4 j=1 2, 3, 4, 6, 8, 5 i=5 x=5 j=2 2, 3, 4, 5, 6, 8,
b/ Sắp xếp chọn: có thể mô tả ngắn gọn như sau For i=0 to n-2 do 10
Chọn phần tử nhỏ nhất chưa đúng vị trí và đặt nó vào vị trí i
Khi sử dụng phương pháp sắp xếp chọn, ở bước thứ i ta giả thiết các vị trí từ 0 đến i-1
trong mảng đã chọn được các phần tử đúng vị trí. Ta chọn phần tử nhỏ nhất chưa đúng vị trí
nằm trong khoảng từ vị trí i đến vị trí n-1 và sắp nó vào vị trí i. Mô tả chi tiết: void SXChon(int a[],int n); { For (i=0;i< -1,i++) { n min=i;
For (j=i+1;jIf (A[j] < A[min]) min= j; //phần tử tại vị trí min là nhỏ nhất chưa được sắp } Hoán vị (A[i], A[min]) }}
Ví dụ: Giả sử mảng đã cho là A = (3, 6, 2, 8, 4, 5). Trong mỗi dòng dưới đây là tình
trạng của mảng sau khi kết thúc một vòng lặp ứng với i i=0 2, 6, 3, 8, 4, 5 i=1 2, 3, 6, 8, 4, 5 i=2 2, 3, 4, 8, 6, 5 i=3 2, 3, 4, 5, 6, 8 i=4 2, 3, 4, 5, 6, 8
c/ Sắp xếp nổi bọt: Ta sẽ so sánh và đổi chỗ của hai phần tử liền nhau đứng không đúng
vị trí (phần tử lớn hơn đứng trước phần tử nhỏ hơn) cho tới khi tất cả các phần tử được sắp
thứ tự. Trong quá trình đổi chỗ các phần tử lớn di chuyển về cuối mảng và các phần tử nhỏ
di chuyển về đầu mảng. Mô tả chi tiết:
void SXNoibot(int a[],int n); { For (i=n-1;i>0;i- ) { - For (j 1;j<=i;j++) { = 11 If (A[j-1] > A[j]) {Hoán -1], A[j]) vị (A[j } }} }
Sau lần duyệt đầu tiên, phần tử lớn nhất trong mảng được đưa về cuối mảng. Tương tự,
sau mỗi lần thực hiện vòng lặp For với i không còn phần tử nào nhỏ hơn A[i] đứng sau nó.
Ví dụ: Giả sử mảng đã cho là A = (4, 6, 3, 8, 2, 5). Trong mỗi dòng dưới đây là tình
trạng của mảng sau khi kết thúc một vòng lặp ứng với i i=5 4, 3, 6, 2, 5, 8 i=4 3, 4, 2, 5, 6, 8 i=3 3, 2, 4, 5, 6, 5 i=2 2, 3, 4, 5, 8, 6 i=1 2, 3, 4, 5, 6, 8
Ngoài ra có phương pháp sắp xếp đếm, nội dung của phương pháp này là đếm số phần
tử nhỏ hơn hoặc bằng A[i]. Nếu có j phần tử nhỏ hơn hoặc bằng A[i] thì A[i] sẽ có vị trí thứ
j+1 trong dãy đã sắp thứ tự. Khi đếm các phần tử bằng A[i] ta chỉ đếm những phần tử đi
trước nó để đảm bảo các số đếm là khác nhau. Mô tả: void SXDem(int a[],int n); { For (i 0;i= For (i=n-1;i>0;i- ) { - For (j=i-1;j>=0;j- ) { -
If (a[i] < a[j]) { Count[j]++; } Else { Count[i]++;} } } For (i 0;i= { s[Count[ i]+1]=a[i];} Return s; }
Thủ tục này trả lại s là mảng các phần tử của A đã sắp thứ tự.
Ví dụ: Giả sử mảng đã cho là A = (2, 6, 4, 8, 3, 5). Trong mỗi dòng dưới đây là tình 12
trạng của mảng Count sau khi kết thúc một vòng lặp ứng với i i=5 0, 1, 0, 1, 0, 3 i=4 0, 2, 1, 2, 1, 3 i=3 0, 2, 1, 5, 1, 3 i=2 0, 3, 2, 5, 1, 3 i=1 0, 4, 2, 5, 1, 3
Ta có mảng s như sau: (2, 3, 4, 5, 6, 8) 13 BÀI TẬP
1. Đánh giá độ phức tạp trong trường hợp tồi nhất của các thuật toán sắp xếp sơ cấp đã nêu.
2. Trong các thuật toán sắp xếp sơ cấp trên, thuật toán nào có tính ổn định? Giải thích.
3. Chạy từng bước các thuật toán sắp xếp đã nêu trên các mảng cụ thể có kích thước 10.
4. Mô tả một thuật toán thích hợp sắp xếp một mảng các bit. Cho biết độ phức tạp
của thuật toán được sử dụng. 14 2.3.
Các thuật toán tìm kiếm sơ cấp trên mảng.
Tìm kiếm là một thao tác đóng vai trò quan trọng trong nhiều tính toán và được áp dụng
nhiều trong thực tế. Có nhiều yêu cầu tìm kiếm khác nhau cũng như có nhiều thuật toán tìm
kiếm khác nhau. Ta sẽ quan tâm tới một số thuật toán tìm kiếm sơ cấp trên mảng. Bài toán
đặt ra là tìm một phần tử trong mảng A[0..n-1] cho trước, có giá trị bằng T cho trước. Có thể
xét bài toán tổng quát hơn là tìm một phần tử trong mảng A[0..n-1] cho trước có tính chất P cho trước
a. Tìm tuần tự: Để tìm kiếm tuần tự một phần tử x cho trước trong mảng A ta sử dụng
một vòng lặp, tại mỗi bước của vòng lặp ta thao tác với một phần tử xác định của mảng, ở
đây cụ thể là so sánh lần lượt mỗi phần tử của mảng với x (hay kiểm tra xem phần tử tương
ứng có tính chất P hay không). Thao tác này được gọi là duyệt mảng. Việc duyệt mảng được
dừng lại khi bắt gặp một phần tử bằng x hoặc đã so sánh hết các phần tử của mảng. Khi gặp
một phần tử bằng x (hay có tính chất P) ta sẽ ghi nhận sự kiện này.
Mô tả: Duyệt (so sánh mỗi phần tử mảng với x) toàn bộ mảng cho tới khi gặp một phần
tử bằng x hoặc đã duyệt hết mảng.
int timtuantu(int a[], int n, int x ) { int i=0; while(i { if(i; else return 0; i++; } }
Trong trường hợp tổng quát, điều kiện If a[i]== x được thay bằng If a[i] có tính chất P. 15
b. Tìm nhị phân: Trong tình huống A là mảng sắp thứ tự ta có thuật toán tìm kiếm tốt
hơn tìm tuần tự, đó là tìm kiếm nhị phân. Ý tưởng của thuật toán tìm nhị phân là ta so sánh x
với phần tử ở giữa mảng A, dựa vào kết quả so sánh mà kết thúc hoặc tiếp tục tìm kiếm
bằng cách thu hẹp phạm vi tìm kiếm còn bằng một nửa phạm vi trước đó. Quá trình này
được thực hiện lặp đi lặp lại cho tới khi gặp một phần tử bằng x hoặc phạm vi tìm kiếm là rỗng.
Mô tả thuật toán: Giả sử A[0..n-1] là mảng sắp thứ tự tăng
int timnhiphan(int a[], int n, int x ) { int g=-1; int vt=-1;
int d=0; int c=n-1; // d là đầu phạm vi, c là cuối phạm vi tìm While (d<=c) { g=(d+c) / 2; If (x==A[g]) { vt=g; break;} Else If ( < A[g]) { c x
=g-1;} // tiếp tục tìm ở nửa trái phạm vi
Else {d=g+1;} // tiếp tục tìm ở nửa phải phạm vi } Return vt; }
Nếu x < A[g] thì với mọi chỉ số k > g ta có x < A[g] < A[k] (do mảng sắp thứ tự tăng),
do đó ta chỉ cần tìm x trong mảng ứng với các chỉ số k < g. Lúc này ta thu hẹp phạm vi tìm
kiếm bằng cách xác định lại vị trí cuối của phạm vi là g-1.
Nếu x > A[g] thì ta thực hiện một hành động tương tự là tìm x trong mảng ứng với các
chỉ số k > g. Lúc này ta thu hẹp phạm vi tìm kiếm bằng cách xác định lại vị trí đầu của phạm vi là g+1.
Phạm vi là rỗng khi d > c.
Ví dụ: Giả sử A = (1, 6, 14, 17, 22, 25, 25, 30,45)
- Với x = 14 ta có các bước tìm kiếm được thể hiện như sau
Trước khi vào vòng lặp: d=0, c=8, g=-1, vt=-1 16 Sau lần lặp g A[g] d c 1 4 22 0 3 2 1 6 2 3 3 2 14
Kết luận giá trị x có trong mảng tại vị trí thứ 2.
- Với x = 50 ta có các bước tìm kiếm được thể hiện như sau
Trước khi vào vòng lặp: d=0, c=8, g=-1, vt=-1 Sau lần lặp g A[g] d c 1 4 22 5 8 2 6 25 7 8 3 7 30 8 8 4 8 45 9 8
Lúc này d > c và vòng lặp dừng.
Kết luận giá trị x không có trong mảng vì giá trị của biến vt=-1. 17 2.4. BÀI TẬP
1. Đánh giá độ phức tạp của các thuật toán tìm kiếm sơ cấp
2. Mô tả thuật toán Tìm phần tử lớn thứ nhì trong một dãy tùy ý có n phần tử và
đánh giá độ phức tạp của thuật toán. (Lưu ý: phần tử lớn thứ nhì có thể không tồn tại)
3. Chạy từng bước thuật toán tìm nhị phân trên một mảng cụ thể có 16 phần tử, xét
hai trường hợp: phần tử cần tìm có trong mảng và không có trong mảng.
4. Mô tả một thuật toán Tìm phần tử xuất hiện nhiều lần nhất trong một dãy tùy ý có
n phần tử và đánh giá độ phức tạp của thuật toán đã mô tả. 18 2.5. Đệ quy
2.5.1. Thuật toán đệ quy.
Các thuật toán đệ quy đóng vai trò quan trọng trong việc giải quyết nhiều bài toán. Một
thuật toán đệ quy là thuật toán có yêu cầu thực hiện lại chính thuật toán đó với mức độ dữ
liệu thấp hơn. Các thuật toán đệ quy có liên quan chặt chẽ với các định nghĩa đệ quy hoặc các quan hệ truy hồi.
Một thuật toán đệ quy gồm 2 phần:
Phần cơ sở: là các trường hợp không cần thực hiện lại thuật toán.
Phần đệ quy: là các trường hợp yêu cầu thực hiện lại thuật toán.
2.5.2. Một số bài toán
Bài toán 1: Tìm ước số chung lớn nhất (ƯCLN) của hai số tự nhiên a và b cho trước.
Có nhiều thuật toán khác nhau để giải bài toán này, ở đây ta sử dụng một tính chất của
ƯCLN là: nếu a > b thì ƯCLN(a,b)=ƯCLN(a-b,b). Thuật toán được mô tả như sau: int Ucln(int a,int b); { // gỉả thiết b<>0
If (a==b||b==1) { return b;} // phần cơ sở Else { // phần đệ quy
If (at=a; a=b; b=t; // đổi vai trò a, b để luôn có a >= b return ucln(a-b,b); } } }
Bài toán 2: Định nghĩa các số Fibbonacci như sau: f =1, =1, 0 f1
fn=fn-1+fn-2 với n>1. Tính f với cho trước. n n
Thuật toán đệ quy sử dụng ngay định nghĩa đệ quy của các số Fibbonacci, vì thế thuật
toán chỉ là diễn đạt lại định nghĩa. int Fib(int n); { If (n== || n=1) 0 { return 1;} return Fib(n-1)+Fib(n-2); } 19