Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Bích Diệp
lượt xem 3
download
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật đệ qui" giới thiệu tới người học các kiến thức: Các khái niệm cơ bản về giải thuật đệ qui, các ví dụ bài toán giải thuật đệ qui, phân tích giải thuật đệ qui. Mời các bạn cùng tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Đỗ Bích Diệp
- Cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu và Giải thuật Chương II Giải thuật đệ qui Giải thuật đệ qui Nội dung Các khái niệm cơ bản Một số ví dụ Phân tích giải thuật đệ qui Đố Bích Diệp- Khoa CNTT-ĐHBKHN 1
- Cấu trúc dữ liệu và giải thuật Một số đối tượng đệ qui Một số đối tượng đệ qui z Hàm đệ qui: – Là hàm được xác định phụ thuộc vào một biến nguyên không âm n theo sơ đồ: z Bước cơ sở : xác định giá trị hàm tại một giá trị n giá trị nhỏ nhất có thể của biến z Bước đệ qui: Cho giá trị f(k) , đưa ra qui tắc để tính f(k+1) Đố Bích Diệp- Khoa CNTT-ĐHBKHN 2
- Cấu trúc dữ liệu và giải thuật Một số đối tượng đệ qui z Tập hợp đệ qui – Là tập được xác định như sau z Bước cơ sở: Định nghĩa tập cơ sở z Bước đệ qui: Xác định qui tắc để sản sinh tập mới từ tập đã có Một số đối tượng đệ qui z Định nghĩa đệ qui của xâu ký tự – A = bảng chữ cái, tập các xâu S trên bảng chữ cái A được xác định z Xâu rỗng là xâu trong S z Nếu w thuộc S và x là một ký tự trong A thì wx là xâu trong S Đố Bích Diệp- Khoa CNTT-ĐHBKHN 3
- Cấu trúc dữ liệu và giải thuật Một số đối tượng đệ qui z Cây – Định nghĩa đệ qui của cây z Một nút tạo thành 1 cây z Nếu có n cây T1, T2, …, Tn với nút gốc là r1, r2, … , rn; r là một nút có quan hệ cha-con r1, r2, … , rn thì tồn tại một cây mới T nhận r làm gốc Giải thuật đệ qui – Định nghĩa: Giải thuật đệ qui là giải thuật được định nghĩa sử dụng chính giải thuật có dạng giống nó – Cấu trúc của một thuật toán đệ qui bao gồm 2 bước z Bước cơ sở – Với những giá trị đầu vào đủ nhỏ, bài toán có thể giải quyết trực tiếp z Bước đệ qui – Lời gọi đến giải thuật đang định nghĩa – Lời gọi đệ qui phải được định nghĩa để nó tiến gần hơn đến bước cơ sở Đố Bích Diệp- Khoa CNTT-ĐHBKHN 4
- Cấu trúc dữ liệu và giải thuật Các dạng giải thuật đệ qui – Đệ qui trực tiếp : AÆ A – Đệ qui gián tiếp: AÆB Æ…ÆA – Đệ qui đuôi z Lời gọi đệ qui luôn luôn nằm cuối cùng trong giải thuật Giải thuật đệ qui – Ví dụ: Hàm tính n! ⎧ 1 if n = 0 Fact ( n) = ⎨ ⎩n * Fact ( n − 1) if n > 0 Function recursiveFactorial(n) Begin {Tính giá trị n! } Trường hợp cơ sở 1. if n = 0 then return 1 else return n*FACT(n-1); 2. End. Lời gọi đệ qui Tổ hợp kết quả Đố Bích Diệp- Khoa CNTT-ĐHBKHN 5
- Cấu trúc dữ liệu và giải thuật Giải thuật đệ qui – Hình dung việc thực hiện giải thuật tính n! return 4 * 6 = 24 final answer call recursiveFactorial (4 ) call return 3 *2 = 6 recursiveFactorial (3 ) call return 2 *1 = 2 recursiveFactorial (2 ) call return 1 *1 = 1 recursiveFactorial (1 ) call return 1 recursiveFactorial (0 ) Giải thuật đệ qui –Dãy Fibonacci ⎧0 if n = 0 ⎪ Fibonacci ( n ) = ⎨1 if n = 1 ⎪ Fibonacci ( n − 1) + Fibonacci ( n − 2) otherwise ⎩ Function Fibonacci(n) Begin {Tính giá trị n! } 1. if n
- Cấu trúc dữ liệu và giải thuật Giải thuật đệ qui – Thực hiện tính Fibonacci(6) Fibonacci(6) Fibonacci(5) Fionacci(4) Fibonacci(4) Fibonacci(3) Fibonacci(3) Fibonacci(2) Fibonacci(3) Fibonacci(2) Fibonacci(2) Fibonacci(2) Fibonacci(1) Fibonacci(2) Fibonacci(1) Fibonacci(1) Giải thuật đệ qui – Bài toán Tháp Hà nội z Có 3 cọc A, B, C và n đĩa có kích thước khác nhau z Ban đầu, các đĩa được xếp có thứ tự đĩa to ở trên, đĩa nhỏ ở dưới tại cọc A z Mục tiêu là chuyển n đĩa này sang cọc C với điều kiện mỗi lần được chuyển 1 đĩa, không được đặt đĩa to ở trên đĩa nhỏ B n đĩa A C Đố Bích Diệp- Khoa CNTT-ĐHBKHN 7
- Cấu trúc dữ liệu và giải thuật Giải thuật đệ qui z Bước cơ sở : n
- Cấu trúc dữ liệu và giải thuật Giải thuật đệ qui B B A C A C B A C B A C Giải thuật đệ qui B TOWER(n-1, A, C, B) B A C A C B Move(A, C) TOWER(n, A, B, C) A C B TOWER(n-1, B, A, C) A C Đố Bích Diệp- Khoa CNTT-ĐHBKHN 9
- Cấu trúc dữ liệu và giải thuật Giải thuật đệ qui Procedure TOWER( n, A, B, C) Begin {n là số đĩa ban đầu trên cọc A, cọc đầu tiên được chỉ định là cọc chứa các đĩa cần chuyển, cọc thứ 2 là cọc trung chuyển, cọc thứ 3 là cọc cần chuyển đĩa đến } if n < 1 then return else begin call TOWER(n-1, A, C, B) call MOVE(A,C) call TOWER( n-1, B, A, C) end End Phân tích thuật toán đệ qui – Hàm thời gian thực hiện giải thuật T(n) là hàm đệ qui với tham số n Đố Bích Diệp- Khoa CNTT-ĐHBKHN 10
- Cấu trúc dữ liệu và giải thuật Phân tích thuật toán đệ qui – Ví dụ 1 Procedure f(n) z T(0) = 1 {n là số nguyên không âm} z T(n) = 2 + T(n-1) Begin if (n > 0) then begin writeln(n) ; Call f(n-1); end End Phân tích giải thuật đệ qui – Ví dụ 2 z Trường hợp cơ sở Function g( n) Begin T(1) = 2 if (n =1) then z Đệ qui return 2; T(n) = c + 2* T(n/2) else return 3 * g(n / 2) + g( n / 2) + 5; End. Đố Bích Diệp- Khoa CNTT-ĐHBKHN 11
- Cấu trúc dữ liệu và giải thuật Phân tích thời gian thực hiện giải thuật – Cách thức giải công thức đệ qui của thời gian thực hiện giải thuật đệ qui z Phương pháp lặp Phân tích giải thuật đệ qui z Phương pháp lặp – Giải công thức đệ qui của thời gian thành một tổng các toán hạng cụ thể z Lặp lại việc thay thế hàm cho đến khi bắt gặp trường hợp cơ sở z Tính tổng Đố Bích Diệp- Khoa CNTT-ĐHBKHN 12
- Cấu trúc dữ liệu và giải thuật Phân tích giải thuật đệ qui – Ví dụ: T(n) = c + T(n/2) T(n) = c + T(n/2) = c + c + T(n/4) = c + c + c + T(n/8) Giả sử n = 2k T(n) = c + c + … + c + T(1) = clogn + T(1) Vậy ta có T(n) = O(logn) Phân tích giải thuật đệ qui – Ví dụ: T(n) = n + 2T(n/2) T(n) = n + 2T(n/2) = n + 2(n/2 + 2T(n/4)) = n + n + 4T(n/4) = n + n + 4(n/4 + 2T(n/8)) = n + n + n + 8T(n/8) … = in + 2iT(n/2i) Giả sử n = 2k thì ta sẽ rút gọn được T(n) = kn + 2kT(1) = nlogn + nT(1) Vậy T(n)= O(nlogn) Đố Bích Diệp- Khoa CNTT-ĐHBKHN 13
- Cấu trúc dữ liệu và giải thuật Phân tích giải thuật đệ qui z Phân tích giải thuật tính giai thừa T(0) = c Function recursiveFactorial(n) T(n) = b + T(n - 1) Begin = b + b + T(n - 2) {Tính giá trị n! } = b +b +b + T(n - 3) 1. if n = 0 then return 1 … else return n*FACT(n-1); = kb + T(n - k) 2. End. Khi k = n, ta có: T(n) = nb + T(n - n) = bn + T(0) = bn + c. Vậy T(n) = O(n). Phân tích giải thuật đệ qui z Phân tích giải thuật Tháp Hà Nội T(1) = a Procedure TOWER( n, A, B, C) T(n) = b+ 2T(n-1) Begin if n < 1 then return else begin call TOWER(n-1, A, C, B); call MOVE(A,C); call TOWER( n-1, B, A, C); end End Đố Bích Diệp- Khoa CNTT-ĐHBKHN 14
- Cấu trúc dữ liệu và giải thuật Phân tích giải thuật đệ qui T(n) = 2T(n – 1) + b = 2[2T(n – 2) + b] + b = 22 T(n – 2) + 2b + b = 2 [2T(n – 3) + b] + 2b + b 2 = 23 T(n – 3) + 22b + 2b + b = 23 [2T(n – 4) + b] + 22b + 2b + b = 24 T(n – 4) + 23 b + 22b + 21b + 20b = …… = 2k T(n – k) + b[2k- 1 + 2k– 2 + . . . 21 + 20] Khi n = k-1 ta có Khử đệ qui – Một hàm đệ qui có thể được giải quyết tương đương bằng việc sử dụng vòng lặp và stack Đố Bích Diệp- Khoa CNTT-ĐHBKHN 15
- Cấu trúc dữ liệu và giải thuật Khử đệ qui Algorithm P (val n ) 1 if (n = 0) 1 print ("Stop") 2 else 1 Q(n) 2 P(n - 1) 3 R(n) End P Khử đệ qui Algorithm P (n) Algorithm P (n) 1 if (n = 0) 1 createStack (s) 1 print ("Stop") 2 loop (n > 0) 2 else 1 Q(n) 1 Q(n) 2 push(s, n) 2 P(n - 1) 3 n=n-1 3 R(n) 3 print ("Stop") End P 4 loop (not emptyStack (s)) 1 popStack(s, n) 2 R(n) End P Đố Bích Diệp- Khoa CNTT-ĐHBKHN 16
- Cấu trúc dữ liệu và giải thuật Khử đệ qui Algorithm P (n) 1 if (n = 0) 1 print("Stop") 2 else 1 Q(n) 2 P(n - 1) End P Khử đệ qui Algorithm P (n) Algorithm P (n) 1 if (n = 0) 1 print("Stop") 1 loop (n > 0) 2 else 1 Q(n) 1 Q(n) 2 n=n-1 2 P(n - 1) 2 print("Stop") End P End P Đố Bích Diệp- Khoa CNTT-ĐHBKHN 17
- Cấu trúc dữ liệu và giải thuật Đệ qui có nhớ z Một kỹ thuật sử dụng khi trong các bài toán đệ qui có việc lặp đi lặp lại lời gọi một bài toán con nào đó z Làm tăng tính hiệu quả của giải thuật đệ qui Fibonacci(6) Fibonacci(5) Fionacci(4) Fibonacci(4) Fibonacci(3) Fibonacci(3) Fibonacci(2) Fibonacci(3) Fibonacci(2) Fibonacci(2) Fibonacci(2) Fibonacci(1) Fibonacci(2) Fibonacci(1) Fibonacci(1) Đệ qui có nhớ – Ý tưởng khắc phục: z Ghi lại lời giải của các bài toán con sử dụng một biến trong giải thuật z Ví dụ: Bài toán tính hệ số nhị thức C (n,0) = 1 (n ≥ 0) C (n, n) = 1 (n ≥ 0) C (n, k ) = C (n − 1, k − 1) + C (n − 1, k ) 0 < k < n Đố Bích Diệp- Khoa CNTT-ĐHBKHN 18
- Cấu trúc dữ liệu và giải thuật Đệ qui có nhớ z Hàm đệ qui của bài toán Function C(n,k) Begin if ( k == 0) || (k ==n) then return 1; else return C(n-1,k-1) + C( n-1,k); End z Hàm đệ qui có nhớ Function C(n,k) Begin if D[n,k] > 0 then return D[n,k]; else D[n,k] = C(n-1,k-1) + C( n-1,k); return D[n,k]; End Đố Bích Diệp- Khoa CNTT-ĐHBKHN 19
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 59 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 160 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 52 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn