›

Bài giảng Cấu trúc dữ liệu và giải thuật - Đệ quy - Đào Nam Anh

pdf 50 trang huongle 6881
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Đệ quy - Đào Nam Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_de_quy_dao_nam_anh.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Đệ quy - Đào Nam Anh

  1. DATA STRUCTURE AND ALGORITHM Recursion CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đệ qui Dr. Dao Nam Anh Data Structure and Algorithm 1
  2. Resource - Reference Slides adapted from Robert Sedgewick, and Kevin Wayne, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hồng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 2
  3. Khái niệm • Là một phương pháp lập trình cho phép một hàm cĩ thể gọi lại chính nĩ trực tiếp hoặc gián tiếp. Ví dụ: void Test() { Test(); } Reproductive Parts M. C. Escher, 1948 • Một chương trình đệ quy hoặc một định nghĩa đệ quy thì khơng thể gọi đến chính nĩ mãi mãi mà phải cĩ một điểm dừng đến một trường hợp đặc biệt nào đĩ, mà ta gọi là trường hợp suy biến (degenerate case). Data Structure and Algorithm 3
  4. Khái niệm Phương pháp thiết kế một giải thuật đệ quy: • Tham số hố bài tốn • Phân tích trường hợp chung : đưa bài tốn dưới dạng bài tốn cùng loại nhưng cĩ phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến • Tìm trường hợp suy biến Data Structure and Algorithm 4
  5. Khái niệm Chương trình đệ quy gồm hai phần chính: 1. Phần cơ sở: Điều kiện thốt khỏi đệ quy (điểm dừng) 2. Phần đệ quy: Trong phần thân chương trình cĩ lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu Data Structure and Algorithm 5
  6. Greatest Common Divisor Ước số chung nhỏ nhất • Gcd. Tìm số nguyên lớn nhất, chia hết bới hai số p và q. • Ví dụ. gcd(4032, 1272) = 24. 4032 = 26 32 71 1272 = 23 31 531 gcd = 23 31 = 24 Data Structure and Algorithm 6
  7. Greatest Common Divisor Ước số chung nhỏ nhất • Gcd. Tìm số nguyên lớn nhất, chia hết bới hai số p và q. p if q 0 base case gcd(p, q)  gcd(q, p % q) otherwise reduction step, converges to base case • Euclid's algorithm. [Euclid 300 BCE] gcd(4032, 1272)= gcd(1272, 216) = gcd(216, 192) = gcd(192, 24) 4032 = 3 1272 + 216 = gcd(24, 0) = 24. Data Structure and Algorithm 7
  8. Greatest Common Divisor Ước số chung nhỏ nhất p if q 0 base case gcd(p, q)  gcd(q, p % q) otherwise reduction step, converges to base case p q q p % q x x x x x x x x p = 8x gcd q = 3x gcd(p, q) = x Data Structure and Algorithm 8
  9. Greatest Common Divisor Ước số chung nhỏ nhất p if q 0 base case gcd(p, q)  gcd(q, p % q) otherwise reduction step, converges to base case public static int gcd(int p, int q) { if (q == 0) return p; base case else return gcd(q, p % q); reduction step } Data Structure and Algorithm 9
  10. Tính giai thừa đệ qui Data Structure and Algorithm 10
  11. Recursive Graphics Đệ qui Đồ họa Data Structure and Algorithm 11
  12. Data Structure and Algorithm 12
  13. Data Structure and Algorithm 13
  14. Htree – Cây đệ qui chữ H • H-tree bậc n. Và kích thước giảm nửa  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. size Bậc 1 Bậc 2 Bậc 3 Data Structure and Algorithm 14
  15. Htree – Cây đệ qui chữ H • H-tree bậc n. Và kích thước giảm nửa  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. size Bậc 1 Bậc 2 Bậc 3 Data Structure and Algorithm 15
  16. Htree – Cây đệ qui chữ H • H-tree bậc n. Và kích thước giảm nửa  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. tip size Bậc 1 Bậc 2 Bậc 3 Data Structure and Algorithm 16
  17. Htree in Java public class Htree { public static void draw(int n, double sz, double x, double y) { if (n == 0) return; double x0 = x - sz/2, x1 = x + sz/2; double y0 = y - sz/2, y1 = y + sz/2; StdDraw.line(x0, y, x1, y); draw the H, centered on (x, y) StdDraw.line(x0, y0, x0, y1); StdDraw.line(x1, y0, x1, y1); draw(n-1, sz/2, x0, y0); recursively draw 4 half-size Hs draw(n-1, sz/2, x0, y1); draw(n-1, sz/2, x1, y0); draw(n-1, sz/2, x1, y1); } public static void main(String[] args) { int n = Integer.parseInt(args[0]); draw(n, .5, .5, .5); } } Data Structure and Algorithm 17
  18. Animated H-tree Data Structure and Algorithm 18
  19. Animated H-tree Data Structure and Algorithm 19
  20. Animated H-tree Data Structure and Algorithm 20
  21. Animated H-tree Data Structure and Algorithm 21
  22. Animated H-tree Data Structure and Algorithm 22
  23. Animated H-tree 20% Data Structure and Algorithm 23
  24. Animated H-tree 20% 40% Data Structure and Algorithm 24
  25. Animated H-tree 20% 40% 60% 80% 100% Data Structure and Algorithm 25
  26. Data Structure and Algorithm 26
  27. Tháp Hà nội Data Structure and Algorithm 27
  28. Tháp Hà nội • Move all the discs from the leftmost peg to the rightmost one.  Only one disc may be moved at a time.  A disc can be placed either on empty peg or on top of a larger disc. start finish Edouard Lucas (1883) Data Structure and Algorithm 28
  29. Tháp Hà nội: Giải pháp đệ qui Chuyển n-1 đĩa nhỏ sang phải. Cịn lại đĩa lớn nhất cyclic wrap-around Chuyển n-1 đĩa nhỏ sang phải. Data Structure and Algorithm 29
  30. Tháp Hà nội: Giải pháp đệ qui public class TowersOfHanoi { public static void moves(int n, boolean left) { if (n == 0) return; moves(n-1, !left); if (left) System.out.println(n + " left"); else System.out.println(n + " right"); moves(n-1, !left); } public static void main(String[] args) { int N = Integer.parseInt(args[0]); moves(N, true); } } moves(n, true) : move discs 1 to n one pole to the left moves(n, false): move discs 1 to n one pole to the right Data Structuresmallest disc and Algorithm 30
  31. Tháp Hà nội: Giải pháp đệ qui % java TowersOfHanoi 3 % java TowersOfHanoi 4 1 left 1 right 2 right 2 left 1 left 1 right 3 left 3 right 1 left 1 right 2 right 2 left 1 left 1 right 4 left 1 right 2 left 1 right 3 right 1 right every other move is smallest disc 2 left 1 right subdivisions of ruler Data Structure and Algorithm 31
  32. Tháp Hà nội: Giải pháp đệ qui n, left 3, true Data Structure and Algorithm 32
  33. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 2, false 2, false 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 33
  34. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 2, false 2, false 2 1, true 1, true 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 34
  35. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 14 2, false 2, false 2 7 1, true 1, true 3 4 5 6 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 35
  36. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 14 15 28 2, false 2, false 2 7 8 13 16 21 22 27 1, true 1, true 1, true 1, true 3 4 5 6 9 10 11 12 17 18 19 20 23 24 25 26 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 36
  37. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 14 2, false 2, false 2 7 8 13 1, true 1, true 3 4 5 6 9 10 11 12 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 37
  38. Tháp Hà nội: Giải pháp đệ qui n, left 3, true 1 14 15 28 2, false 2, false 2 7 8 13 16 21 22 27 1, true 1, true 1, true 1, true 3 4 5 6 9 10 11 12 17 18 19 20 23 24 25 26 1 left 2 right 1 left 3 left 1 left 2 right 1 left Data Structure and Algorithm 38
  39. Tháp Hà nội: Giải pháp đệ qui • Remarkable properties of recursive solution.  Takes 2n - 1 moves to solve n disc problem.  Sequence of discs is same as subdivisions of ruler.  Every other move involves smallest disc. • Recursive algorithm may reveal fate of world.  Takes 585 billion years for n = 64 (at rate of 1 disc per second).  Reassuring fact: any solution takes at least this long! Data Structure and Algorithm 39
  40. Divide-and-Conquer Chia để trị • Chia để trị  Chia thành nhiều vấn đề nhỏ hơn với cùng một cấu trúc.  Giải quyết các vấn đề nhỏ bằng đệ qui cùng một giải pháp  Nhĩm các kết quả để cĩ giải pháp cho cả bài tốn Divide et impera. Veni, vidi, vici. - Julius Caesar • Ứng dụng thực tế.  Xử lý dữ liệu: FFT for signal processing.  Chương trình dịch: Parsers for programming languages.  Tính vi phân: Multigrid methods for solving PDEs.  Sắp xếp: Quicksort and mergesort for sorting.  Chía nhỏ vấn đề: Hilbert curve for domain decomposition. Data Structure and Algorithm 40
  41. Fibonacci Numbers Dãy số Fibonacci Dãy số Fibonacci bắt nguồn từ bài tốn cổ về việc sinh sản của các cặp thỏ. Bài tốn đặt ra như sau: • Các con thỏ khơng bao giờ chết • Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái) • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới Data Structure and Algorithm 41
  42. Fibonacci Numbers Dãy số Fibonacci • Giả sử từ đầu tháng 1 cĩ một cặp mới ra đời thì đến giữa tháng thứ n sẽ cĩ bao nhiêu cặp. • Ví dụ, n = 5, ta thấy:  Giữa tháng thứ 1: 1 cặp (ab) (cặp ban đầu)  Giữa tháng thứ 2: 1 cặp (ab) (cặp ban đầu vẫn chưa đẻ)  Giữa tháng thứ 3: 2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con)  Giữa tháng thứ 4: 3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ)  Giữa tháng thứ 5: 5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ) Data Structure and Algorithm 42
  43. Fibonacci Numbers Dãy số Fibonacci • Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n) • Nếu mỗi cặp thỏ ở tháng thứ n - 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là: F(n) = 2 * F(n - 1) Data Structure and Algorithm 43
  44. Fibonacci Numbers and Nature pinecone cauliflower Data Structure and Algorithm 44
  45. Fibonacci Numbers 0 if n 0  •F(Fibonaccin) 1 numbers.if n 0, 1 1, 1, 2, 3, 5, 8, 13, 21, 34,  F(n 1) F(n 2) otherwise L. P. Fibonacci Fibonacci rabbits (1170 - 1250) Data Structure and Algorithm 45
  46. Fibonacci Numbers 0 if n 0  •F(Fibonaccin) 1 numbers.if n 0, 1 1, 1, 2, 3, 5, 8, 13, 21, 34,  F(n 1) F(n 2) otherwise public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2); } Data Structure and Algorithm 46
  47. Đánh giá Đệ qui 1 • Q. Cách tính này cĩ hiệu quả khơng F(50)? public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2); } • A. Khơng hiệu quả. F(50) is called once. F(50) F(49) is called once. F(49) F(48) F(48) is called 2 times. F(47) is called 3 times. F(48) F(47) F(47) F(46) F(46) is called 5 times. F(45) is called 8 times. F(47) F(46) F(46) F(45) F(46) F(45) F(45) F(44) F(1) is called 12,586,269,025 times. recursion tree for nạve Fibonacci function F(50) Data Structure and Algorithm 47
  48. Đánh giá đệ qui 2 • Q. Cách sau cho F(50) cĩ hiệu quả khơng? public static long(int n) { long[] F = new long[n+1]; F[0] = 0; F[1] = 1; for (int i = 2; i <= n; i++) F[i] = F[i-1] + F[i-2]; return F[n]; } • Hiệu quả Data Structure and Algorithm 48
  49. Summary – Kết luận Thơng thường thay vì sử dụng lời giải đệ quy cho một bài tốn, ta cĩ thể thay thế bằng lời giải khơng đệ quy (khử đệ quy) bằng phương pháp lặp. Ưu điểm • Thuận lợi cho việc biểu diễn bài tốn • Gọn (đối với chương trình) Hạn chế • Cĩ khi khơng được tối ưu về thời gian • Cĩ thể gây tốn bộ nhớ Chính vì vậy, trong lập trình người ta cố tránh sử dụng thủ tục đệ quy nếu thấy khơng cần thiết Data Structure and Algorithm 49
  50. Discussion – Câu hỏi • structure-algorithm Data Structure and Algorithm 50