Tài liệu Cấu trúc dữ liệu phân tích thuật toán và phát triển phần mềm

H ồ THUẦN (Chủ biên) C Ấ U P H Â N v ñ T R Ú C T ÍC H P H Á T D ữ L IÇ U T H U Ộ T T O R N T R Iấ N P H Ầ N M € M NHÀ X U Ấ T BẢN G IÁO DỤC VIỆT NAM Chương I KHÁi QUÁT vế THUẬT TOnN vn cnu TRÚC DỮ Llfu 1. THUẬT TOÁN 1.1. KHÁI NIỆM THUẬT TOÁN Thuật ngữ thuật toán (Algorithm) xuất phát từ tên một nhà toán học Ảrập Abu Ja'far Mohamed ibn Musa al'Khwarizmi, thường gọi là arKhwarizmi. ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Thuật ngữ algorithm ra đời từ đó dựa theo cách phiên âm tên của ông. Cùng với thời gian khái niệm thuật toán được hoàn chỉnh dần và khái niệm hình thức chính xác của thuật toán được định nghĩa thông qua mô hình máy Turing. Giáo trình này không đi sâu vào những khía cạnh lí thuyết của thuật toán nên chỉ trình bày khái niệm không hình thức của thuật toán; Thuật toán là một hệ thống các quy tắc chặt chẽ và rỗ ràng nhằm xác định một dãy thao tác trên những đối tượng sao cho sau một số hữu hạn bước thực hiện các thao tác thì đạt được mục tiêu định trước. 1.2. CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN Một thuật toán thông thường có các đặc trưng cơ bản sau: 1.2.1. Tính kết thúc (tính dừng) Thuật toán bao giờ cũng phải dừng sau một số hữu hạn bước thực hiện. Ví dụ, các quy tắc sau không phải là thuật toán vì không có tứứi dừng: Bước 1. ỉ' <— 1, í 0 Bước 2. A'<- i’ + i Bước 3. Lặp lại bước 2. Bước 4. Dừng. Để các quy tắc trên có tứih dừng, sửa lại: Bước 3. Lặp lại bước 2 khi ỉ < 10. Tính dừng của thuật toán thực sự có ý nghĩa khi thòi gian hoàn thành thuật toán nằm trong giới hạn "chấp nhận được". Với tốc độ máy túủi như hiện nay, nhiều thuật toán được chứng minh là dừng nhưng thờigian hoàn thành là vài trăm năm, chẳng hạn như các thuật toán về giải mã văn bản mà không biết khoá giải mã. 1.2.2. Tính xác định Thuật toán yêu cầu ỏ mỗi bước các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lẫn lộn, tuỳ tiện. Khi thực hiện thuật toán, với cùng một dữ liệu vào thì cho cùng một kết quả. 1.2.3. Tính phổ dụng Thuật toán phải có thể giải được một lớp các bài toán. Mỗi thuật toán có thể làm việc với những dữ liệu khác nhau trong một miền xác định. Việc cung cấp dữ liệu vào là một cách thức để thuật toán có thể giải được bài toán tổng quát thay vì giải các bài toán với dữ liệu cụ thể. 1.2.4. Dữ liệu vào Mỗi thuật toán thường có những đại lượng vào gọi là dữ liệu vào để cung cấp dữ liệu cho thuật toán. Tuy nhiên, cũng có những thuật toán không có dữ liệu vào. 1.2.5. Dữ liệu ra Sau khi kết thúc thuật toán, tuỳ vào*chức năng của thuật toán mà thu được một số đại lượng xác định gọi là đại lượng ra hay dữ liệu ra. 1.2.6. Tính hiệu quả Vói dữ liệu vào, sau một số hữu hạn bước thực hiện thuật toán sẽ dừng và cho đúng kết quả mong muốn với thời gian chấp nhận được. Cho đến nay, mặc dù máy tính có tốc độ túih toán rất nhanh nhxmg vẫn còn nhiều bài toán mà thời gian tính toán rất lớn. Do đó con người vẫn luôn phải tìm cách để cải thiện hiệu quả thuật toán và tăng tốc độ tính toán của hệ thống máy tính. 1.3. TIÊU CHUẨN ĐÁNH GIÁ THUẬT TOÁN Một bài toán có thể có nhiều thuật toán giải, mỗi thuật toán có những ưu, nhược điểm riêng. Để quyết định chọn thuật toán nào thông thường dựa vào hai tiêu chuẩn cơ bản sau: Tiêu chuẩn 1: Thuật toán đơn giản, dễ hiểu, dễ cài đặt. Tiêu chuẩn 2: Thuật toán sử dụng tiết kiệm các tài nguyên của hệ thống máy tính như bộ nhớ, thời gian chiếm dụng CPU và đặc biệt là thời gian chạy. Trong trường hợp chương trình ít sử dụng và giá viết chương trình vượt xa giá chạy chương trình thì tiêu chuẩn 1 được ưu tiên. Với những chưoỉng trình thưòng dùng như trong các thư viện chương trình, các chương trình hệ thống thì tiêu chuẩn 2 được ưu tiên, ở đây ta không đi sâu vào tiêu chuẩn 1. Trong tiêu chuẩn 2, tính hiệu quả của thuật toán bao gồm hai yếu tố: - Dung lượng không gian nhớ cần thiết để lưu dữ liệu và các kết quả trung gian để giải bài toán (tổ chức dữ liệu cho bài toán). - Thời gian cần thiết để thực hiện thuật toán (thời gian chạy). Hai yếu tố trên thường mâu thuẫn và ảnh hưởng qua lại lẫn nhau. Thường khi chọn thuật toán ta quan tâm đến thời gian thực hiện. Mặc dù hiện nay tốc độ máy tmh ngày được cải thiện đáng kể, có thể thực hiện hàng trăm triệu phép tmh trên một giây nhưng vẫn chưa đáp ứng được cho một số thuật toán có thời gian chạy rất lớn. 1.4. Đ ộ PHỨC TẠP CỦA THUẬT TOÁN Việc đánh giá thời gian thực hiện của thuật toán phụ thuộc vào nhiều yếu tố: - Dữ liệu vào. - Tốc độ của máy tính. - Chương trình dịch và hệ điều hành dùng để thực hiện chương trình. Do đó việc đo, đếm chính xác thời gian thực hiện thuật toán là bao nhiêu đơn vị thời gian gần như không thể thực hiện được. Để có thể so sánh thời gian chạy của các thuật toán, trên phương diện lí thuyết, thời gian thực hiện thuật toán được đánh giá là một hàm phụ thuộc vào kích thước của dữ liệu vào gọi là độ phức tạp thuật toán. Để đánh giá độ phức tạp của thuật toán thông thường người ta tính số phép toán cơ bản mà thuật toán thực hiện. Một phép toán được gọi là cơ bản nếu thời gian thực hiện thuật toán tỉ lệ với số phép toán đó. Tuỳ từng thuật toán cụ thể, dễ dàng xác định được phép toán nào là cơ bản. Các phép toán cơ bản thường dùng có thể là các phép toán: +, *, /, các phép so sánh, phép gán, thao tác đọc, ghi tệp,... Tuỳ thuộc vào thuật toán, độ phức tạp là một hàm phụ thuộc vào kích thước của dữ liệu vào. Thông thường ta dùng một số nguyên n để đặc trưng cho kích thước của dữ liệu vào. Kí hiệu; D„ là tập các dữ liệu vào có kích thước n. Với mỗi bộ dữ liệu d e D„, kí hiệu costẶd) là số phép toán cơ bản mà thuật toán A phải thực hiện với bộ dữ liệu vào d (trong trường hợp không gây nhầm lẫn ta có thể kí hiệu cost{d) thay cho costẬd)). Độ phức tạp trong trường hợp tốt nhất: được đánh giá trong trường hợp bộ dữ liệu vào mà thuật toán thực hiện ít phép toán cơ bản nhất, kí hiệu Min^(n). Min^(n)= MỊn{cost^(ú?)}, ¡JeD„ Độ phức tạp trong trường hợp xấu nhất: được đánh giá trong trường hợp bộ dữ liệu vào mà thuật toán thực hiện nhiều phép toán cơ bản nhất, kí hiệu Max^(n). Max^(«)= Max{cost^(í/)}. Trong giáo trình này, khi nói đến độ phức tạp, ngầm định được đánh giá trong trường hợp xấu nhất. Khi đó kí hiệu T(n) là độ phức tạp của thuật toán với dữ liệu vào có kích thước n. Ví dụ 1. Thuật toán tìm số nhỏ nhất trong một mảng các số nguyên a{ì..n]\ M in := a[l] ; F o r i :'=2 t o n d o i f M in>a[i] th en M in ;= a [i]; + Kích thước của dữ liệu vào được đặc trưng bởi số phần tử của mảng mà ta eần tìm số nhỏ nhất. + Phép toán cơ bản của thuật toán là phép so sánh trong biểu thức Min > a[ĩ\. + Số phép so sánh trong trưòfng hợp tốt nhất và xấu nhất đều là n - 1. + Vậy độ phức tạp thuật toán tìm số nhỏ nhất trong mảng có n phần tử là T(«) = n - \ . Trong trưcmg hợp thuật toán thực hiện nhiều phép toán cơ bản, ta có thể đánh giá độ phức tạp trên từng loại phép toán hoặc tổng hợp của các phép toán bằng cách gán trọng số cho từng phép toán. Ví dụ 2. Thuật toán nhân hai ma trận a„,x„ và b„^p. Kết quả lưu vào ma trận c„,xpi F o r i : =1 t o m d o F o r j : =1 t o p d o B egin c [ i , j ] :=0; For k : = l t o n do c [i,j]:= c [i,j]+ a [i,k ]* b [k ,j]; End; Đánh giá độ phức tạp của thuật toán: + Đặc trưng kích thước dữ liệu vào: giả sử n là số lớn nhất trong ba số m, n, p. Khi đó ta lấy n là đại lượng đặc trưng cho dữ liệu vào. + Phép toán cơ bản: thuật toán sử dụng hai phép toán cơ bản là phép cộn^ (+) và phép nhân (*). Dễ tíiấy độ phức tạp được tính trong trường hợp tốt nhất và xấu nhất là như nhau, cụ thể: + Số phép cộng: Tl(n) = m.(n - 1 ).p\ + Số phép nhân: T2{n) = m.n.p-, + Không mất túih tổng quát ta có thể giả thiết m = n= p v ằ xem phép nhân là phép toán cơ bản, ta có thể đánh giá độ phức tạp của thuật toán nhân hai ma trận vuông có kích thước nxn là: T{n) = n^. Ví dụ 3. Thuật toán tìm một phần tử X trong danh sách L e ó n phần tử bằng cách tìm tuần tư. fou n d := F alse; F o r i :=1 t o n do I f L [i] = X then B egin found:=T rue; E xit; End; + Do phiic tap duac danh gia qua s6' l^n thiic hien phep so sanh L[/]=jf. + Truofng.hop tot nhat: so Ian so sanh la 1, trong tnicmg hop ph^n tu can tim x la ph^n tu dau tien cua danh sach. Do do Min(n) =1. + TnJotig hop xau nhat la ph^n tir c^n tim khong c6 trong danh sach. Khi do Max(«) = n. Vi du 4. Thu^t toan sap xep day so a[\..n] tang ddn. For i : = l t o n - 1 do For j ; = i + l If t o n do a [i]> a [j] then B egin tg := a [i] ; a [i]:= a [j]; a[j]:= tg; E nd ; Do phlic tap cua thuat toan diioc danh gia trdn hai phep toan cd ban la phep so s^nh trong bieu thurc di^u kien cua lenh //v a phep gan, ki hieu tuong ling la C{n) va M(n). Do phlic tap duoc danh gia trong trucmg hop "xa'u" nhat cua dii lieu vao la day so b tinh trang thii tu giam. Khi do ta tinh dugc: n + So phep so sanh C{n) = ( « - ! ) —. + So phep gan M(n) = 3(n ~ • Danh gia thuat toan trong trucmg hop thuan Igi nha't, Irudng hop day so da sap theo thii tu tang. Khi do: + So phep so sanh C{n) = { n - 1) + So phep gan M(n) = 0. 2.CTDL..- PTPMEMA . 1.5. ĐỘ PHỨC TẠP TRUNG BÌNH Việc đánh giá độ phức tạp của thuật toán trong trường hợp xấu nhất hay tốt nhất trong nhiều trường hợp không thể hiện được tính "phức tạp" của thuật toán vì căn cứ vào những trường hợp dữ liệu vào có tính đặc thù. Độ phức tạp trung bình: gọi piđ) là xác suất để bộ dữ liệu d e D„ được chọn. Độ phức tạp trung bình của thuật toán A trong tnicmg hợp kích thước dữ liệu vào là n, kí hiệu Avg^(rt): Avg^(n) = X P (d).cost^(d). deD„ Việc túih độ phức tạp trung bình trong nhiều trường hợp rất khó khăn. Để thuận lợi trong tính toán, chúng ta xét một số trường hợp sau: i) Min^(n) < Avg^(n) < Max^(rt) ii) Phân bố của dữ liêu vào là phân bố đều, khi đó p{d) = A vg»= (điều này luôn đúng). D . Do đó ^co st^(tí?). deD„ Giả sử D„ được phân hoạch thành D „ J u D „2 u ... u D„„„ trong đó D „J là tập các bộ dữ liệu mà độ phức tạp của thuật toán A trên các bộ dữ liệu này đều bằng nhau và được kí hiệu là cost^(D„y). Gọi p(D„j) là xác suất để một bộ dữ liệu của D„ thuộc vào D„J. Khi đó ta có: iii) Avg^(n)= X P(D„j) .cosị^{D„j). Ví dụ. Tính độ phức tạp trung bình của thuật toán tìm kiếm tuần tự. Gọi: q là xác suất để X có mặt trong danh sách. Sự xuất hiện của X tại vị trí bất kì của danh sách là như nhau. 1 - ợ là xác suất để X không có mặt trong danh sách. Phân hoạch D„ thành các tập: Z)„o là tập các bộ dữ liệu thuộc D„ mà không chứa phần tử cần tìm X. là tập các bộ dữ liệu thuộc D„ mà phần tử đầu tiên bằng JClà phần tử thứ nhất. D„J là tập các bộ dữ liệu thuộc D„ mà phần tử đầu tiên bằng Xlà phần tử thứ j. D„„ là tập các bộ dữ liệu thuộc D„ mà phần tử đầu tiên bằng Xlà phần tử thứ n. Khi đó: 10 2.CTDL...PTPWẾM.B 7=0 Vì cost^(D„o) = n, p ( D J = I - q , p(D ) = - , y = 1..« nên ta CÓ: n A vg^{n)= p(D Jcosi^(D J + ỲpiD„j).cost^{D„j) J=\ = ( l - q ) n + -^ ¿co st^ (Z ) ) = ( ! - < ? ) « + ^ ¿ 7 = (1-< 7)«+ 1 qn .... + — 1 q. =n- — Xét các trường hợp đặc biệt: a) í/ = 1 trường hợp X luôn có mặt trong mọi bộ dữ liệu. Khi đó độ phức tạp trung bình của thuật toán tìm tuần tự là: Avg^(n)= (« + 1) Với n = 33 thì Avg^(rt)= 25. . K í hiệu 0-lớn Việc đánh giá độ phức tạp của thuật toán qua hàm T(/i) như trên quá chi tiết vào các phép toán thực hiện của thuật toán nên khó khăn trong việc so sánh và phân lớp các thuật toán. Để thể hiện bản chất hơn độ phức tạp của thuật toán phụ thuộc vào kích thước dữ liệu vào ta dùng khái niệm O-lớn (big O). Cho /(n), g{n) là hai hàm xác định trên tập số nguyên không âm (tập số tự nhiên N) có miền giá trị là R”", tập các số thực không âm, có nghĩa/, N w . Ta nói f{n) là 0-lớn của g{n), kí hiệu /(n) = 0(g(n)), nếu và chỉ nếu tồn tại các hằng số dương c và n,) sao cho với mọi n > «0 ta có f(n) < c.g(n). Ví dụ. Nếu f(n) = 3/í' + 2« - 10 thì/(«) = 0(n'). Kí hiệu O-lớn cho ta phân lớp các hàm theo độ tăng của nó. Một số lớp thường dùng trong đánh giá độ phức tạp thuật toán qua kí hiệu 0-lớn. 11 K í hiệu 0-1ớn 0(1) O(logn) 0(n) O(nlogn) Tên g ọ i thường dùng hằng lôgarit tuyến tính nlogn 0 {rĩ) bình phương 0(2") mũ Độ tăng của các hàm thể hiện qua đồ thị sau: n Một số quy tắc tính độ phức tạp qua kí hiệu O-lớn: a) Quy tắc tổng Nếu thuật toán gồm hai phần thực hiện tuần tự, phần thứ nhất có độ phức tạp được đánh giá là T,(n) = 0(/ì(aỉ)) và phần thứ hai được đánh giá là TịÍ«) = oự^in)) thì độ phức tạp của toàn bộ thuật toán là T(«) = Ti(«) + T2(rt)= 0(max(/',(/ỉ),/2(rt)). b) Quy tắc nhân Nếu một thuật toán gồm f(n) lần thực hiện công việc c, trong hiện g(n) lần phép toán cơ bản, khi đó độ phức tạp của thuật toán là: T(n) =fin)xg(n). Trường hợp/(n) = 0(/i|(«)) và g(n) = 0(/í2(«)), ta có: T(n) = ự.g)(n) = 0 (/i,(rt)./ỉ2(/ĩ)). 12 đó công việc c thực 2. KIỂU D ữ LIỆU VÀ CẤU TRÚC DỮ LIỆU 2.1. KIỂU DỮ LIỆU Mọi dữ liệu lưu trữ trong máy tính đều được biểu diễn dưới dạng mã nhị phân. Việc sử dụng trực tiếp các số nhị phân trong máy tính là một công việc khó khăn cho người lập trình. Chính vì lí do này mà các ngôn ngữ lập trình bậc cao đã xây dựng các kiểu dữ liệu. Một kiểu dữ liệu là sự trừu tượng hoá các thuộc tính bản chất của các đối tượng trong thực tế và phù hợp với cách tổ chức thông tin trên máy tính, chẳng hạn như các kiểu số nguyên, số thực, logic,... Một kiểu dữ liệu T là một bộ T = , trong đó V là tập các giá trị hợp lệ của kiểu T và ơ là tập các phép toán trên kiểu T. Ví dụ. Kiểu dữ liệu Byte = <ì'^Byic> với = {0, 1, 255}, ỠBy„ = {+, *, div, mod, >, >=, <, <=, =, <>} 2.2. CẤU TRÚC DỮ LIỆU Các kiểu dữ liệu cơ sở không đủ để mô tả các đối tượng của thế giới thực nên các ngôn ngữ lập trình bậc cao cho phép kết hợp các kiểu dữ liệu cơ sở để tạo nên kiểu dữ liệu mới phức tạp hơn được gọi là kiểu dữ liệu có cấu trúc. Các kiểu dữ liệu có cấu trúc thưòng dùng trên các ngôn ngữ lập trình bậc cao như; Aưay, String, Record, File,... là các cấu trúc dữ liệu thường dùng. 2.3. MÔ HÌNH DỮ LIỆU Các bài toán thực tế cần phải giải trên máy tính ngày càng phức tạp và đa dạng, do đó trước khi tổ chức các cấu trúc dữ liệu mô tả bài toán, người lập trình thường phải dùng các mô hình toán học để biểu diễn các đối tượng của bài toán và mối liên hộ giữa các đối tượng. Việc sử dụng các mô hình toán học cho phép người lập trình mô tả chính xác bản chất của các đối tượng trong bài toán và việc sử dụng toán học như một công cụ giúp việc giải các bài toán dễ dàng, chính xác hơn trước khi giải bài toán trên máy tính bằng chương trình. Mô hình toán học có thể biểu diễn được trên máy tính gọi là mô hình dữ liệu. Mô hình dữ liệu muốn cài đặt được trên máy tính phải có một cách tổ chức dữ liệu phù hợp. Các mô hình dữ liệu thường được sử dụng trong các bài toán tin học là danh sách, cây, đồ thị, bảng băm, quan hệ,... 2.4. CÁC TIÊU CHUẨN CỦA CẤU TRÚC DỮ LIỆU Khi tổ chức dữ liệu cho một bài toán thường dựa vào các tiêu chuẩn sau để lựa chọn cách tổ chức dữ liệu tối ưu. Phản ánh đúng thực tế: Đây là tiêu chuẩn quan trọng nhất, quyết định túih đúng đắn của toàn bộ quá trình giải bài tõán. Trong khi tổ chức dữ liệu cũng dự tính các trạng thái biến đổi của dữ liệu trong tương lai để đảm bảo cho chương trình hoạt động được lâu dài. 13 Các thao tác phù hợp: Mỗi cấu trúc dữ liệu có thể biểu diễn được một tập các đối tượng và có một tập các phép toán phù hợp. Việc chọn cách tổ chức dữ liệu không chỉ biểu diễn được các đối tượng của bài toán mà còn phải phù hợp với các thao tác trên đối tượng đó, có như vậy ta mới xây dựng được thuật toán giải bài toán đơn giản hơn. Tiết kiệm tài nguyên hệ thống: Khi tổ chức dữ liệu chỉ nên sử dụng tài nguyên hộ thống vừa đủ đáp ứng được yêu cầu công việc, tránh lãng phí. Có hai loại tài nguyên quan trọng của hộ thống là bộ nhớ và thời gian chiếm dụng CPU để thực hiện các thao tác trên dữ liệu. Thông thưòng hai loại tài nguyên này thường mâu thuẫn nhau trong khi giải các bài toán. Tuy nhiên, nếu tổ chức khéo léo chúng ta cũng có thể tiết kiệm được cả hai loại tài nguyên. 3. MỐI LIÊN HỆ GIỮA CÂU TRÚC DỮ LIỆU VÀ THUẬT TOÁN Trong khi giải một bài toán, thông thưcíng ta chỉ chú trọng đến thuật toán (hay cách giải của bài toán) mà ít khi quan tâm đến việc tổ chức dữ liệu. Tuy nhiên giữa việc tổ chức dữ liệu và thuật toán có mối liên hệ chặt chẽ với nhau. 3.1. MỐI LIÊN HỆ Theo cách tiếp cận của lập trình cấu trúc, Niklaus Wirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và thuật toán: THUẬT TOÁN + CẤU TRÚC DỮ LIỆU = CHƯƠNG TRÌNH (Algorithms + Data Structures = Programs) Một thuật toán giải' bài toán bao giờ cũng thao tác trên một cách tổ chức dữ liệu (cấu trúc dữ liệu) cụ thể và các thao tác phải được cấu trúc dữ liệu đó hỗ trợ. Khi tổ chức dữ liệu cho bài toán thay đổi thì thuật toán cũng phải thay đổi theo cho phù hợp với cách tổ chức dữ liệu mới. Ngược lại, trong quá trình xây dựng, hoàn thiện Ihuật toán cũng gợi mở cho người lập trình cách tổ chức dữ liệu phù hợp với thuật toán và tiết kiệm tài nguyên hệ thống. Chẳng hạn, dùng thêm các ô nhớ phụ để lưu các kết quả trung gian và giảm thời gian tính toán. Quá trình giải một bài toán trên máy tính là một quá trình hoàn thiện dần cách tổ chức dữ liệu và thuật toán để tiết kiệm tài nguyên của hệ thống. 3.2. MỘT SỐ Ví DỤ MINH HOẠ Ví dụ 1. Xét bài toán đổi giá trị hai biến X, >». Với bài toán này ta có hai phương án giải như sau: Phương án 1. Dùng ô nhớ trung gian tg := x ; x := y; y := tg; 14 Phương án 2. Không dùng biến trung gian. X := X + y; y := X - y; X ;= X - y; Qua ví dụ đơn giản trên, ta nhận thấy việc tổ chức dữ liệu khác nhau (dùng hay không dùng biến trung gian) ảnh hưcmg rất lớn đến thuật toán và gần như thay đổi toàn bộ thuật toán. Hơn nữa, nó còn ảnh hưởng đến tmh hiệu quả và phạm vi ứng dụng của thuật toán. Ví dụ 2. Xét bài toán tmh số tổ hợp chập k của n phần tử C *. Phương án 1. Dùng đinh nghĩa C* = -----—---- . Giả sử gt(n) là hàm trả về n!. Ta k \{ n -k )\ có hàm tính hệ số C* như sau: F u n c t i o n H e S o ( n , k :w o r d ) : L o n g i n t ; Begin HeSo ;= g t ( n ) d iv gt(k) d iv g t ( n - k ) ; End; Nhận xét: Với thuật toán này các chương trình chỉ tính được vì phải lưu các kết quả trung gian rất lớn là với các số n, k nhỏ n- Phương án 2. Dùng công thức C* = c*r,' + c*_|, với c “=l, c ,'= l. Hàm tính C* được viết dưới dạng đệ quy như sau: F u n c tio n H eSo(n, k ; word) : L ongin t; B egin if (k =0 ) or (k=n) then H eSo:=l else HeSo := H e S o ( n - l , k - l ) + H eS o (n -1 ,k ); End; Nhận xét: Với thuật toán này khắc phục việc phải lưu các giá trị trung gian lớn nhưng hạn chế của thuật toán là phải tính lại nhiều lần các giá trị đã túih ở bước trước, chẳng hạn để tính cị chương trình phải lặp lại hai lần tính c l , ba lần tmh c\ Phương án 3. Dùng một mảng hai chiều C[0..n,0..^] mỗi phần tử có kiểu Longlnt để lưu các kết quả trung gian trong khi tính C *, với C[i, J]= c i (0 < j < i, j < k, i < n). Từ công thức C* = c*r,' + c*_,, ta có mảng c duiỉg để tính cụ, J]= C [i-ỉ,j -1]+C[/ -1 , /Ị. Bảng dưới đây minh hoạ Cj. 15 0 F u n c tio n H eSo(n, Var i , j 1 2 3 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 5 1 5 10 10 k ; word) : L on gin t; : word; c : a r r a y [ 0 . . n , 0 . . k] o f L on gin t; B egin For i : = l t o n do C [ i , 0 ] : = l ; F o r j :=1 t o k d o B egin C[ j , j ] : = 1 ; For i : = j + l t o n do C [i,j] := C [i-l,j-l]+ C [i-l,j] ; End; H eS o := C [n ,k ]; End; Nhận xét: Phương án này còn nhiểu ô nhớ của mảng không dùng, cụ thể là các ô nằm ở phần trên đường chéo chính. Vì mục đích của bài toán là tính giá trị mà không cần các giá trị trung gian nên ta có thể tổ chức bộ nhớ tiết kiệm hơn bằng cách dùng một mảng một chiều. Phương án 4. Dùng mảng một chiều H[ồ..k] để lưu các giá trị của từng dòng trong mảng c của phưoỉng án trên. Mảng H được tính qua n bước, tại bước thứ ỉ, H là dòng thứ i của mảng c, cụ thể tại bước thứ i, //[/]= c/ , với j < i. F u n c tio n H eSo(n ,k :W ord ):L on gIn t; v a r H; a r r a y [ 0 . . 1 0 0 0 ] i,j o f L ongln t; ; Word; B egin for i: = l t o k do H [ i ] : = 0 ; H [0]:=1; for j:= l 16 t o n do for i : =k d o w n t o 1 d o H [i]:= H [i]+ H [i-l]; H eso:=H [k]; E nd ; Nhận xét: Với phương án này vừa tiết kiệm được bộ nhớ vừa tăng khả năng tính toán với n, k lớn hofn các phương án khác. 4. PHÁT TRIỂN CHƯƠNG TRÌNH BẰNG t in h chế ‘ DẦN TÙNG B ư ớ c Khi phát triển một chương trình ta thưcmg tiến hành qua các bước sau: Hiểu rỗ yêu cầu bài toán: Trong bước này người lập trình phải hiểu đúng bài toán cần giải và nếu có thể hãy diễn đạt lại bài toán bằng các kí hiệu toán học hoặc các công thức. - Hình thành ý tưởng về cách giải bài toán: Trước khi giải một bài toán bằng máy tữih, chúng ta phải phác thảo cách giải dưới dạng ý tưởng. Ý tưcmg này được hình thành dựa trên những kiến thức về giải các bài toán tương tự hoặc các phương pháp thiết kế thuật toán đã biết. Ý tưởng về cách giải này sẽ được cụ thể dần ở các bước sau và cũng có thể không thực thi được sau khi đã cụ thể hoá. Khi đó phải hình thành ý tưởng khác (cách giải khác). Cụ thể ý tưởng bằng mô tả thuật toán dưới dạng "thô": Ý tưcmg của thuật toán được mô tả bằng một thuật toán dạng thô hay còn gọi là thuật toán mô tả ở mức 0. Việc mô tả này thưòfng dùng ngôn ngữ tự nhiên vì còn nhiều điều trong thuật toán chưa tường minh. Việc mô tả ở bước này là cần thiết để tránh việc người lập trình quá quan tâm đến chi tiết các thao tác làm phân tán tư tưởng cũng như định hướng ban đầu. Trong bước này, dùng chiến thuật "chia để trị", các chức năng của thuật toán được mô tả hình thức dưới dạng các thao tác chưa tường minh. Tỉnh chế dẩn từng bước thuật toán: Thuật toán mô tả dạng thô ở bước trên được tinh chế dần từng bước cho đến khi có thể lập trình được. Các mô tả chưa tường minh trong thuật toán sẽ được chi tiết dần trong bước này. Việc chi tiết được thực hiện từng bước, qua mỗi bước thuật toán sẽ được cụ thể dần bằng các thao tác, gần với ngôn ngữ lập trình. Quá trình này được lặp lại nhiều lần và chỉ dừng lại khi tất cả các bước của thuật toán đã được tường minh với việc cài đặt là dễ dàng. Cài đặt chương trình cho thuật toán'. Đây là bước cụ thể hoá thuật toán đã được tường minh ở bước trên bằng chương trình. Bước này sẽ dễ dàng nếu ở bước trước ta mô tả thuật toán bằng giả mã hoặc bằng một ngôn ngữ lập trình cụ thể. Tinh chế còn được gọi là làm mịn. 3.CTDL...PTPMỂMJk 17 ở bước này, công việc chủ yếu là tổ chức chương trình thành các đơn thể (đối với lập trình cấu trúc) hoặc các lớp đối tượng (đối với lập trình hướng đối tượng). Xét một ví dụ về sắp xếp dãy số a[\..n\ theo thứ tự không giảm. - Hiểu rõ bài toán: Đổi chỗ các phần tử trong dãy số sao cho a[ỉ] ì, i =1, 2,..., n -1, phần tử a, là phần tử ngay trước phần tử và là phần tử ngay sau phần tử ũ ị . Trong một danh sách các phần tử có thể giống nhau. Danh sách con Cho L = (aj, ữ2, (3„) là một danh sách và /, j là các vị trí trong danh sách (1< i < j < n). Danh sách L = (6|, ¿ 2trong đó ố, = ú!ị, = «i+i. bj.M=aj được gọi là danh sách con của danh sách L. Dãy con Danh sách L' được tạo thành từ danh sách L bằng cách bỏ đi một số phần tử của danh sách L nhưng vẫn giữ nguyên thứ tự được gọi là dãy con của danh sách L. Ví dụ: L = (1, 5, 2, 5, 7, 2), L, = (5, 2, 5) là danh sách con của L, ¿2 = (1, 5, 7, 2) là dãy con của danh sách L. Trong thực tế có rất nhiều dữ liệu được tổ chức dưới dạng danh sách như danh sách nhân viên trong một cơ quan, danh sách các môn học, danh bạ điện thoại,... 1.1.2. Các thao tác trên danh sách Tuỳ thuộc từng loại danh sách sẽ có các thao tác đặc trưng riêng. Trên danh sách ứiường thực hiện các thao tác cơ bản sau: 20