›
›

Cấu trúc dữ liệu và giải thuật - Chương 2: Hàm - Đệ quy (function - recursion)

pdf 65 trang vanle 2010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 2: Hàm - Đệ quy (function - recursion)", để 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:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_2_ham_de_quy_function.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 2: Hàm - Đệ quy (function - recursion)

  1. Chương 2: HÀM - ĐỆ QUY (Function - Recursion)
  2. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 2
  3. 1. Hàm  khả năng lập trình theo modul  chia nhỏ thao tác  tránh lặp lại một thao tác #include int add (int x, int y) { int z; z = x + y; return (z); } void main () { int i, j, k; i = 10; j = 20; k = add(i, j); cout<<"The value of k is"<<k; } 3 Chương 2: Hàm – Đệ quy
  4. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 4
  5. 2. Khái niệm ngăn xếp (stack)  Stack là phần bộ nhớ mà trong đó các giá trị của nó được lưu vào (Push) và lấy ra (Pop) theo kiểu “last in first out” 5 Chương 2: Hàm – Đệ quy
  6. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 6
  7. 3. Quá trình thực thi hàm  Khi hàm được gọi, vị trí lệnh hiện tại sẽ tạm thời bị dừng và điều khiển sẽ chạy đến hàm được gọi  Sau khi hàm được thực thi xong, điều khiển sẽ quay trở về vị trí đã bị dừng tạm thời để thi hành tiếp  Để biết được chính xác vị trí để quay trở về, máy tính sẽ lưu địa chỉ của lệnh kế tiếp lúc bị dừng vào stack → Như vậy: ◦ Trước khi thực thi hàm, máy tính sẽ lưu (Push) địa chỉ lệnh kế tiếp vào stack ◦ Khi hàm được thực thi xong, máy tính sẽ lấy (Pop) địa chỉ đó ra để thực hiện tiếp 7 Chương 2: Hàm – Đệ quy
  8. 3. Quá trình thực thi hàm 1 2 3 4 5 6 7 8 9 Kết quả??? 10 11 12 13 14 15 16 17 18 19 20 8 Chương 2: Hàm21 – Đệ quy
  9. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 9
  10. 4. Tham số hàm 1. Tham số hàm là tham trị (value): . giá trị tham số truyền trước và sau khi gọi hàm là như nhau 2. Tham số hàm là tham chiếu (reference): . giá trị tham số truyền sẽ được thay đổi sau khi gọi hàm 10 Chương 2: Hàm – Đệ quy
  11. 4. Tham số hàm void f1 (int k) void f1 (int &k) { { k = k + 10; k = k + 10; } } void main( ) void main( ) { { int i; int i; i = 0; i = 0; cout<<“Gia tri i truoc khi goi ham cout<<"Gia tri i truoc khi goi ham "<< i<<"\n"; "<< i<<"\n"; f1(i); f1(i); cout<<"Gia tri i sau khi goi ham cout<<"Gia tri i sau khi goi ham "<< i<<“\n"; "<< i<<“\n"; } } 11
  12. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 12
  13. 5. Biến toàn cục và cục bộ #include int i =0; // Global variable void f1() { int i=0; // local variable for f1 i = 50; Kết quả??? } void main() { int i ; // local variable for main f1() ; i =0; cout<<"value of i in main "<< i<<endl; f1(); cout<<"value of i after call "<< i<<endl; } 13 Chương 2: Hàm – Đệ quy
  14. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 14
  15. 6. Đệ quy (Recursion)  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(); }  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).  Ví dụ: Ta định nghĩa n! như sau: n * (n - 1)! n! 0! 1 15 Chương 2: Hàm – Đệ quy
  16. 6. Đệ quy (Recursion)  Phương pháp thiết kế một giải thuật đệ quy: ◦ Tham số hoá bài toán ◦ Phân tích trường hợp chung : đưa bài toán dưới dạng bài toá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 16 Chương 2: Hàm – Đệ quy
  17. 6. Đệ quy (Recursion)  Chương trình đệ quy gồm hai phần chính: 1. Phần cơ sở: Điều kiện thoá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 17 Chương 2: Hàm – Đệ quy
  18. 6. Đệ quy (Recursion)  Ví dụ 1 : Lập hàm tính n! bằng đệ quy n * (n - 1)! n! 0! 1 int GT(int n) { if (n==0) // điểm dừng return 1; else return n*GT(n-1); } 18 Chương 2: Hàm – Đệ quy
  19. 6. Đệ quy (Recursion) Minh họa Gọi hàm answer <- GT(5) CT chính: Chưa xong: answer <- GT(5) 19 Chương 2: Hàm – Đệ quy
  20. 6. Đệ quy (Recursion) Minh họa GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 20 Chương 2: Hàm – Đệ quy
  21. 6. Đệ quy (Recursion) Minh họa GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 21 Chương 2: Hàm – Đệ quy
  22. 6. Đệ quy (Recursion) Minh họa GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 22 Chương 2: Hàm – Đệ quy
  23. 6. Đệ quy (Recursion) Minh họa GT. 4th: N=2, Chưa xong: 2*GT(1) GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 23 Chương 2: Hàm – Đệ quy
  24. 6. Đệ quy (Recursion) Minh họa GT. 5th: N=1, Chưa xong: 1*GT(0) GT. 4th: N=2, Chưa xong: 2*GT(1) GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT (5) 24 Chương 2: Hàm – Đệ quy
  25. 6. Đệ quy (Recursion) Minh họa GT. 6th: N=0, xong: returns 1 GT. 5th: N=1, Chưa xong: 1*GT(0) GT. 4th: N=2, Chưa xong: 2*GT(1) GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 25 Chương 2: Hàm – Đệ quy
  26. 6. Đệ quy (Recursion) Minh họa GT. 5th: N=1, xong: returns 1*1 GT. 4th: N=2, Chưa xong: 2*GT(1) GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 26 Chương 2: Hàm – Đệ quy
  27. 6. Đệ quy (Recursion) Minh họa GT. 4th: N=2, xong: returns 2*1 GT. 3rd: N=3, Chưa xong: 3*GT(2) GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 27 Chương 2: Hàm – Đệ quy
  28. 6. Đệ quy (Recursion) Minh họa GT. 3rd: N=3, xong: returns 3*2 GT. 2nd: N=4, Chưa xong: 4*GT(3) GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 28 Chương 2: Hàm – Đệ quy
  29. 6. Đệ quy (Recursion) Minh họa GT. 2nd: N=4, xong: returns 4*6 GT. 1st: N=5, Chưa xong: 5*GT(4) CT chính: Chưa xong: answer <- GT(5) 29 Chương 2: Hàm – Đệ quy
  30. 6. Đệ quy (Recursion) Minh họa GT. 1st: N=5, xong: returns 5*24 CT chính: Chưa xong: answer <- GT(5) 30 Chương 2: Hàm – Đệ quy
  31. 6. Đệ quy (Recursion) Minh họa CT chính: xong: answer <- 120 31 Chương 2: Hàm – Đệ quy
  32. 6. Đệ quy (Recursion)  Ví dụ 2: Tính bằng đệ quy Dãy số Fibonaci: F1 = F2 = 1; Fn = Fn-1 + Fn-2. (n 3) int Fibo(int n) { if (n 2) // điểm dừng return 1; else return Fibo(n-1)+Fibo(n-2); } 32 Chương 2: Hàm – Đệ quy
  33. 6. Đệ quy (Recursion)  Nhận xét: ◦ Thông thường thay vì sử dụng lời giải đệ quy cho một bài toá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. ◦ Việc sử dụng giải thuật đệ quy có: Ưu điểm Khuyết điểm Thuận lợi cho việc biểu diễn Có khi không được tối ưu về bài toán thời gian Gọn (đối với chương trình) 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. 33 Chương 3: Hàm – Đệ quy
  34. 6. Đệ quy (Recursion)  Tính giai thừa dùng vòng lặp: int GT(int n) { int s = 1; for(int i= 2; i<= n; i++) s = s* i; return s; } 34 Chương 2: Hàm – Đệ quy
  35. NỘI DUNG 1. Hàm (function) 2. Khái niệm ngăn xếp (stack) 3. Quá trình thực thi hàm 4. Tham số hàm 5. Biến toàn cục (global) và cục bộ (local) 6. Đệ quy (recursion) 7. Các loại đệ quy (types of recursion) 35
  36. 7. Các loại đệ quy  Đệ quy tuyến tính (Linear Recursion)  Đệ quy đuôi (Tail Recursion)  Đệ quy nhị phân (Binary Recursion)  Đệ quy mũ (Exponential Recursion)  Đệ quy lồng (Nested Recursion)  Đệ quy hỗ tương (Mutual Recursion) 36 Chương 2: Hàm – Đệ quy
  37. 7. Các loại đệ quy  Đệ quy tuyến tính (Linear Recursion) ◦ mỗi lần hàm thực thi chỉ gọi đệ quy 1 lần (only makes a single call to itself each time the function runs) Ví dụ: tính giai thừa bằng đệ quy: int GT(int n) { if (n==0) // điểm dừng return 1; else return n*GT(n-1); } 37 Chương 2: Hàm – Đệ quy
  38. 7. Các loại đệ quy  Đệ quy đuôi (Tail Recursion) ◦ là một dạng đệ quy tuyến tính ◦ lệnh cuối cùng của hàm là một lời gọi đệ quy (the last operation of the function is a recursive call) ◦ dễ chuyển thành vòng lặp Ví dụ: tìm Ước số chung lớn nhất của m, n bằng đệ quy (Greatest Common Denominator) int gcd(int m, int n) { int r; if (m < n) return gcd(n,m); r = m%n; if (r == 0) return n; else return gcd(n,r); } 38 Chương 2: Hàm – Đệ quy
  39. 7. Các loại đệ quy  Đệ quy nhị phân (Binary Recursion) ◦ mỗi lần hàm thực thi có thể gọi đệ quy 2 lần (A recursive function which calls itself twice during the course of its execution) Ví dụ: tính số các tổ hợp chập k của n phần tử (C(n,k)) bằng đệ quy: 1 nếu k = 0 or k=n C(n, k) = C(n-1, k) + C(n-1, k-1) nếu 0 < k < n int choose(int n, int k) { if (k == 0 || k == n) return 1; else return (choose(n-1, k) + choose(n-1, k-1)); } 39 Chương 2: Hàm – Đệ quy
  40. 7. Các loại đệ quy  Đệ quy mũ (Exponential Recursion) ◦ là loại đệ quy mà số lời gọi đệ quy được tính bằng hàm mũ (if you were to draw out a representation of all the function calls, would have an exponential number of calls in relation to the size of the data set) Ví dụ: viết hàm xuất ra các hoán vị của các số trong mảng void print_permutations (int arr[], int n, int i) { void print_array (int arr[], int n) int j, swap; { print_array (arr, n); int i; for (j=i+1; j<n; j++) for(i=0; i<n; i++) cout<<arr[i]; { cout<<"\n"; swap = arr[i]; arr[i] = arr[j]; arr[j] = swap; } print_permutations(arr, n, i+1); swap = arr[i]; arr[i] = arr[j]; arr[j] = swap; } } 40 Chương 2: Hàm – Đệ quy
  41. 7. Các loại đệ quy  Đệ quy lồng (Nested Recursion) ◦ trong đệ quy lồng, tham số trong lời gọi đệ quy là một lời gọi đệ quy (In nested recursion, one of the arguments to the recursive function is the recursive function itself) ◦ Đệ quy lồng phát triển rất nhanh Ví dụ: viết hàm Ackermann's: int ackerman (int m, int n) { if (m == 0) return (n+1); else if (n == 0) return ackerman(m-1,1); else return ackerman(m-1, ackerman(m,n-1)); } 41 Chương 2: Hàm – Đệ quy
  42. 7. Các loại đệ quy  Đệ quy lồng (Nested Recursion) 42 Chương 2: Hàm – Đệ quy
  43. 7. Các loại đệ quy  Đệ quy hỗ tương (Mutual Recursion) ◦ hàm đệ quy không cần thiết phải gọi chính nó (A recursive function doesn't necessarily need to call itself) ◦ một số hàm đệ quy gọi lẫn nhau ◦ ví dụ: hàm A gọi hàm B, hàm B gọi hàm C, hàm C lại gọi hàm A Ví dụ: viết hàm kiểm tra chẵn, lẻ bằng đệ quy: int is_even(unsigned int n) { if (n==0) return 1; else return (is_odd(n-1)); } int is_odd(unsigned int n) { return (!is_even(n)); } 43 Chương 2: Hàm – Đệ quy
  44. Giải một số bài tập đệ quy  Ví dụ 1: Bài toán tháp Hà Nội ◦ Chuyển một chồng đĩa gồm n đĩa với kích thước khác nhau từ cột A sang cột C theo cách: + Mỗi lần chỉ chuyển 1 đĩa + Không có trường hợp đĩa lớn được đặt trên đĩa nhỏ + Khi chuyển có thể dùng cột trung gian B 44 Chương 2: Hàm – Đệ quy
  45. Giải một số bài tập đệ quy  Ví dụ 1: Bài toán tháp Hà Nội Tham số hoá bài toán: HaNoi (n, A, B, C) Trong đó: n: Số đĩa. A: Cọc nguồn cần chuyển đĩa đi B: Cọc trung gian C: Cọc đích để chuyển đĩa đến (A, B, C có kiểu ký tự) 45 Chương 2: Hàm – Đệ quy
  46. Giải một số bài tập đệ quy Giải thuật đệ quy bài toán Tháp Hà Nội:  Trường hợp suy biến (điểm dừng): Nếu n = 1 thì chuyển đĩa từ A qua C  Trường hợp chung (n 2): Thử với n=2: + Chuyển đĩa thứ nhất từ A sang B + Chuyển đĩa thứ hai từ A sang C + Chuyển đĩa thứ nhất từ B sang C Tổng quát: + Chuyển (n -1) đĩa từ A sang B (C làm trung gian) + Chuyển 1 đĩa từ A sang C (B làm trung gian) + Chuyển (n -1) đĩa từ B sang C (A làm trung gian) 46 Chương 2: Hàm – Đệ quy
  47. Giải một số bài tập đệ quy 1 đĩa A B C Chương 2: Hàm – Đệ quy
  48. Giải một số bài tập đệ quy 1 đĩa A B C Chương 2: Hàm – Đệ quy
  49. Giải một số bài tập đệ quy 2 đĩa A B C Chương 2: Hàm – Đệ quy
  50. Giải một số bài tập đệ quy 2 đĩa A B C Chương 2: Hàm – Đệ quy
  51. Giải một số bài tập đệ quy 2 đĩa A B C Chương 2: Hàm – Đệ quy
  52. Giải một số bài tập đệ quy 2 đĩa A B C Chương 2: Hàm – Đệ quy
  53. Giải một số bài tập đệ quy N đĩa A B C Chương 2: Hàm – Đệ quy
  54. Giải một số bài tập đệ quy N đĩa A B C Chương 2: Hàm – Đệ quy
  55. Giải một số bài tập đệ quy N đĩa A B C Chương 2: Hàm – Đệ quy
  56. Giải một số bài tập đệ quy Giải thuật đệ quy bài toán Tháp Hà Nội: void HaNoi (int n, char A, char B, char C){ if (n==1) cout<<A<<“ ”<< C; else{ HaNoi(n -1, A, C, B); HaNoi(1, A, B, C); HaNoi(n -1, B, A, C); } } 56 Chương 2: Hàm – Đệ quy
  57. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép in chuỗi đảo ngược - Trường hợp chung: + In ký tự cuối của chuỗi X + Lấy phần chuỗi còn lại - Trường hợp suy biến: Nếu chuỗi rỗng thì không làm gì void InNguoc(char *X) { static int len=strlen(X); if (len>0) { cout<<X[len-1]; len ; InNguoc(X); } } 57 Chương 2: Hàm – Đệ quy
  58. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép xuất biểu diễn nhị phân của 1 số nguyên n, ví dụ: n=13 1101 Xuất dạng nhị phân của n: Nếu (n/2>0) Xuất dạng nhị phân của n/2; Xuất (n%2); void XuatNhiPhan(int n) { if (n/2>0) XuatNhiPhan (n/2); cout<<n%2; } 58 Chương 2: Hàm – Đệ quy
  59. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép nhập số giây và chuyển thành giờ, phút, giây. Ví dụ: nhập 3665 -> 1 giờ 1 phút 5 giây void DoiGio(int n, int &g, int &p, int &gi) { if (n 0) { g=n/3600; return DoiGio(n%3600, g, p, gi); } else{ p=n/60; return DoiGio(n%60, g, p, gi); } } 59 Chương 2: Hàm – Đệ quy
  60. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép kiểm tra xem một số có phải số nguyên tố không int isPrime (int N) { if (N==1) return 1; isPrime(N) = prime(N, N-1) int static M=N-1; prime(N, 1) = true if (M==1) return 1; prime(N, D) = if D divides N, false else if (N%M==0) return 0; else prime(N, D-1) else { M ; isPrime (N); } } 60 Chương 2: Hàm – Đệ quy
  61. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép tính tổng các chữ số của một số nguyên n, ví dụ n=1980 =>Sum=1+9+8+0=18 Tổng các chữ số của n: + Nếu (n<10) thì Tổng bằng n; + Nếu (n<10) thì Tổng bằng n%10 + Tổng các chữ số của n/10 int tong(int n) { if (n<10) return n; else return n%10+tong(n/10); } 61 Chương 2: Hàm – Đệ quy
  62. Giải một số bài tập đệ quy  Bài tập: Viết hàm đệ quy cho phép xuất ngược một số nguyên n, ví dụ n=1980 xuất 0891 Xuất ngược n: + Nếu n =10 thì Xuất n%10 và Xuất ngược n/10 void XuatSoNguoc(int n) { if (n<10) cout<<n; else { cout<<n%10; XuatSoNguoc(n/10); } } 62 Chương 2: Hàm – Đệ quy
  63. Giải một số bài tập đệ quy  Bài tập: In hình tam giác sau bằng cách đệ quy void InSao(int n) { if (n>1) InSao(n-1); for (int i=0; i<n; i++) cout<<"*"; cout<<endl; } 63 Chương 2: Hàm – Đệ quy
  64. Giải một số bài tập đệ quy  Bài tập: Cho mảng a có n phần tử, tính tổng các phần tử trong mảng bằng đệ quy Điều kiện biên: Mảng 0 phần tử thì tổng bằng 0 Giải thuật chung: Sum (a,n) = 0 , n=0 a[n-1] + Sum(a, n-1), n>0 64 Chương 2: Hàm – Đệ quy
  65. Giải một số bài tập đệ quy  Bài tập: Cho mảng a có n phần tử, tìm giá trị lớn nhất trong mảng bằng đệ quy Điều kiện biên: Mảng 1 phần tử thì trị lớn nhất là a[0] Giải thuật chung: Max (a,n) = a[0] , n=1 a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1), n>1 65 Chương 2: Hàm – Đệ quy