THUẬT TOÁN

Lượt xem: 130,616Lượt tải: 3Số trang: 18

Mô tả tài liệu

Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.

Tóm tắt nội dung

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 4 CHƯƠNG I: THUẬT TOÁN 1.1. KHÁI NIỆM THUẬT TOÁN. 1.1.1. Mở ñầu: Có nhiều lớp bài toán tổng quát xuất hiện trong toán học rời rạc. Chẳng hạn, cho một dãy các số nguyên, tìm số lớn nhất; cho một tập hợp, liệt kê các tập con của nó; cho tập hợp các số nguyên, xếp chúng theo thứ tự tăng dần; cho một mạng, tìm ñường ñi ngắn nhất giữa hai ñỉnh của nó. Khi ñược giao cho một bài toán như vậy thì việc ñầu tiên phải làm là xây dựng một mô hình dịch bài toán ñó thành ngữ cảnh toán học. Các cấu trúc rời rạc ñược dùng trong các mô hình này là tập hợp, dãy, hàm, hoán vị, quan hệ, cùng với các cấu trúc khác như ñồ thị, cây, mạng - những khái niệm sẽ ñược nghiên cứu ở các chương sau. Lập ñược một mô hình toán học thích hợp chỉ là một phần của quá trình giải. ðể hoàn tất quá trình giải, còn cần phải có một phương pháp dùng mô hình ñể giải bài toán tổng quát. Nói một cách lý tưởng, cái ñược ñòi hỏi là một thủ tục, ñó là dãy các bước dẫn tới ñáp số mong muốn. Một dãy các bước như vậy, ñược gọi là một thuật toán. Khi thiết kế và cài ñặt một phần mềm tin học cho một vấn ñề nào ñó, ta cần phải ñưa ra phương pháp giải quyết mà thực chất ñó là thuật toán giải quyết vấn ñề này. Rõ ràng rằng, nếu không tìm ñược một phương pháp giải quyết thì không thể lập trình ñược. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. 1.1.2. ðịnh nghĩa: Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác ñịnh nhằm giải một bài toán ñã cho. Thuật ngữ “Algorithm” (thuật toán) là xuất phát từ tên nhà toán học Ả Rập Al- Khowarizmi. Ban ñầu, từ algorism ñược dùng ñể chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau ñó, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng ñối với các máy tính, khái niệm thuật toán ñã ñược cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác ñịnh ñể giải các bài toán, chứ không phải chỉ là thủ tục ñể thực hiện các phép tính số học. Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu ñồ (sơ ñồ khối), ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ngữ lập trình thì chỉ những lệnh ñược phép trong ngôn ngữ ñó mới có thể dùng ñược và ñiều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu. Hơn nữa, vì nhiều ngôn ngữ lập trình ñều ñược dùng rộng rãi, nên chọn một ngôn ngữ ñặc biệt nào ñó là ñiều người ta không muốn. Vì vậy ở ñây các thuật toán ngoài việc ñược trình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã ñể mô tả thuật http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 5 toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán ñó trong ngôn ngữ lập trình. Các bước của thuật toán ñược chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình. Thí dụ 1: Mô tả thuật 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. a) Dùng ngôn ngữ tự nhiên ñể mô tả các bước cần phải thực hiện: 1. ðặt giá trị cực ñại tạm thời bằng số nguyên ñầu tiên trong dãy. (Cực ñại tạm thời sẽ là số nguyên lớn nhất ñã ñược kiểm tra ở một giai ñoạn nào ñó của thủ tụ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 ñó. 3. Lặp lại bước trước nếu còn các số nguyên trong dãy. 4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực ñại tạm thời ở ñiểm này chính là số nguyên lớn nhất của dãy. b) Dùng ñoạn giả mã: procedure max (a1, a2, ..., an: integers) max:= a1 for i:= 2 to n if max <ai then max:= ai {max là phần tử lớn nhất} Thuật toán này trước hết gán số hạng ñầu tiên a1 của dãy cho biến max. Vòng lặp “for” ñược dùng ñể kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nó ñược gán làm giá trị mới của max. 1.1.3. Các ñặc trưng của thuật toán: -- ðầu vào (Input): Một thuật toán có các giá trị ñầu vào từ một tập ñã ñược chỉ rõ. -- ðầu ra (Output): Từ mỗi tập các giá trị ñầu vào, thuật toán sẽ tạo ra các giá trị ñầu ra. Các giá trị ñầu ra chính là nghiệm của bài toán. -- Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. -- Tính xác ñịnh: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn, trong cùng một ñiều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. -- Tính hiệu quả: Trước hết thuật toán cần ñúng ñắn, nghĩa là sau khi ñưa dữ liệu vào thuật toán hoạt ñộng và ñưa ra kết quả như ý muốn. -- Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các ñầu vào là các bộ dữ liệu khác nhau trong một miền xác ñịnh. 1.2. THUẬT TOÁN TÌM KIẾM. 1.2.1. Bài toán tìm kiếm: Bài toán xác ñịnh vị trí của một phần tử trong một bảng liệt kê sắp thứ tự thường gặp trong nhiều trường hợp khác nhau. Chẳng hạn chương trình http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 6 kiểm tra chính tả của các từ, tìm kiếm các từ này trong một cuốn từ ñiển, mà từ ñiển chẳng qua cũng là một bảng liệt kê sắp thứ tự của các từ. Các bài toán thuộc loại này ñược gọi là các bài toán tìm kiếm. Bài toán tìm kiếm tổng quát ñược mô tả như sau: xác ñịnh vị trí của phần tử x trong một bảng liệt kê các phần tử phân biệt a1, a2, ..., an hoặc xác ñịnh rằng nó không có mặt trong bảng liệt kê ñó. Lời giải của bài toán trên là vị trí của số hạng của bảng liệt kê có giá trị bằng x (tức là i sẽ là nghiệm nếu x=ai và là 0 nếu x không có mặt trong bảng liệt kê). 1.2.2. Thuật toán tìm kiếm tuyến tính: Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt ñầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi x≠a1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi x≠a2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm ñược số hạng bằng x, khi ñó nghiệm là vị trí của số hạng ñó. Nếu toàn bảng liệt kê ñã ñược kiểm tra mà không xác ñịnh ñược vị trí của x, thì nghiệm là 0. Giả mã ñối với thuật toán tìm kiếm tuyến tính ñược cho dưới ñây: procedure tìm kiếm tuyến tính (x: integer, a1,a2,...,an: integers phân biệt) i := 1 while (i ≤ n and x ≠ ai) i := i + 1 if i ≤ n then location := i else location := 0 {location là chỉ số dưới của số hạng bằng x hoặc là 0 nếu không tìm ñược x} 1.2.3. Thuật toán tìm kiếm nhị phân: Thuật toán này có thể ñược dùng khi bảng liệt kê có các số hạng ñược sắp theo thứ tự tăng dần. Chẳng hạn, nếu các số hạng là các số thì chúng ñược sắp từ số nhỏ nhất ñến số lớn nhất hoặc nếu chúng là các từ hay xâu ký tự thì chúng ñược sắp theo thứ tự từ ñiển. Thuật toán thứ hai này gọi là thuật toán tìm kiếm nhị phân. Nó ñược tiến hành bằng cách so sánh phần tử cần xác ñịnh vị trí với số hạng ở giữa bảng liệt kê. Sau ñó bảng này ñược tách làm hai bảng kê con nhỏ hơn có kích thước như nhau, hoặc một trong hai bảng con ít hơn bảng con kia một số hạng. Sự tìm kiếm tiếp tục bằng cách hạn chế tìm kiếm ở một bảng kê con thích hợp dựa trên việc so sánh phần tử cần xác ñịnh vị trí với số hạng giữa bảng kê. Ta sẽ thấy rằng thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm tuyến tính. Thí dụ 2. ðể tìm số 19 trong bảng liệt kê 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 ta tách bảng liệt kê gồm 16 số hạng này thành hai bảng liệt kê nhỏ hơn, mỗi bảng có 8 số hạng, cụ thể là: 1,2,3,5,6,7,8,10 và 12,13,15,16,18,19,20,22. Sau ñó ta so sánh 19 với số hạng cuối cùng của bảng con thứ nhất. Vì 10<19, việc tìm kiếm 19 chỉ giới hạn trong bảng liệt kê con thứ 2 từ số hạng thứ 9 ñến 16 trong bảng liệt kê ban ñầu. Tiếp theo, ta http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 7 lại tách bảng liệt kê con gồm 8 số hạng này làm hai bảng con, mỗi bảng có 4 số hạng, cụ thể là 12,13,15,16 và 18,19,20,22. Vì 16<19, việc tìm kiếm lại ñược giới hạn chỉ trong bảng con thứ 2, từ số hạng thứ 13 ñến 16 của bảng liệt kê ban ñầu. Bảng liệt kê thứ 2 này lại ñược tách làm hai, cụ thể là: 18,19 và 20,22. Vì 19 không lớn hơn số hạng lớn nhất của bảng con thứ nhất nên việc tìm kiếm giới hạn chỉ ở bảng con thứ nhất gồm các số 18,19, là số hạng thứ 13 và 14 của bảng ban ñầu. Tiếp theo bảng con chứa hai số hạng này lại ñược tách làm hai, mỗi bảng có một số hạng 18 và 19. Vì 18<19, sự tìm kiếm giới hạn chỉ trong bảng con thứ 2, bảng liệt kê chỉ chứa số hạng thứ 14 của bảng liệt kê ban ñầu, số hạng ñó là số 19. Bây giờ sự tìm kiếm ñã thu hẹp về chỉ còn một số hạng, so sánh tiếp cho thấy19 là số hạng thứ 14 của bảng liệt kê ban ñầu. Bây giờ ta có thể chỉ rõ các bước trong thuật toán tìm kiếm nhị phân. ðể tìm số nguyên x trong bảng liệt kê a1,a2,...,an với a1 < a2 < ... < an, ta bắt ñầu bằng việc so sánh x với số hạng am ở giữa của dãy, với m=[(n+1)/2]. Nếu x > am, việc tìm kiếm x giới hạn ở nửa thứ hai của dãy, gồm am+1,am+2,...,an. Nếu x không lớn hơn am, thì sự tìm kiếm giới hạn trong nửa ñầu của dãy gồm a1,a2,...,am. Bây giờ sự tìm kiếm chỉ giới hạn trong bảng liệt kê có không hơn [n/2] phần tử. Dùng chính thủ tục này, so sánh x với số hạng ở giữa của bảng liệt kê ñược hạn chế. Sau ñó lại hạn chế việc tìm kiếm ở nửa thứ nhất hoặc nửa thứ hai của bảng liệt kê. Lặp lại quá trình này cho tới khi nhận ñược một bảng liệt kê chỉ có một số hạng. Sau ñó, chỉ còn xác ñịnh số hạng này có phải là x hay không. Giả mã cho thuật toán tìm kiếm nhị phân ñược cho dưới ñây: procedure tìm kiếm nhị phân (x: integer, a1,a2,...,an: integers tăng dần) i := 1 {i là ñiểm mút trái của khoảng tìm kiếm} j := n {j là ñiểm mút phải của khoảng tìm kiếm} while i < j begin m:= [(i+j)/2] if x>am then i:=m+1 else j := m end if x = ai then location := i else location := 0 {location là chỉ số dưới của số hạng bằng x hoặc 0 nếu không tìm thấy x} 1.3. ðỘ PHỨC TẠP CỦA THUẬT TOÁN. 1.3.1. Khái niệm về ñộ phức tạp của một thuật toán: Thước ño hiệu quả của một thuật toán là thời gian mà máy tính sử dụng ñể giải bài toán theo thuật toán ñang xét, khi các giá trị ñầu vào có một kích thước xác ñịnh. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 8 Một thước ño thứ hai là dung lượng bộ nhớ ñòi hỏi ñể thực hiện thuật toán khi các giá trị ñầu vào có kích thước xác ñịnh. Các vấn ñề như thế liên quan ñến ñộ phức tạp tính toán của một thuật toán. Sự phân tích thời gian cần thiết ñể giải một bài toán có kích thước ñặc biệt nào ñó liên quan ñến ñộ phức tạp thời gian của thuật toán. Sự phân tích bộ nhớ cần thiết của máy tính liên quan ñến ñộ phức tạp không gian của thuật toán. Vệc xem xét ñộ phức tạp thời gian và không gian của một thuật toán là một vấn ñề rất thiết yếu khi các thuật toán ñược thực hiện. Biết một thuật toán sẽ ñưa ra ñáp số trong một micro giây, trong một phút hoặc trong một tỉ năm, hiển nhiên là hết sức quan trọng. Tương tự như vậy, dung lượng bộ nhớ ñòi hỏi phải là khả dụng ñể giải một bài toán,vì vậy ñộ phức tạp không gian cũng cần phải tính ñến.Vì việc xem xét ñộ phức tạp không gian gắn liền với các cấu trúc dữ liệu ñặc biệt ñược dùng ñể thực hiện thuật toán nên ở ñây ta sẽ tập trung xem xét ñộ phức tạp thời gian. ðộ phức tạp thời gian của một thuật toán có thể ñược biểu diễn qua số các phép toán ñược dùng bởi thuật toán ñó khi các giá trị ñầu vào có một kích thước xác ñịnh. Sở dĩ ñộ phức tạp thời gian ñược mô tả thông qua số các phép toán ñòi hỏi thay vì thời gian thực của máy tính là bởi vì các máy tính khác nhau thực hiện các phép tính sơ cấp trong những khoảng thời gian khác nhau. Hơn nữa, phân tích tất cả các phép toán thành các phép tính bit sơ cấp mà máy tính sử dụng là ñiều rất phức tạp. Thí dụ 3: Xét thuật toán tìm số lớn nhất trong dãy n số a1, a2, ..., an. Có thể coi kích thước của dữ liệu nhập là số lượng phần tử của dãy số, tức là n. Nếu coi mỗi lần so sánh hai số của thuật toán ñòi hỏi một ñơn vị thời gian (giây chẳng hạn) thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây. Với dãy 64 số, thời gian thực hiện thuật toán nhiều lắm là 63 giây. Thí dụ 4:Thuật toán về trò chơi “Tháp Hà Nội” Trò chơi “Tháp Hà Nội” như sau: Có ba cọc A, B, C và 64 cái ñĩa (có lỗ ñể ñặt vào cọc), các ñĩa có ñường kính ñôi một khác nhau. Nguyên tắc ñặt ñĩa vào cọc là: mỗi ñĩa chỉ ñược chồng lên ñĩa lớn hơn nó. Ban ñầu, cả 64 ñĩa ñược ñặt chồng lên nhau ở cột A; hai cột B, C trống. Vấn ñề là phải chuyển cả 64 ñĩa ñó sang cột B hay C, mỗi lần chỉ ñược di chuyển một ñĩa. Xét trò chơi với n ñĩa ban ñầu ở cọc A (cọc B và C trống). Gọi Sn là số lần chuyển ñĩa ñể chơi xong trò chơi với n ñĩa. Nếu n=1 thì rõ ràng là S1=1. Nếu n>1 thì trước hết ta chuyển n-1 ñĩa bên trên sang cọc B (giữ yên ñĩa thứ n ở dưới cùng của cọc A). Số lần chuyển n-1 ñĩa là Sn-1. Sau ñó ta chuyển ñĩa thứ n từ cọc A sang cọc C. Cuối cùng, ta chuyển n-1 ñĩa từ cọc B sang cọc C (số lần chuyển là Sn-1). Như vậy, số lần chuyển n ñĩa từ A sang C là: Sn=Sn-1+1+Sn=2Sn-1+1=2(2Sn-2+1)+1=2 2Sn-2+2+1=.....=2 n-1S1+2 n-2+...+2+1=2n−1. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 9 Thuật toán về trò chơi “Tháp Hà Nội” ñòi hỏi 264−1 lần chuyển ñĩa (xấp xỉ 18,4 tỉ tỉ lần). Nếu mỗi lần chuyển ñĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm! Hai thí dụ trên cho thấy rằng: một thuật toán phải kết thúc sau một số hữu hạn bước, nhưng nếu số hữu hạn này quá lớn thì thuật toán không thể thực hiện ñược trong thực tế. Ta nói: thuật toán trong Thí dụ 3 có ñộ phức tạp là n-1 và là một thuật toán hữu hiệu (hay thuật toán nhanh); thuật toán trong Thí dụ 4 có ñộ phức tạp là 2n−1 và ñó là một thuật toán không hữu hiệu (hay thuật toán chậm). 1.3.2. So sánh ñộ phức tạp của các thuật toán: Một bài toán thường có nhiều cách giải, có nhiều thuật toán ñể giải, các thuật toán ñó có ñộ phức tạp khác nhau. Xét bài toán: Tính giá trị của ña thức P(x)=anx n+an-1x n-1+ ... +a1x+a0 tại x0. Thuật toán 1: Procedure tính giá trị của ña thức (a0, a1, ..., an, x0: các số thực) sum:=a0 for i:=1 to n sum:=sum+aix0 i {sum là giá trị của ña thức P(x) tại x0} Chú ý rằng ña thức P(x) có thể viết dưới dạng: P(x)=(...((anx+an-1)x+an-2)x...)x+a0. Ta có thể tính P(x) theo thuật toán sau: Thuật toán 2: Procedure tính giá trị của ña thức (a0, a1, ..., an, x0: các số thực) P:=an for i:=1 to n P:=P.x0+an-i {P là giá trị của ña thức P(x) tại x0} Ta hãy xét ñộ phức tạp của hai thuật toán trên. ðối với thuật toán 1: ở bước 2, phải thực hiện 1 phép nhân và 1 phép cộng với i=1; 2 phép nhân và 1 phép cộng với i=2, ..., n phép nhân và 1 phép cộng với i=n. Vậy số phép tính (nhân và cộng) mà thuật toán 1 ñòi hỏi là: (1+1)+(2+1)+ ... +(n+1)= 2 )1( +nn +n= 2 )3( +nn . ðối với thuật toán 2, bước 2 phải thực hiện n lần, mỗi lần ñòi hỏi 2 phép tính (nhân rồi cộng), do ñó số phép tính (nhân và cộng) mà thuật toán 2 ñòi hỏi là 2n. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 10 Nếu coi thời gian thực hiện mỗi phép tính nhân và cộng là như nhau và là một ñơn vị thời gian thì với mỗi n cho trước, thời gian thực hiện thuật toán 1 là n(n+3)/2, còn thời gian thực hiện thuật toán 2 là 2n. Rõ ràng là thời gian thực hiện thuật toán 2 ít hơn so với thời gian thực hiện thuật toán 1. Hàm f1(n)=2n là hàm bậc nhất, tăng chậm hơn nhiều so với hàm bậc hai f2(n)=n(n+3)/2. Ta nói rằng thuật toán 2 (có ñộ phức tạp là 2n) là thuật toán hữu hiệu hơn (hay nhanh hơn) so với thuật toán 1 (có ñộ phức tạp là n(n+3)/2). ðể so sánh ñộ phức tạp của các thuật toán, ñiều tiện lợi là coi ñộ phức tạp của mỗi thuật toán như là cấp của hàm biểu hiện thời gian thực hiện thuật toán ấy. Các hàm xét sau ñây ñều là hàm của biến số tự nhiên n>0. ðịnh nghĩa 1:Ta nói hàm f(n) có cấp thấp hơn hay bằng hàm g(n) nếu tồn tại hằng số C>0 và một số tự nhiên n0 sao cho |f(n)| ≤ C|g(n)| với mọi n≥n0. Ta viết f(n)=O(g(n)) và còn nói f(n) thoả mãn quan hệ big-O ñối với g(n). Theo ñịnh nghĩa này, hàm g(n) là một hàm ñơn giản nhất có thể ñược, ñại diện cho “sự biến thiên” của f(n). Khái niệm big-O ñã ñược dùng trong toán học ñã gần một thế kỷ nay. Trong tin học, nó ñược sử dụng rộng rãi ñể phân tích các thuật toán. Nhà toán học người ðức Paul Bachmann là người ñầu tiên ñưa ra khái niệm big-O vào năm 1892. Thí dụ 5: Hàm f(n)= 2 )3( +nn là hàm bậc hai và hàm bậc hai ñơn giản nhất là n2. Ta có: f(n)= 2 )3( +nn =O(n2) vì 2 )3( +nn ≤ n2 với mọi n≥3 (C=1, n0=3). Một cách tổng quát, nếu f(n)=akn k+ak-1n k-1+ ... +a1n+a0 thì f(n)=O(n k). Thật vậy, với n>1, |f(n)|| ≤ |ak|n k+|ak-1|n k-1+ ... +|a1|n+|a0| = n k(|ak|+|ak-1|/n+ ... +|a1|/n k-1+a0/n k) ≤ nk(|ak|+|ak-1|+ ... +|a1|+a0). ðiều này chứng tỏ |f(n)| ≤ Cnk với mọi n>1. Cho g(n)=3n+5nlog2n, ta có g(n)=O(nlog2n). Thật vậy, 3n+5nlog2n = n(3+5log2n) ≤ n(log2n+5log2n) = 6nlog2n với mọi n≥8 (C=6, n0=8). Mệnh ñề: Cho f1(n)=O(g1(n)) và f2(n) là O(g2(n)). Khi ñó (f1 + f2)(n) = O(max(|g1(n)|,|g2(n)|), (f1f2)(n) = O(g1(n)g2(n)). Chứng minh. Theo giả thiết, tồn tại C1, C2, n1, n2 sao cho |f1(n)| ≤ C1|g1(n)| và |f2(n)| ≤ C2|g2(n)| với mọi n > n1 và mọi n > n2. Do ñó |(f1 + f2)(n)| = |f1(n) + f2(n)| ≤ |f1(n)| + |f2(n)| ≤ C1|g1(n)| + C2|g2(n)| ≤ (C1+C2)g(n) với mọi n > n0=max(n1,n2), ở ñâyC=C1+C2 và g(n)=max(|g1(n)| , |g2(n)|). |(f1f2)(n)| = |f1(n)||f2(n)| ≤ C1|g1(n)|C2|g2(n)| ≤ C1C2|(g1g2)(n)| với mọi n > n0=max(n1,n2). http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 11 ðịnh nghĩa 2: Nếu một thuật toán có ñộ phức tạp là f(n) với f(n)=O(g(n)) thì ta cũng nói thuật toán có ñộ phức tạp O(g(n)). Nếu có hai thuật toán giải cùng một bài toán, thuật toán 1 có ñộ phức tạp O(g1(n)), thuật toán 2 có ñộ phức tạp O(g2(n)), mà g1(n) có cấp thấp hơn g2(n), thì ta nói rằng thuật toán 1 hữu hiệu hơn (hay nhanh hơn) thuật toán 2. 1.3.3. ðánh giá ñộ phức tạp của một thuật toán: 1) Thuật toán tìm kiếm tuyến tính: Số các phép so sánh ñược dùng trong thuật toán này cũng sẽ ñược xem như thước ño ñộ phức tạp thời gian của nó. Ở mỗi một bước của vòng lặp trong thuật toán, có hai phép so sánh ñược thực hiện: một ñể xem ñã tới cuối bảng chưa và một ñể so sánh phần tử x với một số hạng của bảng. Cuối cùng còn một phép so sánh nữa làm ở ngoài vòng lặp. Do ñó, nếu x=ai, thì ñã có 2i+1 phép so sánh ñược sử dụng. Số phép so sánh nhiều nhất, 2n+2, ñòi hỏi phải ñược sử dụng khi phần tử x không có mặt trong bảng. Từ ñó, thuật toán tìm kiếm tuyến tính có ñộ phức tạp là O(n). 2) Thuật toán tìm kiếm nhị phân: ðể ñơn giản, ta giả sử rằng có n=2k phần tử trong bảng liệt kê a1,a2,...,an, với k là số nguyên không âm (nếu n không phải là lũy thừa của 2, ta có thể xem bảng là một phần của bảng gồm 2k+1 phần tử, trong ñó k là số nguyên nhỏ nhất sao cho n < 2k+1). Ở mỗi giai ñoạn của thuật toán vị trí của số hạng ñầu tiên i và số hạng cuối cùng j của bảng con hạn chế tìm kiếm ở giai ñoạn ñó ñược so sánh ñể xem bảng con này còn nhiều hơn một phần tử hay không. Nếu i < j, một phép so sánh sẽ ñược làm ñể xác ñịnh x có lớn hơn số hạng ở giữa của bảng con hạn chế hay không. Như vậy ở mỗi giai ñoạn, có sử dụng hai phép so sánh. Khi trong bảng chỉ còn một phần tử, một phép so sánh sẽ cho chúng ta biết rằng không còn một phần tử nào thêm nữa và một phép so sánh nữa cho biết số hạng ñó có phải là x hay không. Tóm lại cần phải có nhiều nhất 2k+2=2log2n+2 phép so sánh ñể thực hiện phép tìm kiếm nhị phân (nếu n không phải là lũy thừa của 2, bảng gốc sẽ ñược mở rộng tới bảng có 2k+1 phần tử, với k=[log2n] và sự tìm kiếm ñòi hỏi phải thực hiện nhiều nhất 2[log2n]+2 phép so sánh). Do ñó thuật toán tìm kiếm nhị phân có ñộ phức tạp là O(log2n). Từ sự phân tích ở trên suy ra rằng thuật toán tìm kiếm nhị phân, ngay cả trong trường hợp xấu nhất, cũng hiệu quả hơn thuật toán tìm kiếm tuyến tính. 3) Chú ý: Một ñiều quan trọng cần phải biết là máy tính phải cần bao lâu ñể giải xong một bài toán. Thí dụ, nếu một thuật toán ñòi hỏi 10 giờ, thì có thể còn ñáng chi phí thời gian máy tính ñòi hỏi ñể giải bài toán ñó. Nhưng nếu một thuật toán ñòi hỏi 10 tỉ năm ñể giải một bài toán, thì thực hiện thuật toán ñó sẽ là một ñiều phi lý. Một trong những hiện tượng lý thú nhất của công nghệ hiện ñại là sự tăng ghê gớm của tốc ñộ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết ñể giải một http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 12 bài toán là sự xử lý song song - ñây là kỹ thuật thực hiện ñồng thời các dãy phép tính. Do sự tăng tốc ñộ tính toán và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật toán lợi dụng ñược ưu thế của kỹ thuật xử lý song song, các bài toán vài năm trước ñây ñược xem là không thể giải ñược, thì bây giờ có thể giải bình thường. 1. Các thuật ngữ thường dùng cho ñộ phức tạp của một thuật toán: ðộ phức tạp Thuật ngữ O(1) ðộ phức tạp hằng số O(logn) ðộ phức tạp lôgarit O(n) ðộ phức tạp tuyến tính O(nlogn) ðộ phức tạp nlogn O(nb) ðộ phức tạp ña thức O(bn) (b>1) ðộ phức tạp hàm mũ O(n!) ðộ phức tạp giai thừa 2222. . . . Thời gian máy tính ñược dùng bởi một thuật toán: Kích thước Các phép tính bit ñược sử dụng của bài toán n logn N nlogn n2 2n n! 10 3.10-9 s 10-8 s 3.10-8 s 10-7 s 10-6 s 3.10-3 s 102 7.10-9 s 10-7 s 7.10-7 s 10-5 s 4.1013năm * 103 1,0.10-8 s 10-6 s 1.10-5 s 10-3 s * * 104 1,3.10-8 s 10-5 s 1.10-4 s 10-1 s * * 105 1,7.10-8 s 10-4 s 2.10-3 s 10 s * * 106 2.10-8 s 10-3 s 2.10-2 s 17 phút * * 1.4. SỐ NGUYÊN VÀ THUẬT TOÁN. 1.4.1. Thuật toán Euclide: Phương pháp tính ước chung lớn nhất của hai số bằng cách dùng phân tích các số nguyên ñó ra thừa số nguyên tố là không hiệu quả. Lý do là ở chỗ thời gian phải tiêu tốn cho sự phân tích ñó. Dưới ñây là phương pháp hiệu quả hơn ñể tìm ước số chung lớn nhất, gọi là thuật toán Euclide. Thuật toán này ñã biết từ thời cổ ñại. Nó mang tên nhà toán học cổ Hy lạp Euclide, người ñã mô tả thuật toán này trong cuốn sách “Những yếu tố” nổi tiếng của ông. Thuật toán Euclide dựa vào 2 mệnh ñề sau ñây. Mệnh ñề 1 (Thuật toán chia): Cho a và b là hai số nguyên và b≠0. Khi ñó tồn tại duy nhất hai số nguyên q và r sao cho a = bq+r, 0 ≤ r < |b|. Trong ñẳng thức trên, b ñược gọi là số chia, a ñược gọi là số bị chia, q ñược gọi là thương số và r ñược gọi là số dư. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 13 Khi b là nguyên dương, ta ký hiệu số dư r trong phép chia a cho b là a mod b. Mệnh ñề 2: Cho a = bq + r, trong ñó a, b, q, r là các số nguyên. Khi ñó UCLN(a,b) = UCLN(b,r). (Ở ñây UCLN(a,b) ñể chỉ ước chung lớn nhất của a và b.) Giả sử a và b là hai số nguyên dương với a ≥ b. ðặt r0 = a và r1 = b. Bằng cách áp dụng liên tiếp thuật toán chia, ta tìm ñược: r0 = r1q1 + r2 0 ≤ r2 < r1 r1 = r2q2 + r3 0 ≤ r3 < r2 .................. rn-2 = rn-1qn-1 + rn 0 ≤ rn < rn-1 rn-1 = rnqn . Cuối cùng, số dư 0 sẽ xuất hiện trong dãy các phép chia liên tiếp, vì dãy các số dư a = r0 > r1 > r2 >... ≥ 0 không thể chứa quá a số hạng ñược. Hơn nữa, từ Mệnh ñề 2 ở trên ta suy ra: UCLN(a,b) = UCLN(r0,r1) = UCLN(r1,r2) = ... = UCLN(rn-2, rn-1) = UCLN(rn-1,rn) = rn. Do ñó, ước chung lớn nhất là số dư khác không cuối cùng trong dãy các phép chia. Thí dụ 6: Dùng thuật toán Euclide tìm UCLN(414, 662). 662 = 441.1 + 248 414 = 248.1 + 166 248 = 166.1+ 82 166 = 82.2 + 2 82 = 2.41. Do ñó, UCLN(414, 662) = 2. Thuật toán Euclide ñược viết dưới dạng giả mã như sau: procedure ƯCLN (a,b: positive integers) x := a y := b while y ≠ 0 begin r := x mod y x := y y := r end {UCLN (a,b) là x} Trong thuật toán trên, các giá trị ban ñầu của x và y tương ứng là a và b. Ở mỗi giai ñoạn của thủ tục, x ñược thay bằng y và y ñược thay bằng x mod y. Quá trình này ñược lặp lại chừng nào y ≠ 0. Thuật toán sẽ ngừng khi y = 0 và giá trị của x ở ñiểm này, ñó là số dư khác không cuối cùng trong thủ tục, cũng chính là ước chung lớn nhất của a và b. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 14 1.4.2. Biểu diễn các số nguyên: Mệnh ñề 3: Cho b là một số nguyên dương lớn hơn 1. Khi ñó nếu n là một số nguyên dương, nó có thể ñược biểu diễn một cách duy nhất dưới dạng: n = akb k + ak-1b k-1 + ... + a1b + a0. Ở ñây k là một số tự nhiên, a0, a1,..., ak là các số tự nhiên nhỏ hơn b và ak ≠ 0. Biểu diễn của n ñược cho trong Mệnh ñề 3 ñược gọi là khai triển của n theo cơ số b, ký hiệu là (akak-1... a1a0)b. Bây giờ ta sẽ mô tả thuật toán xây dựng khai triển cơ số b của số nguyên n bất kỳ. Trước hết ta chia n cho b ñể ñược thương và số dư, tức là n = bq0 + a0, 0 ≤ a0 < b. Số dư a0 chính là chữ số ñứng bên phải cùng trong khai triển cơ số b của n. Tiếp theo chia q0 cho b, ta ñược: q0 = bq1 + a1, 0 ≤ a1 < b. Số dư a1 chính là chữ số thứ hai tính từ bên phải trong khai triển cơ số b của n. Tiếp tục quá trình này, bằng cách liên tiếp chia các thương cho b ta sẽ ñược các chữ số tiếp theo trong khai triển cơ số b của n là các số dư tương ứng. Quá trình này sẽ kết thúc khi ta nhận ñược một thương bằng 0. Thí dụ 7: Tìm khai triển cơ số 8 của (12345)10. 12345 = 8.1543 + 1 1543 = 8.192 + 7 192 = 8.24 + 0 24 = 8.3 + 0 3 = 8.0 + 3. Do ñó, (12345)10 = (30071)8. ðoạn giả mã sau biểu diễn thuật toán tìm khai triển cơ số b của số nguyên n. procedure khai triển theo cơ số b (n: positive integer) q := n k := 0 while q ≠ 0 begin ak := q mod b q := [ q b ] k := k + 1 end 1.4.3. Thuật toán cho các phép tính số nguyên: Các thuật toán thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong số học của máy tính. Ta sẽ mô tả ở http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 15 ñây các thuật toán cộng và nhân hai số nguyên trong biểu diễn nhị phân. Ta cũng sẽ phân tích ñộ phức tạp tính toán của các thuật toán này thông qua số các phép toán bit thực sự ñược dùng. Giả sử khai triển nhị phân của hai số nguyên dương a và b là: a = (an-1an-2 ... a1 a0)2 và b = (bn-1 bn-2 ... b1 b0)2 sao cho a và b ñều có n bit (ñặt các bit 0 ở ñầu mỗi khai triển ñó, nếu cần). 1) Phép cộng: Xét bài toán cộng hai số nguyên viết ở dạng nhị phân. Thủ tục thực hiện phép cộng có thể dựa trên phương pháp thông thường là cộng cặp chữ số nhị phân với nhau (có nhớ) ñể tính tổng của hai số nguyên. ðể cộng a và b, trước hết cộng hai bit ở phải cùng của chúng, tức là: a0 + b0 = c0.2 + s0. Ở ñây s0 là bit phải cùng trong khai triển nhị phân của a+b, c0 là số nhớ, nó có thể bằng 0 hoặc 1. Sau ñó ta cộng hai bit tiếp theo và số nhớ a1 + b1 + c0 = c1.2 + s1. Ở ñây s1 là bit tiếp theo (tính từ bên phải) trong khai triển nhị phân của a+b và c1 là số nhớ. Tiếp tục quá trình này bằng cách cộng các bit tương ứng trong hai khai triển nhị phân và số nhớ ñể xác ñịnh bit tiếp sau tính từ bên phải trong khai triển nhị phân của tổng a+b. Ở giai ñoạn cuối cùng, cộng an-1, bn-1 và cn-2 ñể nhận ñược cn-1.2+sn-1. Bit ñứng ñầu của tổng là sn=cn-1. Kết quả, thủ tục này tạo ra ñược khai triển nhị phân của tổng, cụ thể là a+b = (sn sn-1 sn-2 ... s1 s0)2. Thí dụ 8: Tìm tổng của a = (11011)2 và b = (10110)2. a0 + b0 = 1 + 0 = 0.2 + 1 (c0 = 0, s0 = 1), a1 + b1 + c0 = 1 + 1 + 0 = 1.2 + 0 (c1 = 1, s1 = 0), a2 + b2 +c1 = 0 + 1 + 1 = 1.2 + 0 (c2 = 1, s2 = 0), a3 + b3 + c2 = 1 + 0 + 1 = 1.2 + 0 (c3 = 1, s3 = 0), a4 + b4 +c3 = 1 + 1 + 1 = 1.2 + 1 (s5 = c4 =1, s4 = 1). Do ñó, a + b = (110001)2. Thuật toán cộng có thể ñược mô tả bằng cách dùng ñoạn giả mã như sau. procedure cộng (a,b: positive integers) c := 0 for j := 0 to n-1 begin d :=       ++ 2 cba jj sj := aj + bj + c − 2d c := d end sn := c {khai triển nhị phân của tổng là (sn sn-1 ...s1 s0) 2} http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 16 Tổng hai số nguyên ñược tính bằng cách cộng liên tiếp các cặp bit và khi cần phải cộng cả số nhớ nữa. Cộng một cặp bit và số nhớ ñòi ba hoặc ít hơn phép cộng các bit. Như vậy, tổng số các phép cộng bit ñược sử dụng nhỏ hơn ba lần số bit trong khai triển nhị phân. Do ñó, ñộ phức tạp của thuật toán này là O(n). 2) Phép nhân: Xét bài toán nhân hai số nguyên viết ở dạng nhị phân. Thuật toán thông thường tiến hành như sau. Dùng luật phân phối, ta có: ab = a∑ − = 1 0 2 n j j jb = ∑ − = 1 0 )2( n j j jba . Ta có thể tính ab bằng cách dùng phương trình trên. Trước hết, ta thấy rằng abj=a nếu bj=1 và abj=0 nếu bj=0. Mỗi lần ta nhân một số hạng với 2 là ta dịch khai triển nhị phân của nó một chỗ về phía trái bằng cách thêm một số không vào cuối khai triển nhị phân của nó. Do ñó, ta có thể nhận ñược (abj)2 j bằng cách dịch khai triển nhị phân của abj ñi j chỗ về phía trái, tức là thêm j số không vào cuối khai triển nhị phân của nó. Cuối cùng, ta sẽ nhận ñược tích ab bằng cách cộng n số nguyên abj.2 j với j=0, 1, ..., n-1. Thí dụ 9: Tìm tích của a = (110)2 và b = (101)2. Ta có ab0.2 0 = (110)2.1.2 0 = (110)2, ab1.2 1 = (110)2.0.2 1 = (0000)2, ab2.2 2 = (110)2.1.2 2 = (11000)2. ðể tìm tích, hãy cộng (110)2, (0000)2 và (11000)2. Từ ñó ta có ab= (11110)2. Thủ tục trên ñược mô tả bằng ñoạn giả mã sau: procedure nhân (a,b: positive integers) for j := 0 to n-1 begin if bj = 1 then cj := a ñược dịch ñi j chỗ else cj := 0 end {c0, c1,..., cn-1 là các tích riêng phần} p := 0 for j := 0 to n-1 p := p + cj {p là giá trị của tích ab} Thuật toán trên tính tích của hai số nguyên a và b bằng cách cộng các tích riêng phần c0, c1, c2, ..., cn-1. Khi bj=1, ta tính tích riêng phần cj bằng cách dịch khai triển nhị phân của a ñi j bit. Khi bj=0 thì không cần có dịch chuyển nào vì cj=0. Do ñó, ñể tìm tất cả n số nguyên abj.2 j với j=0, 1, ..., n-1, ñòi hỏi tối ña là 0 + 1 + 2 + ... + n−1 = 2 )1( −nn phép dịch chỗ. Vì vậy, số các dịch chuyển chỗ ñòi hỏi là O(n2). http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 17 ðể cộng các số nguyên abj từ j=0 ñến n−1, ñòi hỏi phải cộng một số nguyên n bit, một số nguyên n+1 bit, ... và một số nguyên 2n bit. Ta ñã biết rằng mỗi phép cộng ñó ñòi hỏi O(n) phép cộng bit. Do ñó, ñộ phức tạp của thuật toán này là O(n2). 1.5. THUẬT TOÁN ðỆ QUY. 1.5.1. Khái niệm ñệ quy: ðôi khi chúng ta có thể quy việc giải bài toán với tập các dữ liệu ñầu vào xác ñịnh về việc giải cùng bài toán ñó nhưng với các giá trị ñầu vào nhỏ hơn. Chẳng hạn, bài toán tìm UCLN của hai số a, b với a > b có thể rút gọn về bài toán tìm ƯCLN của hai số nhỏ hơn, a mod b và b. Khi việc rút gọn như vậy thực hiện ñược thì lời giải bài toán ban ñầu có thể tìm ñược bằng một dãy các phép rút gọn cho tới những trường hợp mà ta có thể dễ dàng nhận ñược lời giải của bài toán. Ta sẽ thấy rằng các thuật toán rút gọn liên tiếp bài toán ban ñầu tới bài toán có dữ liệu ñầu vào nhỏ hơn, ñược áp dụng trong một lớp rất rộng các bài toán. ðịnh nghĩa: Một thuật toán ñược gọi là ñệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban ñầu tới bài toán cũng như vậy nhưng có dữ liệu ñầu vào nhỏ hơn. Thí dụ 10: Tìm thuật toán ñệ quy tính giá trị an với a là số thực khác không và n là số nguyên không âm. Ta xây dựng thuật toán ñệ quy nhờ ñịnh nghĩa ñệ quy của an, ñó là an+1=a.an với n>0 và khi n=0 thì a0=1. Vậy ñể tính an ta quy về các trường hợp có số mũ n nhỏ hơn, cho tới khi n=0. procedure power (a: số thực khác không; n: số nguyên không âm) if n = 0 then power(a,n) := 1 else power(a,n) := a * power(a,n-1) Thí dụ 11: Tìm thuật toán ñệ quy tính UCLN của hai số nguyên a,b không âm và a > b. procedure UCLN (a,b: các số nguyên không âm, a > b) if b = 0 then UCLN (a,b) := a else UCLN (a,b) := UCLN (a mod b, b) Thí dụ 12: Hãy biểu diễn thuật toán tìm kiếm tuyến tính như một thủ tục ñệ quy. ðể tìm x trong dãy tìm kiếm a1,a2,...,an trong bước thứ i của thuật toán ta so sánh x với ai. Nếu x bằng ai thì i là vị trí cần tìm, ngược lại thì việc tìm kiếm ñược quy về dãy có số phần tử ít hơn, cụ thể là dãy ai+1,...,an. Thuật toán tìm kiếm có dạng thủ tục ñệ quy như sau. Cho search (i,j,x) là thủ tục tìm số x trong dãy ai, ai+1,..., aj. Dữ liệu ñầu vào là bộ ba (1,n,x). Thủ tục sẽ dừng khi số hạng ñầu tiên của dãy còn lại là x hoặc là khi dãy còn lại chỉ có một phần tử khác x. Nếu x không là số hạng ñầu tiên và còn có các số hạng khác thì lại áp dụng thủ tục này, nhưng dãy tìm kiếm ít hơn một phần tử nhận ñược bằng cách xóa ñi phần tử ñầu tiên của dãy tìm kiếm ở bước vừa qua. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 18 procedure search (i,j,x) if ai = x then loacation := i else if i = j then loacation := 0 else search (i+1,j,x) Thí dụ 13: Hãy xây dựng phiên bản ñệ quy của thuật toán tìm kiếm nhị phân. Giả sử ta muốn ñịnh vị x trong dãy a1, a2, ..., an bằng tìm kiếm nhị phân. Trước tiên ta so sánh x với số hạng giữa a[(n+1)/2]. Nếu chúng bằng nhau thì thuật toán kết thúc, nếu không ta chuyển sang tìm kiếm trong dãy ngắn hơn, nửa ñầu của dãy nếu x nhỏ hơn giá trị giữa của của dãy xuất phát, nửa sau nếu ngược lại. Như vậy ta rút gọn việc giải bài toán tìm kiếm về việc giải cũng bài toán ñó nhưng trong dãy tìm kiếm có ñộ dài lần lượt giảm ñi một nửa. procedure binary search (x,i,j) m := [(i+j)/2] if x = am then loacation := m else if (x < am and i < m) then binary search (x,i,m-1) else if (x > am and j > m) then binary search (x,m+1,j) else loacation := 0 1.5.2. ðệ quy và lặp: Thí dụ 14. Thủ tục ñệ quy sau ñây cho ta giá trị của n! với n là số nguyên dương. procedure factorial (n: positive integer) if n = 1 then factorial(n) := 1 else factorial(n) := n * factorial(n-1) Có cách khác tính hàm giai thừa của một số nguyên từ ñịnh nghĩa ñệ quy của nó. Thay cho việc lần lượt rút gọn việc tính toán cho các giá trị nhỏ hơn, ta có thể xuất phát từ giá trị của hàm tại 1và lần lượt áp dụng ñịnh nghĩa ñệ quy ñể tìm giá trị của hàm tại các số nguyên lớn dần. ðó là thủ tục lặp. procedure iterative factorial (n: positive integer) x := 1 for i := 1 to n x := i * x {x là n!} Thông thường ñể tính một dãy các giá trị ñược ñịnh nghĩa bằng ñệ quy, nếu dùng phương pháp lặp thì số các phép tính sẽ ít hơn là dùng thuật toán ñệ quy (trừ khi dùng các máy ñệ quy chuyên dụng). Ta sẽ xem xét bài toán tính số hạng thứ n của dãy Fibonacci. procedure fibonacci (n: nguyên không âm) http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 19 if n = 0 the fibonacci(n) := 0 else if n = 1 then fibonacci(n) := 1 else fibonacci(n) := fibonacci(n - 1) + fibonacci(n - 2) Theo thuật toán này, ñể tìm fn ta biểu diễn fn = fn-1 + fn-2. Sau ñó thay thế cả hai số này bằng tổng của hai số Fibonacci bậc thấp hơn, cứ tiếp tục như vậy cho tới khi f0 và f1 xuất hiện thì ñược thay bằng các giá trị của chúng theo ñịnh nghĩa. Do ñó ñể tính fn cần fn+1-1 phép cộng. Bây giờ ta sẽ tính các phép toán cần dùng ñể tính fn khi sử dụng phương pháp lặp. Thủ tục này khởi tạo x là f0 = 0 và y là f1 = 1. Khi vòng lặp ñược duyệt qua tổng của x và y ñược gán cho biến phụ z. Sau ñó x ñược gán giá trị của y và y ñược gán giá trị của z. Vậy sau khi ñi qua vòng lặp lần 1, ta có x = f1 và y = f0 + f1 = f2. Khi qua vòng lặp lần n-1 thì x = fn-1. Như vậy chỉ có n – 1 phép cộng ñược dùng ñể tìm fn khi n > 1. procedure Iterative fibonacci (n: nguyên không âm) if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y là số Fibonacci thứ n} Ta ñã chỉ ra rằng số các phép toán dùng trong thuật toán ñệ quy nhiều hơn khi dùng phương pháp lặp. Tuy nhiên ñôi khi người ta vẫn thích dùng thủ tục ñệ quy hơn ngay cả khi nó tỏ ra kém hiệu quả so với thủ tục lặp. ðặc biệt, có những bài toán chỉ có thể giải bằng thủ tục ñệ quy mà không thể giải bằng thủ tục lặp. BÀI TẬP CHƯƠNG I: 1. Tìm một số nguyên n nhỏ nhất sao cho f(x) là O(xn) ñối với các hàm f(x) sau: a) f(x) = 2x3 + x2log x. b) f(x) = 2x3 + (log x)4. c) f(x) = 1 1 3 24 + ++ x xx http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 20 d) f(x) = 1 log5 4 5 + + x xx . 2. Chứng minh rằng a) x2 + 4x + 7 là O(x3), nhưng x3 không là O(x2 +4x + 17). b) xlog x là O(x2), nhưng x2 không là O(xlog x). 3. Cho một ñánh giá big-O ñối với các hàm cho dưới ñây. ðối với hàm g(x) trong ñánh giá f(x) là O(g(x)), hãy chọn hàm ñơn giản có bậc thấp nhất. a) nlog(n2 + 1) + n2logn. b) (nlogn + 1)2 + (logn + 1)(n2 + 1). c) 22 nnn n + . 4. Cho Hn là số ñiều hoà thứ n: Hn = 1 + 2 1 + 3 1 + ... + n 1 Chứng minh rằng Hn là O(logn). 5. Lập một thuật toán tính tổng tất cả các số nguyên trong một bảng. 6. Lập thuật toán tính xn với x là một số thực và n là một số nguyên. 7. Mô tả thuật toán chèn một số nguyên x vào vị trí thích hợp trong dãy các số nguyên a1, a2, ..., an xếp theo thứ tự tăng dần. 8. Tìm thuật toán xác ñịnh vị trí gặp ñầu tiên của phần tử lớn nhất trong bảng liệt kê các số nguyên, trong ñó các số này không nhất thiết phải khác nhau. 9. Tìm thuật toán xác ñịnh vị trí gặp cuối cùng của phần tử nhỏ nhất trong bảng liệt kê các số nguyên, trong ñó các số này không nhất thiết phải khác nhau. 10. Mô tả thuật toán ñếm số các số 1 trong một xâu bit bằng cách kiểm tra mỗi bit của xâu ñể xác ñịnh nó có là bit 1 hay không. 11. Thuật toán tìm kiếm tam phân. Xác ñịnh vị trí của một phần tử trong một bảng liệt kê các số nguyên theo thứ tự tăng dần bằng cách tách liên tiếp bảng liệt kê ñó thành ba bảng liệt kê con có kích thước bằng nhau (hoặc gần bằng nhau nhất có thể ñược) và giới hạn việc tìm kiếm trong một bảng liệt kê con thích hợp. Hãy chỉ rõ các bước của thuật toán ñó. 12. Lập thuật toán tìm trong một dãy các số nguyên số hạng ñầu tiên bằng một số hạng nào ñó ñứng trước nó trong dãy. http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 21 13. Lập thuật toán tìm trong một dãy các số nguyên tất cả các số hạng lớn hơn tổng tất cả các số hạng ñứng trước nó trong dãy. 14. Cho ñánh giá big-O ñối với số các phép so sánh ñược dùng bởi thuật toán trong Bài tập 10. 15. ðánh giá ñộ phức tạp của thuật toán tìm kiếm tam phân ñược cho trong Bài tập 11. 16. ðánh giá ñộ phức tạp của thuật toán trong Bài tập 12. 17. Mô tả thuật toán tính hiệu của hai khai triển nhị phân. 18. Lập một thuật toán ñể xác ñịnh a > b, a = b hay a < b ñối với hai số nguyên a và b ở dạng khai triển nhị phân. 19. ðánh giá ñộ phức tạp của thuật toán tìm khai triển theo cơ số b của số nguyên n qua số các phép chia ñược dùng. 20. Hãy cho thuật toán ñệ quy tìm tổng n số nguyên dương lẻ ñầu tiên. 21. Hãy cho thuật toán ñệ quy tìm số cực ñại của tập hữu hạn các số nguyên. 22. Mô tả thuật toán ñệ quy tìm xn mod m với n, x, m là các số nguyên dương. 23. Hãy nghĩ ra thuật toán ñệ quy tính n a2 trong ñó a là một số thực và n là một số nguyên dương. 24. Hãy nghĩ ra thuật toán ñệ quy tìm số hạng thứ n của dãy ñược xác ñịnh như sau: a0=1, a1 = 2 và an = an-1 an-2 với n = 2, 3, 4, ... 25. Thuật toán ñệ quy hay thuật toán lặp tìm số hạng thứ n của dãy trong Bài tập 24 là có hiệu quả hơn?