Cấu trúc dữ liệu và giải thuật - Chương 1

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

137
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

GIẢI THUẬT I. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giải thuật là một khái niệm cơ sở của tin học. Thuật ngữ “algorithm”, nghĩa là “giải thuật” (hay thuật toán) xuất phát từ tên một nhà toán học Ả Rập : Abu Já far Mohammed ibn Musa al Khowaizmi (năm 825 sau công nguyên) người đã viết một cuốn sách trong đó có mô tả về cách tính toán. Giải thuật thể hiện một giải pháp cụ thể, thực hiện từng bước một, để đưa tới lời giải cho một bài toán nào đó. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật - Chương 1

Chương I. GIẢI THUẬT I. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giải thuật là một khái niệm cơ sở củ a tin học. Thu ật ngữ “algorithm”, ngh ĩa là “giải thuật” (hay thu ật toán) xu ất phát từ tên một nhà toán học Ả Rập : Abu Já far Mohammed ibn Musa al Khowaizmi (n ăm 825 sau công nguyên) người đã viết một cuốn sách trong đó có mô tả về cách tính toán. Giải thuật th ể h iện mộ t giải pháp cụ th ể, thực hiện từng bước một, để đưa tới lời giải cho một bài toán nào đó. Có th ể nói : giải thuật là mộ t tập hữu hạn các phép toán cơ sở, được sắp đặt theo ngững qui tắc chính xác, nh ằm giải một bài toán nào đó. Các phép toán cơ sở là ngững phép toán đ ơn giản mà thời gian thực hiện nó luôn là một hằng số , ngh ĩa là nó không phụ thuộc gì vào kích thước của toán hạng. Các phép toán trong giải thuật luôn được xác định rõ ràng, không mập mờ ai cũng có th ể h iểu được cách thực hiện nó và ch ỉ một cách duy nh ất. Với b ộ dữ liệu củ a bài toán, giải thuật sẽ kết thúc sau mộ t số hữu hạn bước và cho mộ t lời giải. Khi giải một bài toán trên máy tính đ iện tử (MTĐT) ta quan tâm ngay đ ến việc thiết kế giải thuật. Như ng cần nhớ rằng :giải thuật là đặt trưng cho cách xử lí, mà cách xử lí thì thường liên quan tới đối tượng xử lí, tức là “dữ liệu”.Cung cách th ể h iện dữ liệu mà theo nó chúng được lưu trữ và xử lí trong MTĐT , đ ược gọ i là cấu trúc dữ liệu. Hình dung và tổ chức các dữ liệu theo cấu trúc nào đ iều đó có ảnh hưởng tới cách xử lí. Như vậy giữa cấu trúc dữ liệu và giải thu ật luôn có quan h ệ ; thay đổ i cấu trúc dữ liệu sẽ dẫn đến thay đ ổi giải thuật. Chẳng hạn : Xét mộ t danh mụ c đ iện tho ại có dạng mà 1≤ i ≤ n , với ai là kí h iệu ch ỉ họ tên người “thuê bao” bi chỉ “số đ iện tho ại”. Chúng ta muốn tìm số diện tho ại của một người có họ tên X nào đó. Nếu danh mục điện thoại được ghi chép tự nhiên trong sổ tay của ta thì việc đi tìm người thuê bao có họ tên X để truy ra số điện thoại củ a họ, chỉ có th ể thực hiện bằng cách so sánh X với ai với i = 1, 2, 3…v.v.cho tới khi hoặc gặp một ak = X thì truy đ ược số điện thoại bk tương ứng hoặc không tìm ra được, sau khiđã duyệt hết cả danh sách . Như vậy là ta đ ã th ực hiện một giải thuật tìm kiếm được gọi là “tìm kiếm tuần tự” (sequential search).
Nhưng n ếu danh mục điện thoại lại được tổ chức sắp xếp theo thứ tự từ đ iển (giống như sắp xếp các từ trong từ điển) thì việc đ i tìm số điện thoại củ a X giống như việc đi tìm ngh ĩa của một từ mà ta cần tra cứu. Trong trường h ợp này không bao giờ ta áp dụng giải thuật “tìm kiếm tu ần tự” như đ ã nêu ở trên cả ! Rõ ràng “giải thu ật” đã thay đổi, khi “cấu trúc dữ liệu” thay đổi. Mỗ i ngôn ngữ lập trình đều ấn định sẵn những cấu trúc dữ liệu riêng cho mình : đó là các cấu trúc dữ liệu tiền định , chúng được th ể h iện qua các kiểu dữ liệu của ngôn ngữ đó. Th ường đa số các cấu trúc tiền định này là các cấu trúc dữ liệu thông dụng. Ngoài ra có thể có những cấu trúc dữ liệu đặc biệt có ở ngôn ngữ này mà không có ở n gôn ngữ khác. “Người dùng” (user), khi sử dụng một ngôn ngữ nào đ ể thể hiện một giải thuật giải bải toán củ a mình, phải biết linh ho ạt tổ chức dữ liệu củ a bài toán theo các cấu trúc tiền dịnh của ngôn ngữ đó. Rất có thể ngôn ngữ đang sử dụng không có sẵn các cấu trúc thật khớp với dữ liệu bài toán , việc vận dụng khéo léo các cấu trúc hiện có của ngôn ngữ để biểu diễn cấu trúc riêng cho dữ liệu thuộc bài toán củ a mình hoàn toàn phụ thuộ c vào kh ả n ăng và kĩ xảo củ a “người dùng” ! II. NGÔN NGỮ DIỄN ĐẠT GIẢI THUẬT Mặt d ầu vấn đ ề ngôn ngữ lập trình không được đặt ra ở giáo trình này, nhưng để diễn đạt giải thuật mà ta sẽ trình bày dưới đ ây, ta cũng ph ải lựa chọn một ngôn ngữ. Có th ể n gh ĩ ngay đến việc sử dụng một ngôn ngữ cấp cao hiện có, chẳng hạn như : PASCAL, C, v. v…, nhưng như vậy sẽ gặp một số hạn chế : − Phải luôn luôn tuân thủ các qui tắc chặt chẽ về cú pháp của ngôn ngữ đó, khiến cho việc trình bày về giải thuật và cấu trúc dữ liệu có thiên hướng nặng nề, gò bó. − Phải phụ thuộc vào cấu trúc dữ liệu tiền định của ngôn ngữ , nên có lúc không thể hiện đầy đ ủ các ý về cấu trúc mà ta mong muốn giới thiệu. − Ngôn ngữ đã chọn không phải ai cũng ưa thích và sử dụng. Vì vậ y ở đây ta sẽ dùng một ngôn ngữ “thô hơn” có đủ khả năng diễn đạt được giải thuật trên các cấu trúc đ ề cập đến (mà ta giới thiệu b ằng Tiếng Việt), với mứ c độ linh hoạt nhất định, không quá gò bó, không câu nệ nhiều về cú pháp nhưng cũng không gần gũi với các ngôn ngữ chu ẩn đ ể việc truyền đổ i khi cần thiết được dễ dàng. Ta tạm gọi b ằng cái tên : “ngôn ngữ tựa C”. Sau đây là một số qui tắc bước đ ầu. Ở các phần sau sẽ có bổ sung thêm. 1. Quy cách về cấu trúc chương trình Cấu trúc chương trình C gồm các ph ần sau : − Ph ần 1 : Các định hướng #include thường ở trên 1 dòng
− Ph ần 2 : Khai báo các Macro (định hướng #define) − Ph ần 3 : Khai báo các nguyên m ẫu hàm và các biến toàn cụ c − Ph ần 4 : Định nghĩa hàm Main() − Ph ần 5 : Định nghĩa các hàm đã khai báo nguyên m ẫu ở trên Tất cả các phần khai báo là tùy chọn nhưng chương trình phải có hàm Main() để gọi các hàm khác và các hàm khác có thể gọi lẫn nhau. Tên (identifier) : Định danh cho 1 thành ph ần trong chương trình theo nguyên tắc : − Các chữ cái (A Z,a z), chữ số (0..9), dấu nối − Không bắt đầu b ằng chữ số − Không dùng từ khóa − Độ dài cực đ ại của tên mặc đ ịnh là 32. − C có phân biệt chữ hoa / thường − Từ khóa và hàm chu ẩn đều ghi chữ thường − Các Macro là chữ hoa. Sau tên có kèm theo lời thuyết minh (ở đây ta quy ước dùng Tiếng Việt) để giới thiệu tóm tắt nhiệm vụ của giải thuật hoặc mộ t số chi tiết cần thiết. Ph ần thuyết minh được đ ặt giữa hai d ấu /* và */ Chương trình bao gồm nhiều bước, mỗi bước được phân biệt bởi số thứ tự, có th ể kèm theo nhữ ng lời thuyết minh. Dấu “;”để ngăn cách các lệnh, cuối lệnh có dấu “;”. Nhiều lệnh có thể được xem là 1 lệnh nếu được đặt trong d ấu { và } Ví dụ : #include #define CHAO printf(“Chao ban!”); main() { CHAO } 2. Kí tự và biểu thức a) Kí tự dùng ở đây cũ ng giống như trong các ngôn ngữ chu ẩn, ngh ĩa là gồm: - 26 chữ cái Latinh in hoa hoặc in th ường - 10 chữ số 0 …9 - Các dấu phép toán số học +,-,*,/,=,() - Ký tự gạch nối : _ (chú ý khác với dấu “-”) - Giá trị logic : true, false
- Dấu phép toán logic: and, or, not - Các ký hiệu đ ặc biệt khác như : . , ; : {} [] ? ! \ & | % # $ . . . b) Còn biểu thức cũng như thứ tự ưu tiên của các phép toán trong biểu thức cũng theo quy tắc như trong C hay các ngôn ngữ chuẩn khác. 3. Các câu lệnh hay các chỉ thị a . Phép gán (=): Để gán cho 1 biến 1 giá trị thích hợp Cú pháp : Tên biến = biểu thức; : Tên biến Phép toán =biểu thức; Hay Ví d ụ : int a =1,b=2,c; c = (a+b)*5; c = c+2; c +=2 /* c=c+2 */ c /=2 /* c=c/3 */ c -=a+b /* c=c-(a+b)*/ b. Lệnh Printf() Cú pháp : Printf(“chuỗi ký tự”,danh sách khác); Để in giá trị các biểu thứ c ra màn hình với dạng thức xuất được ch ỉ đ ịnh trong chuỗi đ ịnh dạng Khai báo nó trong Ví d ụ : printf(“hello…”); c. Lệnh Scanf() Cú pháp : Scanf(“chuỗ i định dạng”,danh sách địa chỉ); Lệnh trên để nhập giá trị từ bàn phím và gán giá trị cho các biến tương ứng trong danh sách địa chỉ của chúng d. Toán tử tăng giảm ++ / -- để tăng hay giảm 1 biến 1 đơn vị ++ đặt trước 1 biến thì giá trị củ a biểu thức được tăng trước khi sử dụng, ngược lại đặt sau thì biến thì giá trị được tăng sau khi sử dụng Tương tự cho -- (giảm) Ví d ụ : Int a=5,b,c; a++; /*++a;a+=1;a=6*/ b=a++; /*b=6;a=7*/ c=++b; /*b=7;c=7*/ c=++a*b; /*a=8;c=56*/ c=a+(++b);/*b=8;c=16*/ e. Lệnh điều kiện
* Lệnh IF Cú pháp : If(điều kiện) lệnh 1; [else lệnh 2;] Nếu điều kiện đúng thì lệnh 1 được thực hiện Ngược lại lệnh 2 được thực hiện * Lệnh Switch Cú pháp : Switch (bt) { Case h1 : các lệnh 1; Case h2 : các lệnh 2; …………………. Case hn : các lệnh n; [default : các lệnh n+1;] } Chuyển qua các giá trị phù hợp của biểu th ức bt đ ể thực hiện các lệnh tương ứng. Nếu không có giá trị phù h ợp thì các lệnh n+1 được thực hiện Trình biên dịch quét từ trên xuống dưới cho đến khi gặp phải giá trị phù hợp thì thự c hiện tất cả các lệnh trong khối này. f. Lệnh vòng lặ p : * Lệnh While Cú pháp : While(biểu thức) lệnh; Trong khi biểu th ức còn đúng thì lệnh được thực hiện, đ ây là vòng lặp kiểm tra điều kiện trước khi th ực hiện lệnh. * Lệnh Do….While Cú pháp : Do lệnh While(biểu thức); Thự c hiện lệnh trong khi biểu thứ c đúng, đây là vòng lặp kiểm tra điều kiện sau khi th ực hiện lệnh nên lệnh được thực hiện ít nh ất 1 lần. * Vòng lặp For Cú pháp : For (danh sách bt đầu, bt kiểm tra;danh sách bt tă ng giảm) lệnh; Vào đầu vòng lặp thự c hiện danh sách biểu thức đ ầu rồ i trong khi biểu thức kiểm tra còn đúng thì thực hiện lệnh và danh sách biểu th ức tăng giảm. 4. Hàm Các hàm được định nghĩa ở cuối chương trình hay dưới hàm Main() với cú pháp như sau : Kiểu trả về Tên hàm(danh sách đối số ) { /*Các khai báo cục bộ*/
Các lệnh Return [biểu thức]; } Các hàm có th ể được gọ i bởi hàm Main() và chúng có th ể gọi lẫn nhau. III. THIẾT KẾ GIẢI THUẬT Tạo lập giải thuật để giải mộ t bài toán, là một nghệ thuật mà không bao giờ có th ể n êu đầy đủ n gay một lúc được. Có nhiều phương pháp thiết kế giải thuật khác nhau, thông dụng là cách thiết kế kiểu “top-down” :cách thiết kế “đi từ tổng thể đến chi tiết”.Chiến thuật được áp dụng đ ể th ể hiện cách thiết kế này là chiến thuật “chia để trị” nghĩa là tách bài toán ra thành các bài toán con (thành các mô-đun : mô-đun hoá).Với mỗi bài toán con này lại áp dụng mộ t chiến thuật tương tự, cho tới khi đ i tới những bài toán con đủ nhỏ đ ể có th ể giải trực tiếp được. Sau đó chỉ cần tổng hợp lại các phép xử lí để có được giải thuật củ a bài toán gốc. Để xác đ ịnh được đ iều đó, đứng trước môth bài toán, thông thường ta ph ải : -Xác định được rõ dữ liệu và yêu cầu : cho biết cái gì ? (d ữ liệu input) và đòi hỏi cái gì ? (dữ liệu output). -Để giải quyết đ ược yêu cầu thì “phả i làm gì?” : ở đ ây mới ch ỉ phân hoạch được công việc và xác đ ịnh mục tiêu của công việc đó. -Với công việc ấy thì “phải làm thế nào” ? Trên cơ sở đó mới cụ thể hóa dần dần các phép xử lí đ ể xây dựng giải thuật cần thiết. Tất nhiên, khi giải quyết câu hỏi “làm thế nào ?” thì dữ liệu input cũng được định hình về cấu trúc. Ví dụ ta xét bài toán : Sắp xếp mộ t dãy số (a1,a2, …., an ) thành mộ t dãy số tăng d ần. Nh ư vậy dãy số input, n ếu có dạng, ch ẳng h ạn : (33, 77, 11, 55, 99, 22, 44, 88, 66) thì dãy số output phải có d ạng: (11, 22, 33, 44, 55, 66, 77, 88, 99) Để có kết quả nh ư vậy thì phải làm gì? Có thể thấy rằng :sắp xếp theo thứ tự tăng dần nghĩa là : - Số bé nh ất trong n số ph ải được đặt vào vị trí đầu tiên. - Số bé nh ất trong(n-1) số còn lại phải được đ ặt vào vị trí thứ hai. v.v… Như vậy sẽ có hai công việc chính phải làm : Chọn số b é nhất trong dãy số chưa được sắp.
Đặt nó vào vị trí sau phần tử cuối của dãy số đã được sắp (nó lại trở thành phần tử cuố i của bước tiếp theo). Chú ý rằng :lúc đầu dãy số được sắp còn rỗng, sau đó được bổ sung dần d ần các ph ần tử vào. Các công việc trên sẽ đ ược lặp lại (n-1) lần : lần đầu với n số, lần cuối với hai số . Để thực hiện dược hai công việc trên thì phải “làm thế nào”? Trước hết phải nghĩ ngay tới : dãy số ở đây được đ ịnh hình theo cấu trúc nào? (cấu trúc dữ liệu) và được cài đặt trong máy theo cấu trúc nào ?(mà ta sẽ được gọi là : cấu trúc lưu trữ). Thông thường nó dược định hình và cài đ ặt theo cấu trúc vectơ (ở chương trình 2 sẽ nói rõ hơn). Ở đây có hai vectơ : vectơ input và vectơ output. Vậy thì trong máy ta sẽ dùng hai vectơ lưu trữ h ay chỉ d ùng mộ t ? Giả sử ta ch ỉ dùng 1, ngh ĩa là lúc đầu vectơ lưu trữ dãy số cho, nhưng sau khi thực hiện thì chính vectơ ấy cũ ng lưu trữ dãy số đ ã đ ược sắp xếp (để tiết kiêm bộ nhớ !) Nếu thế thì công việc “đổ i chỗ” sẽ được cụ thể thêm như sau : - Hoán vị vị trí củ a nó (số bé nhất vừa được chọn) với vị trí của số ở đầu dãy chưa được sắp, sau đó gạt nó ra ngoài dãy chưa được sắp (tất nhiên lúc đó nó đã trở thành phần tử cuối của dãy đã được sắp). Tới đây ta có th ể d iễn đạt sơ bộ giải thuật sắp xếp ở đây như sau : Bước 1: for (i=0;i
k = i ; {coi phần tử đầu là nhỏ nhất lúc đó, và giữ lại chỉ số của nó} for(int j = i +1; j < N; j++) if(a[j]
Không gian nhớ cần thiết cho những cấu trúc lưu trữ . - Thời gian cần thiết để thực hiện. - Việc đ ánh giá được th ời gian thực hiện và không gian nhớ cần thiết củ a 1 giải thuật sẽ cho ta cơ sở để xác định được giải thuật nào là tốt hơn. Tuy nhiên 2 yếu tố “không gian” và “thời gian” ứng với giải thuật hay mâu thu ẩn :”tốt” về thời gian nghĩa là thực hiện nhanh, thường lại kéo theo “không tốt” về không gian, nghĩa là tốn nhiều bộ nhớ và ngược lại. Vì vậy trong th ực tế, đối với từng loại bài toán, 1 trong 2 yếu tố đó sẽ được coi trọng hơn. Thông thường th ời gian thực hiện giải thu ật vẫn được chú ý hơn. Vì vậy, sau đây ta sẽ xét tới việc đ ánh giá thời gian th ực hiện giải thuật. Th ời gian thực hiện 1 giải thuật ch ịu ảnh hưởng củ a nhiều yếu tố. Nh ư ta đã biết : các kiểu lệnh và thời gian thực hiện các lệnh củ a các loại máy tính thường khác nhau. Hơn nữa ngôn ngữ lập trình và ch ất lượng của chương trình dịch cũng là các yếu tố liên quan tới thời gian thực hiện giải thuật . Vì vậy ta không thể tính thời gian này bằng phút, giây. . .như cách đo thời gian thông thường để rồi so sánh với nhau. Cùng 1 giải thuật, nhưng thự c hiện lên 2 loại máy khác nhau, với ngôn ngữ lập trình và chương trình dịch khác nhau sẽ đưa tới chi phí về thời gian tính theo phút, giây khác nhau. Vậy thì dựa vào đâu nói rằng giải thu ật này “nhanh hơn” giải thuật kia ? Trước h ết ta th ấy, thời gian thực hiện giải thuật thường phụ thuộc vào kích thước củ a bộ dữ liệu. Ví dụ : Sắp xếp 1 dãy n số, thì kích thước dữ liệu là n;n càng lớn thì thời gian sắp xếp càng lâu.Do đó người ta tìm cách biểu diễn thời gian th ực hiện giải thuật bằng 1 hàm số của kích thước n: T(n) (việc xác định kích thước của dữ liệu tu ỳ thuộc vào từng bài toán cụ thể). Rõ ràng là T(n) độc lập với các yếu tố khách quan đã nêu ở trên. Với cách tiếp cận này cùng 1 bài toán, nếu giải thuật A1 có thời gian thực hiện là T1(n) =8n, và 1 giải thuật A2, có thời gian thực hiện là T2(n) = 2n 2 thì khi n đủ lớn ta th ấy, T1(n) ≤ T2(n) (ở đây chỉ cần n ≥ 4 là 2n2 ≥ 8n ) và n cành lớn thì sự chênh lệch càng nhỏ. Nh ư vậy ta có thể nói : Khi n đ ủ lớn thì giải thuật A1 “nhanh h ơn” giải thuật A2 . Trong thực tế, với tố độ tính toán củ a MTĐT hiện nay thì việc so sánh thời gian thực hiện giải thuật ch ỉ đặt ra khi n khá lớn (lúc đó độ chênh lệch mới đáng kể). Vấn đề đặt ra bây giờ là : làm thế nào để xác đ ịnh được T(n)? - Trước h ết ta xét 1 ví dụ : giải thuật tính giá trị trung bình của n số :
{ Các số ở đ ây được coi như n giá trị khác nhau của X; M sẽ lư u trữ giá trị trung bình sau khi được tính } 1. scanf(“%d”,&n); 2. S=0; 3. i=1; 4. While i
T(n) = aknk + ak-1nk-1 + . . . + a1n + ao Thì cũng chứng minh được khi n đủ lớn, T(n) = O(n k) Ngh ĩa là khi n đủ lớn thì số h ạng với mũ lớn nh ất sẽ được coi trọng, khi đánh giá thời gian thự c hiện giải thuật. 3) Từ những nhận xét trên, khi xác định độ phức tạp của giải thu ật, theo ký pháp chữ O, ta ch ỉ cần chú ý tới phép toán nào đó mà số lần thực hiện phụ thuộc vào n và không thua kém các phép khác; người ta gọi là “phép toán tích cực” và thời gian thực hịên giải thu ật sẽ được đánh giá về bậc theo số lần thực hiện phép này. Nh ư trong giải thuật “tính giá trị trung bình”ở trên : có thể coi phép so sánh i ≤ n trong câu lệnh While làm phép toán tích cự c. Số lần th ực hiện nó là n+1 từ đó suy ra : T(n) = O(n) Ta sẽ xét thêm đ iều này qua giải thuật SELECTION-SORT ở mục 1.3 Đối với giải thu ật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-1) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có th ể kết luận: Số lần so sánh : n(n-1)/2 Số lần hoán vị lại phụ thuộc vào tình trạng ban đ ầu của dãy số , ta ch ỉ có thể ước lược trong từng trường hợp sau: Trường Hợp Số lần so sánh Số lần hoán vị Tốt nhất N(n-1)/2 O Xấu N(n-1)/2 N(n-1)/2 nh ất Trung bình N(n-1)/2 N(n-1)/4 2. Thời gian trung bình Có nhiều trường h ợp thời gian thực hiện giải thuật T(n) không những phụ thuộc vào kích thước của dữ liệu mà còn phụ thuộc vào tình trạng củ a dữ liệu nữa. Trở lại bài toán tìm kiếm 1 số X trong dãy n số a1;a2;. . .;an . Theo phương pháp tìm kiếm tuần tự ta thấy ngay : với phép tính tích cự c là phép so sánh thì : n ếu X=a ta chỉ cần 1 phép so sánh. Nếu X=an hoặc không có a[i] nào (1≤i≤n) có giá trị bằng X thì cần tới n phép so sánh. Nh ư vậy là tốt nhất thì T(n)=O(1) (Ta ký hiệu là Tt(n)=O(1) Còn xấu nh ất thì T(n)=O(n) (Ta ký hiệu là Tx(n)=O(n)
Vậ y thì tất nhiên phải đặt ra vấn đề : th ời gian trung bình sẽ là bao nhiêu?(Ttb(n)=?) Việc tính giá trị trung bình của thời gian th ực hiện giải thuật thường phức tạp vì nó liên quan dến tính ngẫu nhiên của các sự kiện. Nó đòi hỏi ph ải sử dụng tới phép tính xác suất và thống kê nên ta sẽ không tìm hiểu sâu ở đây. Với giải thuật tìm kiếm tuần tự, người ta chứng minh được rằng : Ttb(n)=O(n). Trong 1 số trường hợp, khi không biết Ttb(n) thì người ta có thể dùng Tx(n) để ước lượng. Tuy nhiên ta cần thấy rằng 1 cách tổng quát thì Tx(n) chỉ cho ta cận trên tố i đa của thời gian thực hiện giải thuật ngh ĩa là : “lấy già ra thì thời gian thực hiện giải thuật có bậc như vậy”( nếu bậc đó không cao thì giải thuật đó cũng “tố t”) còn thời gian trung bình có thể có bậc như thế, nhưng cũng có thể có b ậc th ấp hơn! Dù sao thì với ký pháp chữ O lớn, ta cũng biết được độ đo gần đúng của thời gian thực hiện giải thu ật khi kích th ước dữ liệu đủ lớn. Điều đó cũng giúp ta có cơ sở đ ánh giá 1 cách tương đối về thời gian này; đối với các giải thuật khác nhau. V. GIẢI THUẬT ĐỆ QUY 1. Định nghĩa C không những cho phép từ hàm này gọ i tới hàm khác, mà nó còn cho phép từ 1 điểm trong thân của hàm gọi tới chính hàm đó.Hàm như vậy gọi là hàm đệ quy. Một ví dụ khá quen thuộc về hàm đệ quy là hàm tính giai thừa của 1 số n guyên không âm : n! với quy ước 0!=1 thì hàm này được đ ịnh ngh ĩa như sau : Nếu n=0 thì n!=1 Nếu n>0 thì n!=n(n-1)! Nh ư vậy trong định nghĩa n! lại có (n-1)! Đó chính là đ ệ quy. Ví dụ ta có: 4!=4.3! 3!=3.2! 2!=2.1! 1!=1.0! nhưng 0!=1 Vậ y thì : 4!=4.3.2.1.1=24 Cách xây dựng hàm đệ quy : if ( tr−êng hîp suy biÕn) { Tr×nh bμy c¸ch gi¶i bμi to¸n khi suy biÕn } else /* Tr−êng hîp tæng qu¸t */ { Gäi ®Ö qui tíi hμm ( ®ang viÕt ) víi c¸c gi¸
trÞ kh¸c cña tham sè } 2.Ví dụ về thủ tục đệ quy a. Hàm tính n! Dựa vào đ ịnh ngh ĩa trên, giải thuật đệ quy n! được viết nh ư sau : long int gtdq(int n) { if (n== 0 || n==1) return 1; else return(n*gtdq(n-1)); } Tính đ ệ quy củ a hàm này đ ược thể h iện qua 2 đặc điểm sau : • Có 1 số trường hợp đ ặc biệt, mà ta sẽ gọi là trường hợp suy biến, ứng với 1 “tiêu chuẩn gốc” (ở đây là n=0), thì việc xử lý đ ược thự c hiện cụ thể theo 1 cách riêng. • Còn các trường hợp khác, trong xử lý đ ều có sự tham chiếu đ ến chính nó (nh ư ở đây là gọi đ ến chính nó : gtdq(n-1)). Tuy nhiên phải chú ý là khi có sự tham chiếu đến chính nó thì nó lại tiến gần hơn đ ến trường h ợp suy biến ( ở đ ây là kích th ước (n-1) sẽ nhỏ hơn n và gần tới 0 hơn n) b. Bài toán “Tháp Hà Nộ i” Đây là bài toán mang tính ch ất 1 trò chơi, nội dung như sau : Có n đĩa kích thước nhỏ d ần, đĩa có lỗ ở giữa. Có thể xếp chồng lên - nhau xuyên qua 1 cọc, to ở dưới, nhỏ ở trên, để cuố i cùng có 1 chồng đĩa như cái tháp. - Có 3 cọ c A, B, C, Hiện có n đ ĩa xếp theo hình tháp ở cọc A, yêu cầu là: 1. Mỗ i lần chỉ chuyển đ ược 1 đ ĩa. 2. Không khi nào tình huống đ ĩa to ở trên, đĩa nhỏ ở dưới. 3. Được sử dụng 1 cọc làm trung chuyển, chẳng h ạn khi chuyển đ ĩa từ cọc A sang cọc C thì cọc B được làm cọc trung chuyển. Hình 1.1 ứng với dạng ban đầu của bài toán, với n=6 C B A Hình 1.1
Trước hết ta xét bài toán đơn giản : * Trường hợp n = 1 : ch ỉ cần 1 phép chuyển - Chuyển đ ĩa đang ở A sang C * Trường hợp n = 2 : phải thực hiện 3 phép chuyển: Chuyển đ ĩa thứ nhất từ cọc A sang B: A B - - Chuyển đ ĩa thứ h ai từ cọc A sang C: A C - Chuyển đ ĩa thứ nhất từ cọc B sang C: B C - * Trường hợp n>2 Ta thấy n ếu coi (n-1) đ ĩa ở trên đóng vai trò như đĩa thứ nh ất thì hình dung như đang có 2 đĩa ở cọc A. Nếu thế thì phỏng theo trường hợp 2 ta có thể đi đ ến giải thuật sau : Chuyển (n-1) đĩa trên từ cọ c A sang B: A B - Chuyển đ ĩa thứ n từ cọc A sang C: A C - Chuyển (n-1) đĩa từ cọc B sang C: B C - Vậ y thì cách giải này mang tính ch ất đ ệ quy và giải thuật tương ứng đ ược thể hiện : # include void move(int n,int A,int B,int C); main() { int n printf(“Nhap so dia :”); scanf (“%d”,&n); move (n,1,2,3); return 0 } void move (int n,int A,int B,int C) { if (n==1) printf(“\n%d %d”,a,c);
else { move(n-1,A,C,B); move(1,A,B,C); move(n-1,B,A,C); } }