Cấu trúc dữ liệu

Chương 1: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁN 1. Giải bài toán trên máy tính Xác định bài toán Việc xác định bài toán tức là phải xác định xem ta phải giải quyết vấn đề gì?, với giả thiết nào đã cho và lời giải cần phải đạt những yêu cầu nào. Input → Process → Output (Dữ liệu vào → Xử lý → Kết quả ra) Đối với những bài toán tin học ứng dụng trong thực tế, lời giải cần tìm chỉ cần tốt tới mức nào đó, thậm chí là tồi ở mức chấp nhận được. Bởi lời giải tốt nhất đòi hỏi quá nhiều thời gian và chi phí. Ví dụ: Khi cài đặt các hàm số phức tạp trên máy tính. Nếu tính bằng cách khai triển chuỗi vô hạn thì độ chính xác cao hơn nhưng thời gian chậm hơn hàng tỉ lần so với phương pháp xấp xỉ. Trên thực tế việc tính toán luôn luôn cho phép chấp nhận một sai số nào đó nên các hàm số trong máy tính đều được tính bằng phương pháp xấp xỉ của giải tích số Xác định đúng yêu cầu bài toán là rất quan trọng bởi nó ảnh hưởng tới cách thức giải quyết và chất lượng của lời giải. Một bài toán thực tế thường cho bởi những thông tin khá mơ hồ và hình thức, ta phải phát biểu lại một cách chính xác và chặt chẽ để hiểu đúng bài toán. Ví dụ: • Bài toán: Một dự án có n người tham gia thảo luận, họ muốn chia thành các nhóm và mỗi nhóm thảo luận riêng về một phần của dự án. Nhóm có bao nhiêu người thì được trình lên bấy nhiêu ý kiến. Nếu lấy ở mỗi nhóm một ý kiến đem ghép lại thì được một bộ ý kiến triển khai dự án. Hãy tìm cách chia để số bộ ý kiến cuối cùng thu được là lớn nhất. • Phát biểu lại: Cho một số nguyên dương n, tìm các phân tích n thành tổng các số nguyên dương sao cho tích của các số đó là lớn nhất. Trên thực tế, ta nên xét một vài trường hợp cụ thể để thông qua đó hiểu được bài toán rõ hơn và thấy được các thao tác cần phải tiến hành. Đối với những bài toán đơn giản, đôi khi chỉ cần qua ví dụ là ta đã có thể đưa về một bài toán quen thuộc để giải. Lựa chọn hoặc thiết kế thuật toán a. Lựa chọn thuật toán Chúng ta biết rằng mỗi thuật toán chỉ giải một bài toán, một bài toán có nhiều thuật toán để giải. Vì vậy cần phải chọn một giải thuật phù hợp để giải bài toán đã đặt ra sao cho đạt hiệu quả nhất. Việc chọn một thuật toán để giải bài toàn ta thường quan tâm đến các yếu tố sau: yếu tố không gian để biểu diễn bài toán, lưu trữ các kết quá tính toán trung gian, kết quả của bài toán, yếu tố về mặt thời gian chạy của chương trình và yếu tố thuật tiện cho việc cài đặt thuật toán. Ngoài ra, ta còn phải căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép của hệ thống. b) Diễn tả thuật toán Việc diễn tả một thuật toán có thể bằng cách liệt kê, sơ đồ khối hoặc bằng một ngôn ngữ điều khiển Vi dụ. Thuật chia Ơ-clit Sẽ tồn tại duy nhất hai số nguyên q và r sao cho a = q.b + r với 0 £ r < b, trong đó q được gọi là thương của phép chia a cho b và r được gọi là phần dư. Cho trước a và b, ta cần tìm q và r. Ta có: C Input: Hai số nguyên dương a và b; C Output: Đưa ra thương số q và số dư r. ª Ý tưởng: Nếu a b thì a giảm đi một giá trị bằng b và q tăng lên 1. Quay trở lại lặp cho đến khi a < b thì kết thúc. Bước 3: Viết chương trình Việc viết chương trình là một tổng hợp hữu cơ giữa việc lựa chọn cấu trúc dữ liệu và ngôn ngữ lập trình để diễn đạt đúng thuật toán. Bên cạnh là thuật chia Ơ-clit viết bằng ngôn ngữ Pascal. Bước 4: Hiệu chỉnh Sau khi được viết xong, chương trình vẫn còn có thể có nhiều lỗi khác nhau chưa phát hiện được.Vì vậy, cần phải thử chương trình bằng cách thực hiện nó với một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán. Các bộ Input này được gọi là các test. Bước 5: Viết tài liệu Tài liệu phải mô tả chi tiết bài toán, thiết kế thuật toán, chương trình, kết quả thử nghiệm và hướng dẫn sử dụng. Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi mà ta cho là chương trình đó làm việc đúng đắn. 2. Mô hình dữ liệu (Data Model) Mô hình dữ liệu là các trừu tượng dùng để mô tả bài toán: Mô hình toán học, ví dụ đồ thị, tập hợp, danh sách, cây... Một mô hình dữ liệu thường có hai khía cạnh: Giá trị mà đối tượng có thể nhận được, ví dụ đối tượng nhận giá trị nguyên, thực,… Đó là khía cạnh tĩnh (static) của mô hình dữ liệu, nó cho biết những giá trị mà một đối tượng có thể nhận được. Thành phần tĩnh này gọi là kiểu dữ liệu (type data). Các phép toán ( operation) trên mô hình đó, ví dụ: các phép cộng trừ số nguyên, số thực chẳng hạn. Đây là khía cạnh động ( dynamic) của mô hình, cho biết cách thức thay đổi giá trị để thu được giá trị mới. Mô hình dữ liệu của các ngôn ngữ lập trình Mỗi chương trình có quyền truy/xuất đến các “ hộp” có thể xem như những vùng lưu trữ. Một hộp có một kiểu (type), chẳng hạn như Int hoặc Char. Thường ta gọi những giá trị được lưu trong hộp là các đối tượng dữ liệu (data object). Ta hoàn toàn có thể đặt tên cho các hộp này. 3. Kiểu dữ liệu có cấu trúc Trong thực tế chỉ với các kiểu dữ liệu cơ sở không đủ biểu diễn các bài, dẫn đến nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành phần dữ liệu có kiểu dữ liệu đã được định nghĩa. Những kiểu dữ liệu được xây dựng như thế gọi là kiểu dữ liệu có cấu trúc (hay còn gọi là cấu trúc dữ liệu). Đa số các ngôn ngữ lập trình đều cài đặt sẵn một số kiểu có cấu trúc cơ bản như mảng, chuỗi, tập tin, bản ghi...và cung cấp cơ chế cho lập trình viên tự định nghĩa kiểu dữ liệu mới. Giả sử đã có cấu trúc phù hợp để lưu trữ một sinh viên, nhưng thực tế lại cần quản lý nhiều sinh viên, lúc đó nảy sinh nhu cầu xây dựng kiểu dữ liệu mới...Mục tiêu của việc nghiên cứu cấu trúc dữ liệu chính là tìm những phương cách thích hợp để tổ chức, liên kết dữ liệu, hình thành các kiểu dữ liệu có cấu trúc từ những kiểu dữ liệu đã được định nghĩa.   4. Khái niệm thuật toán 4.1. Khái niệm thuật toán Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này ta nhận được Output cần tìm. Ví dụ: Cần tìm giá trị lớn nhất của dãy số a1, a2,..…,an, Ta xác định bài toán gồm: - Input : Số nguyên dương N và dãy số a1, a2, ,..., aN. - Output : Tìm Max là giá trị lớn nhất của dãy đã cho. Ý t ưởng thuật toán: Giả thiết Max=a1.Bắt đầu từ số hạng thứ 2 đến số hạng thứ N, lần lượt đối sánh ai với Max. Với mỗi i, nếu ai > Max thì thay giá trị Max hiện thời bằng ai. 4.2. Mô tả thuật toán a) Cách liệt kê Cách này sử dụng ngôn ngữ tự nhiên, kết hợp với ngôn ngữ toán học thông thường để liệt kê các bước và các thao tác của thuật toán. Trong mỗi bước xác định các thao tác cần thực hiện và thứ tự thực hiện các bước tiếp theo. Ví dụ, với bài toán đã xác định ở trên, ta có thể mô tả thuật toán giải bằng cách liệt kê như sau: Bước 1. Nhập N và dãy a1, ..., aN Bước 2. Đặt Max = a1, i = 2. Bước 3. Nếu i > N thì chuyển đến bước 5. Bước 4. 4.1. N ếu ai > Max thì đ ặt Max = ai. 4.2. Đ ặt i=i+1 ( T ăng i lên 1) rồi quay lại bước 3. Bước 5. Đưa ra Max rồi kết thúc. b) Sơ đồ khối - Để có thể mô tả thuật toán một cách trực quan, người ta dùng một số hình vẽ kết hợp chú thích bằng lời. Thường hay dùng các hình vẽ chủ yếu sau: v Hình ôvan để mô tả việc vào/ ra dữ liệu v Hình chữ nhật mô tả các thao tác tuần tự v Hình thoi mô tả việc kiểm tra điều kiện v Mũi tên để xác định thứ tự thực hiện các khối công việc. - Chẳng hạn, tương ứng với cách liệt kê ở mục a) là sơ đồ khối như hình bên c) Ngôn ngữ điều khiển Cách thức này dựa trên hệ thống dùng các ký hiệu và quy tắc để mô tả thuật toán một cách nhất quán, tựa một ngôn ngữ tự nhiên nào đó bằng một số cách nói như “trong khi một điều kiện thoả mãn thì lặp lại một nhóm thao tác“ hay “nếu một điều kiện thoả mãn thì thực hiện nhóm thao tác này ngược lại thực hiện nhóm thao tác kia” hay “sau thao tác này thì thực hiện thao tác kia”. Như vậy, các diễn đạt đó chỉ rõ cách thiết lập thứ tự các thao tác và được gọi là cấu trúc điều khiển. Cấu trúc điều khiển chính là cách mô tả thuật toán của các ngôn ngữ lập trình bậc cao. PROCEDURE GREEDY ( var G: GRAPH ; var Newclr: SET ); begin {1} Newclr := Æ; {2} for (mỗi đỉnh v chưa tô màu của G) do {3} if (v không được nối với một đỉnh nào trong Newclr) then Begin {4} đánh dấu v đã được tô màu; {5} thêm v vào Newclr; End; End; 4.3. Các đặc trưng của thuật toán a) Tính kết thúc (tính đóng) - Thuật toán phải đưa ra Output sau hữu hạn bước thực hiện. Ví dụ thuật toán tìm Max của dãy số nêu trên chắc chắn sẽ kết thúc sau N bước thực hiện và đưa ra được giá trị Max cần tìm. - Lưu ý rằng số bước của một quy tắc thao tác có thể là hữu hạn nhưng quy tắc đó không có tính dừng. Ví dụ, xét quy tắc sau: Bước 1: Xoá bảng Bước 2: Vẽ hình tròn Bước 3: Quay lại bước 1 - Quy tắc đó có 3 bước nhưng việc thực hiện khụng có tính dừng và vì vậy quy tắc trên không phải là thuật toán. b) Tính xác định (đơn nghĩa) - Tính xác định của giải thuật đòi hỏi ở mỗi bước các thao tác phải hoàn toàn xác định, đơn trị không có sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác, sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác để được thực hiện tiếp theo. - Nhờ tính chất này mà việc thực hiện thuật toán thuần tuý mang tính cơ học, không cần bất kỳ một sự chỉ dẫn nào về cách giải bài toán cả. c) Tính chi tiết Phụ thuộc vào đối tượng thực hiện thuật toán mà xác định chi tiết các thao tác sao cho đối tượng đó có thể thực hiện được thuật toán. d) Tính phổ dụng - Tính phổ dụng có nghĩa là một giải thuật có thể được áp dụng với một lớp các bài toán với input thay đổi chứ không chỉ áp dụng cho một trường hợp cụ thể. Ví dụ, thuật toán tìm Max nêu trên có thể áp dụng cho bất kỳ dãy số nào và với số hạng N là tùy chọn. - Cần lưu ý là trong khi tính dừng và tính xác định là điều kiện cần để một quá trình là một thuật toán thì tính phổ dụng chỉ là một tính chất thường thấy vì có nhiều bài toán có input hoàn toàn xác định, không tồn tại một lớp các bài toán tương tự. e) Đại lượng vào Mỗi giải thuật có một hoặc nhiều đại lượng vào. Ví dụ, thuật toán Max có các đại lượng vào là N và dãy số a1, ..., aN f) Đại lượng ra Sau khi giải thuật đã được thực hiện xong nó phải cho ra kết quả: Ví dụ, thuật toán Max phải cho ra giá trị Max của dãy số đã cho. g) Tính hiệu quả - Đối với một bài toán, có thể có nhiều thuật toán nhưng chúng phải cho cùng một output đối với một input. Tuy nhiên chúng có thể khác nhau về hiệu quả: - Hiệu quả thời gian: Tốc độ xử lý là nhanh hay chậm. Ta có thể đánh giá căn cứ vào số bước thực hiện. - Hiệu quả không gian: Có thể đánh giá không gian lưu trữ theo số các đối tượng dùng để ghi nhớ các kết quả (kể cả kết quả trung gian). - Thực tế sử dụng cho thấy thách thức về không gian lưu trữ có thể giải quyết dễ hơn thách thức về thời gian thực hiện. 4.4. Phân tích thuật toán 4.4.1. Tính hiệu quả của một thuật toán Khi giải quyết một vấn đề, chúng ta cần chọn một trong số các thuật toán mà chúng ta cho là “tốt” nhất. Thông thường có hai tiểu chuẩn để lựa chọn một thuật toán: (1). Thuật toán dễ hiểu, dễ cài đặt, dể gỡ rối (2). Thuật toán tiết kiệm tài nguyên của máy tính và thời gian thực hiện nhanh có thể được. Tiêu chuẩn (1) thường được sử dụng cho các chương trình sử dụng một lần hoặc một số ít lần, còn tiêu chuẩn (2) thường được sử dụng cho các chương trình sử dụng nhiều lần, có một số lượng lớn dữ liệu đầu vào. Trong quá trình phân tích, đánh giá thuật toán thì tiêu tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán. Tính hiệu quả của một thuật toán phụ thuộc và hai yếu tố cơ bản: (2.1). Dung lượng bộ nhớ cần thiết để lưu trữ tập dữ liệu vào, các kết quả tính toán trung gian và tập dữ liệu đầu ra của thuật toán (độ phức tạp về không gian). (2.2). Thời gian cần thiết để thực hiện thuật toán (độ phức tạp về thời gian). Như vậy, khi phân tích một thuật toán thực chất là ta đi đánh giá hai đặc trưng (2.1) và (2.2) để so sánh các thuật toán với nhau. 4.4.2. Độ phức tạp của thuật toán về thời gian Một thuật toán khi chạy thường phải thực hiện nhiều phép toán khác nhau như: phép toán số học, các phép toán so sánh, tính chỉ số, phép toán đổi chỗ, phép toán logic…Trong các phép toán đó có phép toán là cơ bản, có phép toán là không cơ bản. Thời giản thực hiện của một thuật toán tỷ lệ với số các phép toán cơ bản mà thuật toán phải thực hiện. Ví dụ 1: xét thuật toán tìm phần tử lớn nhất trong dãy hữu hạn Procedure Max(a1, a2, …, an : integer) Max := a1; For i := 2 to n If Max < ai then Max := ai {Max là phần tử lớn nhất} Phép toán so sánh là phép toán cơ sở của thuật toán. Mỗi phần tử của dãy sử dụng hai phép so sánh, một phép so sánh để kiểm tra xem đã đến cuối dãy hay chưa và một phép so sánh để kiểm tra xem có cập nhật lại giá trị Max hay không. Khi i = n+1 ta cần một phép so sánh để kiểm tra kết thúc vòng lặp nữa. Tổng số phép toán so sánh dùng trong thuật toán là: 2*(n-1) + 1 = 2n -1 Vậy độ phức tạp của thuật toán tìm phần tử lớn nhất của một dãy số có độ phức tạp là O(n). Ví dụ: Xét thuật toán nhân hai ma trận: A = (aik) với i,k Î [1,n], B = (bk,j) với k,j Î [1,n] A.B = C = (ci,j) với i,j Î [1,n] Để tính toán được một phần tử cij cần thực hiện (n-1) phép cộng và n phép nhân. Như vậy để tính n2 phần tử của ma trận C cần thực hiện n3 phép nhân và n2(n-1) = n3 - n2 phép cộng, dó đó có thể coi phép nhân là phép toán cơ bản của thuật toán nhân hai ma trận. Đoạn mã chương trình thực hiện phép nhân hai ma trận For i:=1 to n do For j:=1 to n do Begin C[i,j]:=0; For k:=1 to n do C[i,j]:= C[i,j] + A[i,k].B[k,j] End; Với các thuật toán sắp xếp, phép toán cơ bản là so sánh và đổi chỗ các phần tử, với thuật toán tìm kiếm thì phép toán cơ bản là phép so sánh phần tử với khoá. Với các thuật toán số học khác thì phép toán cơ bản là cộng, trừ, nhân, chia. 4.4.3. Kích thước của tập dữ liệu vào Ví dụ: với bài toán sắp xếp danh sách n phần tử thì kích thước của dữ liệu và là n, với bài toán nhân hai ma trận cấp n thì kích thước của dữ liệu vào là n, với các bài toán trên đồi thị G = thì kích thước của dữ liệu vào là |V| = n; |E| =m Đánh giá thời gian thực hiện của một thuật toán. Thời gian chạy của một thuật toán phụ thuộc vào các nhân tố sau: (1). Tập dữ liệu vào của chương trình (2). Chất lượng của đoạn mã chương trình được sinh bởi trình biên dịch được dùng để tạo đối tượng chương trình. (3). Chỉ thị lệnh và tốc dộ của các lệnh dùng để thực hiện chương trình (4). Độ phức tạp về mặt thời gian của thuật toán được dùng để viết chương trình. Vì thời gian chạy của một thuật toán phụ thuộc vào nhiều nhân tố, nên ta không thể biểu diễn chính xác thời gian chạy là bao nhiêu đơn vị thời gian chuẩn, chẳng hạn nó là bao nhiêu giây. Do thời gian thực hiện của một thuật toán phụ thuộc vào tập dữ liệu đầu vào cho nên ta có thể biểu diễn thời gian thực hiện thuật toán là một hàm của tập dữ liệu vào. Kích thước của tập dữ liệu vào là một tham số đặc trưng cho tập dữ liệu vào, nó ảnh hưởng trực tiếp đến thời gian thực hiện của một thuật toán. Ví dụ, đối với bài toán sắp xếp, kích thước của tập dữ liệu vào là số phần tử trong danh sách cần sắp xếp. Thông thường ký hiệu T(n) là thời gian thực hiện của một thuật toán, với n là kích thước của tập dữ liệu vào. T(n) không những phụ thuộc vào n mà còn phụ thuộc vào thứ tự bộ phận của các phần tử trong tập. Ví dụ, xét thuật toán tìm kiếm một phần tử x trong danh sách các phần tử cho trước. Thời gian thực hiện tốt nhất, xấu nhất và trung bình Cho một thuật toán A giải bài toán P. Tập dữ liệu đầu vào của thuật toán A là Dn, d Î Dn là một bộ dữ liệu đầu vào của A. Với d Î Dn, số phép toán cơ bản mà thuật toán A phải thực hiện với dữ liệu vào là d được ký hiệu là costA(d), khi đó: Thời gian thực hiện trong trường hợp tốt nhất của A là: MinA(n) = Min{ CostA(d) } với d Î Dn Thời gian thực hiện trong trường hợp xấu nhất của A là: MaxA(n) = Max{ CostA(d) } với d Î Dn Thời gian thực hiện trong trường hợp trung bình của A là: AvgA(n) = với p(d) là xác xuất để d là dữ liệu vào của A. Ví dụ: Xét bài toán tìm kiếm tuần tự một phần tử trong tập n phần tử nguyên. Phép toán cơ bản là phép so sánh. MinA(n) = 1 (chọn bộ dữ liệu vào có phần tử đầu tiên là phần tử cần tìm) MaxA(n) = n (chọn bộ dữ liệu vào có phần tử cuối cùng là phần tử cần tìm) Ký hiệu “Big O” O lớn và đánh giá độ phức tạp theo O lớn Như chúng ta đã biết, độ phức tạp theo thời gian của một thuật toán là một hàm của kích thước dữ liệu đầu vào, T(n) = f(n). Rõ ràng, khi kích thước dữ liệu vào tăng thì độ phức tạp của thuật toán cũng tăng theo. Tuy nhiên, để xác định độ phức tạp của thuật toán tăng nhanh như thế nào khi n tăng là một điều hết sức khó khăn, do đó trong thực tế người ta thường đánh giá f(n) thông qua các hàm chuẩn đã biết như: log2n, n, nlog2n, n2, n3, 2n. Tốc độ tăng của các hàm này được cho bởi bảng dưới đây F(n) n LogN N NlogN N2 N3 2N 5 3 5 15 25 125 32 10 4 10 40 100 103 103 100 7 100 700 104 106 1030 1000 10 1000 104 106 109 10300 Cách thức để so sánh độ phức tạp của hàm f(n) với các hàm chuẩn là sử dụng ký hiệu “Big O” O lớn được định nghĩa như sau: |f(x)| ≤ C|g(x)| với mọi x > k Khái niệm O lớn: cho f và g là hai hàm trên R hoặc tập con của R. Ta nói f(x) là O(g(x)) nếu tồn tại hai hằng số C và k sao cho: Ví dụ: chứng minh rằng f(n) = n2 + 2n + 1 là O(n2) với mọi x > 1. Giải: vì 0 ≤ n2 + 2n + 1 ≤ n2 + 2n2 + n2 = 4n2, chọn C = 4, k = 1 ta có F(n) là O(n2). Xác định độ phức tạp của thuật toán Việc xác định độ phức tạp tính toán của một thuật toán bất ký có thể rất phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một số quy tắc đơn giản. Các câu lệnh đơn giản (đọc, ghi, gán), độ phức tạp là O(1) (hằng số) Các thao tác đơn giản (cộng, trừ, nhân, chia….), độ phức tạp là O(1). Dãy các thao tác gồm các câu lệnh đơn, các thao tác đơn giản, độ phức tạp sử dụng quy tắc tổng. Các vòng lặp For, Do, While…, độ phức tạp sử dụng quy tắc nhân. Quy tắc tổng Nếu thuật toán thực hiện một chuỗi tuần tự các thao tác, độ phức tạp của thuật toán được tính bằng thao tác có độ phức tạp lớn nhất. Giả sử đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là T1(n) + T2(n) = O(max(f(n), g(n))) Quy tắc nhân Nếu thuật toán lặp lại một thao tác một số lần, độ phức tạp của thuật toán được tính bằng số lần lặp nhân với thời gian thực hiện thao tác đó. Giả sử đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n)) thì độ phức tạp của thuật toán sẽ là O(g(n).f(n)) Chương 2. Đệ quy và thuật toán đệ quy 1. Khái niệm về đệ quy Đệ quy (recursion) là một kĩ thuật định nghĩa một khái niệm trực tiếp hoặc gián tiếp theo chính nó. Ví dụ: trong một ngôi nhà có treo bức ảnh về chính ngôi nhà đó, trong bức ảnh lại có ngôi nhà, và trong đó lại có bức ảnh chính ngôi nhà,…. Trong toán học rất thường gặp định nghĩa đệ quy, ví dụ để tính giai thừa ( n!) ta định nghĩa đệ quy n!= n(n-1)! 2. Giải thuật đệ qui và thủ tục đệ qui Nếu lời giải P được thực hiện bằng lời giải P’ có dạng giống P thì ta nói đó là lời giải đệ quy. Thuật toán tương ứng - đệ quy. (i) Phần neo (anchor): Phần này được thực hiện cho trường hợp bài toán đơn giản. Ví dụ, ta biết chắc chắn 1!=1. (ii) Phần đệ quy: Ta xác định, những bài toán con và gọi các bài toán con đó. Như vậy, phần đệ quy thể hiện tính “quy nạp” của lời giải. Phần neo đảm bảo cho tính dừng của thuật toán. Tính giai thừa: N!= N(N-1)! Int fact ( int n) { If ( n <= 1 ) Return 1; /* cơ sở*/ Else Return n*fact (n-1) /* quy nạp*/ } Bài toán tháp Hà Nội -  Khi chuyển một đĩa phải đặt vào 1 trong 3 cọc. -  Mỗi lần chỉ chuyển đúng một đĩa trên cùng tại một cọc và đặt vào trên cùng ở cọc chuyển đến. -  Đĩa lớn hơn không được phép đặt lên đĩa nhỏ hơn. Ta sử dụng phương pháp quy nạp toán học để giải bài toán này. Nếu n=1 thì chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2.