›
›

Kỹ thuật lập trình - Kỹ thuật lập trình đệ quy

ppt 44 trang vanle 3570
Download
Bạn đang xem 20 trang mẫu của tài liệu "Kỹ thuật lập trình - Kỹ thuật lập trình đệ quy", để 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:

  • pptky_thuat_lap_trinh_ky_thuat_lap_trinh_de_quy.ppt

Nội dung text: Kỹ thuật lập trình - Kỹ thuật lập trình đệ quy

  1. Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Khoa học Tự nhiên KỸ THUẬT LẬP TRÌNH ThS. Đặng Bình Phương dbphuong@fit.hcmus.edu.vn KỸ THUẬT LẬP TRÌNH ĐỆ QUY 1
  2. & VC BB Nội dung 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Phân tích giải thuật & khử đệ quy 4 Các bài toán kinh điển 2 Kỹ thuật lập trình đệ quy
  3. & VC BB Bài toán vCho S(n) = 1 + 2 + 3 + + n =>S(10)? S(11)? S(10) = 1 + 2 + + 10 = 55 S(11) = 1 + 2 + + 10 + 11 = 66 = S(10) + 11 = 55 + 11 = 66 3 Kỹ thuật lập trình đệ quy
  4. & VC BB 2 bước giải bài toán Bước 2. Thế ngược § Xác định kết quả bài toán đồng dạng từ đơn giản đến S(n) = S(n-1) + n phức tạp Kết quả cuối cùng. S(n-1) = S(n-2) + n-1 = + Bước 1. Phân tích S(1) = S(0) + 1 § Phân tích thành bài toán đồng dạng nhưng đơn giản hơn. § Dừng lại ở bài toán đồng S(0) = 0 dạng đơn giản nhất có thể xác định ngay kết quả. 4 Kỹ thuật lập trình đệ quy
  5. & VC BB Khái niệm đệ quy vKhái niệm Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. vVí dụ Tổng S(n) được tính thông qua tổng S(n-1). v2 điều kiện quan trọng Ø Tồn tại bước đệ quy. Ø Điều kiện dừng. 5 Kỹ thuật lập trình đệ quy
  6. & VC BB Hàm đệ quy trong NNLT C vKhái niệm § Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp. Hàm( ) Hàm1( ) Hàm2( ) { { { Lời gọi Hàm Lời gọi Hàm2 Lời gọi Hàmx } } } ĐQ trực tiếp ĐQ gián tiếp 6 Kỹ thuật lập trình đệ quy
  7. & VC BB Cấu trúc hàm đệ quy (TS) { Phần dừng if ( )(Base step) { • Phần khởi tính toán hoặc điểm kết thúc của thuật toán • Không chứa phần đang được return ;định nghĩa } Phần đệ quy (Recursion step) Lời gọi Hàm• Có sử dụng thuật toán đang được định nghĩa. } 7 Kỹ thuật lập trình đệ quy
  8. & VC BB Phân loại Trong thân hàm có duy nhất một TUYẾN TÍNH 1 lời gọi hàm gọi lại chính nó một cách tường minh. Trong thân hàm có hai lời gọi NHỊ PHÂN 2 hàm gọi lại chính nó một cách tường minh. HỖ TƯƠNG Trong thân hàm này có lời gọi hàm tới PHI TUYẾN 3 hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này. 4 Trong thân hàm có lời gọi hàm lại chính nó được đặt bên trong thân vòng lặp. 8 Kỹ thuật lập trình đệ quy
  9. & VC BB Đệ quy tuyến tính Ví dụ Tính S(n) = 1 + 2 + + n S(n) = S(n – 1) + n ĐK dừng: S(0) = 0 Cấu trúc chương trình .: Chương trình :. long Tong(int n) { TênHàm( ) { if (n == 0) if ( ) { return 0; return Tong(n–1) + n; return ; } } TênHàm( ); } 9 Kỹ thuật lập trình đệ quy
  10. & VC BB Đệ quy nhị phân Ví dụ Tính số hạng thứ n của dãy Fibonacy: f(0) = f(1) = 1 f(n) = f(n – 1) + f(n – 2) n > 1 Cấu trúc chương trình ĐK dừng: f(0) = 1 và f(1) = 1 TênHàm( ) { .: Chương trình :. if ( ) { long Fibo(int n) { return ; if (n == 0 || n == 1) } return 1; TênHàm( ); return Fibo(n–1)+Fibo(n–2); } TênHàm( ); } 10 Kỹ thuật lập trình đệ quy
  11. & VC BB Đệ quy hỗ tương Ví dụ Tính số hạng thứ n của dãy: x(0) = 1, y(0) = 0 x(n) = x(n – 1) + y(n – 1) y(n) = 3*x(n – 1) + 2*y(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1, y(0) = 0 .: Chương trình :. TênHàm1( ) { long yn(int n); if ( ) long xn(int n) { return ; if (n == 0) return 1; TênHàm2( ); return xn(n-1)+yn(n-1); } } TênHàm2( ) { long yn(int n) { if ( ) if (n == 0) return 0; return ; return 3*xn(n-1)+2*yn(n-1); TênHàm1( ); } } 11 Kỹ thuật lập trình đệ quy
  12. & VC BB Đệ quy phi tuyến Ví dụ Tính số hạng thứ n của dãy: x(0) = 1 x(n) = n2x(0) + (n-1)2x(1) + + 22x(n – 2) + 12x(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1 TênHàm( ) { .: Chương trình :. if ( ) { long xn(int n) { return ; if (n == 0) return 1; } long s = 0; Vòng lặp { for (int i=1; i ); s = s + i*i*xn(n–i); } return s; } } 12 Kỹ thuật lập trình đệ quy
  13. & VC BB Các bước xây dựng hàm đệ quy § Tổng quát hóa bài toán cụ thể thành bài toán tổng quát. Thông số hóa § Thông số hóa cho bài toán tổng quát bài toán § VD: n trong hàm tính tổng S(n), § Chia bài toán tổng quát ra thành: § Phần không đệ quy. Tìm thuật giải § Phần như bài toán trên nhưng tổng quát kích thước nhỏ hơn. § VD: S(n) = S(n – 1) + n, § Các trường hợp suy biến của bài toán. Tìm các trường § Kích thước bài toán trong trường hợp này là nhỏ nhất. hợp suy biến (neo) § VD: S(0) = 0 13 Kỹ thuật lập trình đệ quy
  14. & VC BB Cơ chế gọi hàm và STACK main() B() main { { ; ; A(); D(); ; ; D(); } A D ; } C() A() { ; C { } B ; B(); D() D ; B B B C C(); { STACK ; ; D A A A A A A A D } } M M M M M M M M M M M Thời gian 14 Kỹ thuật lập trình đệ quy
  15. & VC BB Nhận xét vCơ chế gọi hàm dùng STACK trong C phù hợp cho giải thuật đệ quy vì: § Lưu thông tin trạng thái còn dở dang mỗi khi gọi đệ quy. § Thực hiện xong một lần gọi cần khôi phục thông tin trạng thái trước khi gọi. § Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên. 15 Kỹ thuật lập trình đệ quy
  16. & VC BB Ví dụ gọi hàm đệ quy vTính số hạng thứ 4 của dãy Fibonacy F(4)5 F(3)3 +5 F(2)2 F(2)2 3 F(1)1 + F(1)1 +2 F(0)1 F(1)1 +2 F(0)1 16 Kỹ thuật lập trình đệ quy
  17. & VC BB Một số lỗi thường gặp vCông thức đệ quy chưa đúng, không tìm được bài toán đồng dạng đơn giản hơn (không hội tụ) nên không giải quyết được vấn đề. vKhông xác định các trường hợp suy biến – neo (điều kiện dừng). vThông điệp thường gặp là StackOverflow do: § Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm tràn STACK. § Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện dừng. 17 Kỹ thuật lập trình đệ quy
  18. & VC BB Các vấn đề đệ quy thông dụng Đệ quy?? 18 Kỹ thuật lập trình đệ quy
  19. & VC BB 1.Hệ thức truy hồi vKhái niệm § Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. A0 A1 An-2 An-1 Hàm truyAn hồi A0 A1 An-2 An-1 Hàm truyAn hồi 19 Kỹ thuật lập trình đệ quy
  20. & VC BB 1.Hệ thức truy hồi vVí dụ 1 § Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? vGiải pháp § Gọi Vh là số vi trùng tại thời điểm h. § Ta có: • Vh = 2Vh-1 • V0 = 2 Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2 20 Kỹ thuật lập trình đệ quy
  21. & VC BB 1.Hệ thức truy hồi vVí dụ 2 § Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu? vGiải pháp § Gọi Tn là số tiền có được sau n năm. § Ta có: • Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1 • V(0) = 1000 Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000 21 Kỹ thuật lập trình đệ quy
  22. & VC BB 2.Chia để trị (divide & conquer) vKhái niệm § Chia bài toán thành nhiều bài toán con. § Giải quyết từng bài toán con. § Tổng hợp kết quả từng bài toán con để ra lời giải. 22 Kỹ thuật lập trình đệ quy
  23. & VC BB 2.Chia để trị (divide & conquer) vVí dụ 1 § Cho dãy A đã sắp xếp thứ tự tăng. Tìm vị trí phần tử x trong dãy (nếu có) vGiải pháp § mid = (l + r) / 2; § Nếu A[mid] = x trả về mid. § Ngược lại • Nếu x < A[mid] tìm trong đoạn [l, mid – 1] • Ngược lại tìm trong đoạn [mid + 1, r] Sử dụng đệ quy nhị phân. 23 Kỹ thuật lập trình đệ quy
  24. & VC BB 2.Chia để trị (divide & conquer) vVí dụ 2 § Tính tích 2 chuỗi số cực lớn X và Y vGiải pháp § X = X2n-1 XnXn-1 X0, Y = Y2n-1 YnYn-1 Y0 n § Đặt XL=X2n-1 Xn, XN=Xn-1 X0 X=10 XL+XN n § Đặt YL=Y2n-1 Yn, YN=Yn-1 Y0 Y=10 YL+YN 2n n X*Y = 10 XLYL + 10 (XLYL+XNYN)+XNYN và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN Nhân 3 số nhỏ hơn (độ dài ½) đến khi có thể nhân được ngay. 24 Kỹ thuật lập trình đệ quy
  25. & VC BB 2.Chia để trị (divide & conquer) vMột số bài toán khác § Bài toán tháp Hà Nội § Các giải thuật sắp xếp: QuickSort, MergeSort § Các giải thuật tìm kiếm trên cây nhị phân tìm kiếm, cây nhị phân nhiều nhánh tìm kiếm. vLưu ý § Khi bài toán lớn được chia thành các bài toán nhỏ hơn mà những bài toán nhỏ hơn này không đơn giản nhiều so với bài toán gốc thì không nên dùng kỹ thuật chia để trị. 25 Kỹ thuật lập trình đệ quy
  26. & VC BB 3.Lần ngược (Backtracking) vKhái niệm § Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp. § Nếu không thành công thì “lần ngược” chọn bước khác. § Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần ngược” để truy tìm lời giải mới. § Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã đi tuần. 26 Kỹ thuật lập trình đệ quy
  27. & VC BB 3.Lần ngược (Backtracking) vVí dụ § Tìm đường đi từ X đến Y. A D B Y X C 27 Kỹ thuật lập trình đệ quy
  28. & VC BB Một số bài toán kinh điển THÁP HÀ NỘI TÁM HẬU # $ @ 1 2 3 1 3 2 MÃ ĐI TUẦN PHÁT SINH HOÁN VỊ 28 Kỹ thuật lập trình đệ quy
  29. & VC BB Tháp Hà Nội vMô tả bài toán § Có 3 cột A, B và C và cột A hiện có N đĩa. § Tìm cách chuyển N đĩa từ cột A sang cột C sao cho: • Một lần chuyển 1 đĩa • Đĩa lớn hơn phải nằm dưới. • Có thể sử dụng các cột A, B, C làm cột trung gian. 29 Kỹ thuật lập trình đệ quy
  30. & VC BB Tháp Hà Nội N đĩa A C = N-1? đĩa A B + Đĩa N A C + N-1 đĩa B C 1 N-1 N Cột nguồn A Cột trung gian B Cột đích C 30 Kỹ thuật lập trình đệ quy
  31. & VC BB Tám hậu vMô tả bài toán § Cho bàn cờ vua kích thước 8x8 § Hãy đặt 8 hoàng hậu lên bàn cờ này sao cho không có hoàng hậu nào “ăn” nhau: • Không nằm trên cùng dòng, cùng cột • Không nằm trên cùng đường chéo xuôi, ngược. 31 Kỹ thuật lập trình đệ quy
  32. & VC BB Tám hậu – Các dòng 0 1 n đường 2 3 4 5 6 7 32 Kỹ thuật lập trình đệ quy
  33. & VC BB Tám hậu – Các cột 0 1 2 3 4 5 6 7 n đường 33 Kỹ thuật lập trình đệ quy
  34. & VC BB Tám hậu – Các đường chéo xuôi 2n-1 đường 0 1 2 3 4 5 6 14 13 12 11 10 9 8 7 34 Kỹ thuật lập trình đệ quy
  35. & VC BB Tám hậu – Các đường chéo ngược 2n-1 đường 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 35 Kỹ thuật lập trình đệ quy
  36. & VC BB Tám hậu – Các dòng i = 2 j = 3 j+i=5 j-i+n-1=8 36 Kỹ thuật lập trình đệ quy
  37. & VC BB Mã đi tuần vMô tả bài toán § Cho bàn cờ vua kích thước 8x8 (64 ô) § Hãy đi con mã 64 nước sao cho mỗi ô chỉ đi qua 1 lần (xuất phát từ ô bất kỳ) theo luật: 5 6 4 7 3 8 2 1 37 Kỹ thuật lập trình đệ quy
  38. & VC BB Phân tích giải thuật đệ quy vSử dụng cây đệ quy (recursive tree) § Giúp hình dung bước phân tích và thế ngược. § Bước phân tích: đi từ trên xuống dưới. § Bước thế ngược đi từ trái sang phải, từ dưới lên trên. § Ý nghĩa • Chiều cao của cây  Độ lớn trong STACK. • Số nút  Số lời gọi hàm. 38 Kỹ thuật lập trình đệ quy
  39. & VC BB Nhận xét vƯu điểm § Sáng sủa, dễ hiểu, nêu rõ bản chất vấn đề. § Tiết kiệm thời gian thực hiện mã nguồn. § Một số bài toán rất khó giải nếu không dùng đệ qui. vKhuyết điểm § Tốn nhiều bộ nhớ, thời gian thực thi lâu. § Một số tính toán có thể bị lặp lại nhiều lần. § Một số bài toán không có lời giải đệ quy. 39 Kỹ thuật lập trình đệ quy
  40. & VC BB Ví dụ cây đệ quy Fibonacy F(4) F(3) F(2) F(2) F(1) F(1) F(0) F(1) F(0) Lặp lại 40 Kỹ thuật lập trình đệ quy
  41. & VC BB Khử đệ quy (tham khảo) vKhái niệm § Đưa các bài toán đệ quy về các bài toán không sử dụng đệ quy. § Thường sử dụng vòng lặp hoặc STACK tự tạo. § 41 Kỹ thuật lập trình đệ quy
  42. & VC BB Tổng kết vNhận xét § Chỉ nên dùng phương pháp đệ quy để giải các bài toán kinh điển như giải các vấn đề “chia để trị”, “lần ngược”. § Vấn đề đệ quy không nhất thiết phải giải bằng phương pháp đệ quy, có thể sử dụng phương pháp khác thay thế (khử đệ quy) § Tiện cho người lập trình nhưng không tối ưu khi chạy trên máy. § Bước đầu nên giải bằng đệ quy nhưng từng bước khử đệ quy để nâng cao hiệu quả. 42 Kỹ thuật lập trình đệ quy
  43. & VC BB Bài tập vBài 1: Các bài tập trên mảng sử dụng đệ quy. vBài 2: Viết hàm đệ quy xác định chiều dài chuỗi. vBài 3: Hiển thị n dòng của tam giác Pascal. § a[i][0] = a[i][i] = 1 § a[i][k] = a[i-1][k-1] + a[i-1][k] Dòng 0: 1 Dòng 1: 1 1 Dòng 2: 1 2 1 Dòng 3: 1 3 3 1 Dòng 4: 1 4 6 4 1 43 Kỹ thuật lập trình đệ quy
  44. & VC BB Bài tập vBài 4: Viết hàm đệ quy tính C(n, k) biết § C(n, k) = 1 nếu k = 0 hoặc k = n § C(n, k) = 0 nếu k > n § C(n ,k) = C(n-1, k) + C(n-1, k-1) nếu 0<k<n vBài 5: Đổi 1 số thập phân sang cơ số khác. vBài 6: Tính các tổng truy hồi. vBài 7: Bài toán “Tháp Hà Nội”. vBài 8: Bài toán “8 hậu”. vBài 9: Bài toán “Mã đi tuần”. 44 Kỹ thuật lập trình đệ quy