Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật đệ quy - Đỗ Tuấn Anh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật đệ quy - Đỗ Tuấn Anh

1. Cấutrúcdữ liệuvàgiải thuật Người thực hiện: Đỗ Tuấn Anh Email: anhdt@it-hut.edu.vn ĐT: 0989095167
2. Nộidung z Chương 1 – Thiếtkế và phân tích (5 tiết) z Chương 2 – Giảithuật đệ quy (10 tiết) z Chương 3 – Mảng và danh sách (5 tiết) z Chương 4 – Ngănxếp và hàng đợi (10 tiết) z Chương 5 – Cấu trúc cây (10 tiết) z Chương 8 – Tìm kiếm(5 tiết) z Chương 7 – Sắpxếp (10 tiết) z Chương 6 – Đồ thị (5 tiết)
3. Chương 2 – Giảithuật đệ quy 1. Khái niệm 2. Thiếtkế giảithuật đệ quy 3. Hiệulựccủa đệ quy 4. Đệ quy và quy nạp toán học 5. Đệ quy quay lui
4. 1. Khái niệm zLà mộtkỹ thuậtgiải quyết bài toán quan trọng trong đó: {Phân tích đốitượng thành các thành phầnnhỏ hơn mang tính chấtcủa chính đốitượng đó. zVí dụ: {Định nghĩasố tự nhiên: z1 là mộtsố tự nhiên zx là mộtsố tự nhiên nếux-1 làmộtsố tự nhiên
5. Ví dụ 1 - Tính giai thừa z Hàm tính giai thừachomộtsố nguyên: n! = n * ( n -1 ) * * 1 z Định nghĩa đệ quy: 1 if n = 0 // điềukiệndừng n! = n * ( n - 1)! if n > 0 // bước đệ quy
6. Tính giai thừa z Định nghĩa đệ quy chỉ ra một cách chính xác cách tính giai thừa 4! = 4 * 3! // Bước đệ quy (n = 4) = 4 * ( 3 * 2! ) // Bước đệ quy (n = 3) = 4 * ( 3 * ( 2 * 1!) ) // Bước đệ quy (n = 2) = 4 * ( 3 * ( 2 * ( 1 * 0! ) ) ) // Bước đệ quy (n = 1) = 4 * ( 3 * ( 2 * ( 1 * 1 ) ) ) // Điềukiệndừng ( n = 0) = 4 * ( 3 * ( 2 * 1 ) ) = 4 * ( 3 * 2 ) = 4 * 6 = 24
7. 1. Khái niệm(tiếp) z Giảithuật đệ quy: T đượcthựchiệnbằng T’ có dạng giống như T z Giảithuật đệ quy phảithỏa mãn 2 điềukiện: {Phảicóđiểmdừng: là trường hợpcơ sở (suy biến) nhỏ nhất, đượcthựchiện không cần đệ quy {Phảilàmchokíchthước bài toán thu nhỏ hơn: do đó làm cho bài toán giảmdần đếntrường hợpcơ sở z Thủ tục đệ quy: {Có lờigọi đến chính nó (đệ quy trựctiếp) hoặcchứalời gọi đếnthủ tục khác và thủ tục này chứalờigọi đếnnó (đệ quy gián tiếp) {Sau mỗilầngọi, kích thước bài toán thu nhỏ hơn {Phảikiểmtrađiểmdừng
8. Giảithuật đệ quy – ví dụ zTìm file trong thư mục trên máy tính zTra từ trong từđiển Anh-Anh
9. 2. Thiếtkế giảithuật đệ quy z3 bước: {Thông số hóa bài toán {Tìm điềukiệndừng {Phân rã bài toán zVí dụ bài toán: Tính N!
10. Bước 1: Thông số hóa bài toán z Tìm các thông số biểuthị kích thướccủa bài toán z Quyết định độ phứctạpcủa bài toán z Ví dụ: Tính N! { N trong hàm tính giai thừacủaN
11. Bước2: Tìmđiềukiệndừng z Là trường hợpgiải không đệ quy z Là trường hợpkíchthước bài toán nhỏ nhất z Ví dụ: Tính N! { 0! = 1
12. Bước 3: Phân rã bài toán z Phân rã bài toán thành các thành phần: { Hoặc không đệ quy { Hoặc là bài toán trên nhưng kích thướcnhỏ hơn z Bài toán viết đượcdướidạng công thức đệ quy => đơngiản z Ví dụ: Tính N! { N! = N * (N-1)!
13. Chương trình tính giai thừa // Sử dụng đệ quy long Factorial (long n) { // điềukiệndừng n == 0 if (n == 0) return 1; else // bước đệ quy return n * Factorial (n-1); }
14. Quan điểmN-máy Hàm tính giai thừa(n) cóthểđược xem nhưđược thựchiệnbởin-máy: Máy 4 (4 * 3!) khởi động máy 3 Máy 3 (3 * 2!) khởi động máy 2 Máy 2 (2 * 1!) khởi động máy 1 Máy 1 (1 * 0!) khởi động máy 0 4! KĐ 3! KĐ 2! KĐ 1! KĐ 0! 4 * 3! 3 * 2! 2 * 1! 1 * 0! 4! = 24 3! = 6 2! = 2 1! = 1 0! = 1 24 6 2 1 1
15. 24 Factorial(4) 6 4 * Factorial(3) 2 3 * Factorial(2) 1 2 * Factorial(1) 1 1 * Factorial(0)
16. Điềukiện đệ quy Phảicóđiểmdừng: nếu không sẽ tạo thành một chuỗivôhạn các lờigọihàm long Factorial(long n){ Oops!Oops! return n * Factorial(n-1); Không có điểm } dừng Phải làm cho bài toán đơngiảnhơn: long Factorial(long n){ if (n==0) return 1; else return n * Factorial(n+1); } Oops!Oops!
17. Dãy số Fibonacci zDãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, trong đómỗisố là tổng của2 sốđứng trước nó. zĐịnh nghĩa theo đệ quy: {F(0) = 0; {F(1) = 1; {F(n) = F(n-1)+ F(n-2);
18. Dãy số Fibonacci – Thủ tục đệ quy //Tính số Fibonacci sử dụng hàm đệ quy. int fib(int number) { if (number == 0) return 0; if (number == 1) return 1; return (fib(number-1) + fib(number-2)); } int main(){ int inp_number; printf ("Please enter an integer: “); scanf (“%d”, &inp_number); int intfib = fib(inp_number); printf("The Fibonacci number for %d is %d\n“,inp_number,intfib); return 0; }
19. Cơ chế thựchiện int fib(int num) { z Tính fibonacci của 4, num=4: if (num == 0) return 0; if (num == 1) return 1; fib(4): return 4 == 0 ? Sai; 4 == 1? Sai. (fib(num-1)+fib(num-2)); } fib(4) = fib(3) + fib(2) fib(3): 3 == 0 ? Sai; 3 == 1? Sai. fib(3) = fib(2) + fib(1) fib(2): 2 == 0? Sai; 2==1? Sai. fib(2) = fib(1)+fib(0) fib(1): 1== 0 ? Sai; 1 == 1? Đúng. fib(1) = 1; return fib(1);
20. Cơ chế thựchiện fib(0): 0 == 0 ? Đúng. fib(0) = 0; return fib(0); fib(2) = 1 + 0 = 1; return fib(2); fib(3) = 1 + fib(1) fib(1): 1 == 0 ? Sai; 1 == 1? Đúng fib(1) = 1; return fib(1); fib(3) = 1 + 1 = 2; return fib(3)
21. Cơ chế thựchiện fib(2): 2 == 0 ? Sai; 2 == 1? Sai. fib(2) = fib(1) + fib(0) fib(1): 1== 0 ? Sai; 1 == 1? Đúng. fib(1) = 1; return fib(1); fib(0): 0 == 0 ? Đúng. fib(0) = 0; return fib(0); fib(2) = 1 + 0 = 1; return fib(2); fib(4) = fib(3) + fib(2) = 2 + 1 = 3; return fib(4);
22. Thủ tục đệ quy tổng quát int Hàm_đệ_quy(DS tham số){ if(thỏa mãn điềukiệndừng) return giá_trị_dừng_tương_ứng; // other stopping conditions if needed return hàm_đệ_quy(tham số suy giảm) }
23. BàitoánthápHàNội Ban đầu: Cột1 Cột2 Cột3 Kếtthúc: Cột1 Cột2 Cột3 Quy tắc: đĩalớnhơn không được đặttrênđĩanhỏ hơn trong quá trình chuyển đĩa
24. Giảithuật đệ quy 1. Chuyển n –1 đĩatừ cột 1 sang cột2 1 2 3 2. Chuyển đĩadưới cùng từ cột 1 sang 3 1 2 3 3. Chuyểnn-1 đĩatừ cột2 sang cột3 2 1 3
25. Thủ tục đệ quy // chuyểnn đĩatừ cột nguồn sang cột đích // sử dụng một đĩa trung gian void hanoi (int n, int cot1, int cot3, int cot2) { if (n > 0) { hanoi(n-1, cot1, cot2, cot3); Chuyen_dia(n, cot1, cot3); hanoi(n-1, cot2, cot3, cot1); } }
26. Cơ chế thựchiện hanoi(n, cot1, cot3, cot2) hanoi(2, 1, 3, 2) hanoi(1, 1, 2, 3) hanoi(0, 1, 3, 2) “Chuyển đĩa1 từ cột 1 sang cột2” hanoi(0, 3, 2, 1) “Chuyển đĩa2 từ cột 1 sang cột3” hanoi(1, 2, 3, 1) hanoi(0, 2, 1, 3) “Chuyển đĩa1 từ cột 2 sang cột3” hanoi(0, 3, 1, 2)
27. Cây đệ quy trong trường hợp chuyển3 đĩa hanoi(3, 1, 3, 2) hanoi(2, 1, 2, 3) hanoi(2,2,3,1) hanoi(1, 1, 3, 2) hanoi(1,3,2,1) hanoi(1,2,1,3) hanoi(1,1,3,2) hanoi(0,1,2,3) hanoi(0,3,1,2) hanoi(0,2,3,1) hanoi(0,1,2,3) hanoi(0,2,3,1) hanoi(0,1,2,3) hanoi(0,3,1,2) hanoi(0,2,3,1)
28. 4. Hiệuquả củagiảithuật đệ quy z Nhược điểm: { Tốnkhônggiannhớ { Tốc độ chậm z Ưu điểm: đơngiản, ngắngọn, dễ viết code { Mộtsố giảithuật đệ quy cũng có hiệulựccao, vídụ như Quick sort z Mọigiảithuật đệ quy đềucóthể thay thế bằng mộtgiảithuật không đệ quy (sử dụng vòng lặp)
29. GọihàmvàBộ nhớ Stack Runtime stack: khi hàm đượcgọi, một vùng nhớ trên stack đượcsử dụng để lưutrữ: các tham số, địachỉ trở về củahàm Biến địa phương Activation Địachỉ Activation Frame Record trở về Các tham số
30. Đệ quy và Stack Stack được D D cấp B C C C D D D phát cho dữ A A A A A A A D D D D D liệu M M M M M M M M M M M M M M M Thờigian Các cột theo chiềudọcchỉ ra nội dung của stack tạimộtthời điểm, và sự thay đổi của stack khi gọi hàm và thoát khỏi hàm
31. Cây lờigọi hàm Bắt đầu Kếtthúc Cây gọi hàm tương M đương A D B C D Đệ quy là trường hợpkhi: D D •Mộthàmgọi chính nó, hoặc •Mộthàmgọimộtchuỗi các hàm khác trong đómột/ mộtvài trong số chúng gọilạihàmđầutiên
32. Gọihàmvàđịachỉ trở về long Factorial (long n) { F( ) int temp; if (n == 0) return 1;// giải phóng activation record else F( ) // lờigọi Factorial(n-1) temp = n * Factorial (n-1); RecLoc2 void main ( ) return temp; // giải phóng activation { // record int n; } // đẩy activation record của Factorial(4) } // vào Stack n = Factorial(4); } RecLoc1
33. Factorial(4) và Stack tham_sốđịa_chỉ_trả_về Lệnh trướckhitrả về Factorial(0) 0 RecLoc2 RecLoc2 temp = 1 * 1; // 1 từ Factorial (0) Factorial(1) 1 return temp; temp = 2 * 1; // 1 từ Factorial(1) Factorial(2) 2 RecLoc2 return temp; temp = 3 * 2; // 2 từ Factorial(2) Factorial(3) 3 RecLoc2 return temp; temp = 4 * 6; // 6 từ Factorial(3) Factorial(4) 4 RecLoc1 return temp; N = Factorial(4); // quay lạimain
34. Khửđệquy z Hàm tính giai thừa không đệ quy // Sử dụng vòng lặp long Factorial (long n) { long prod = 1; // 0! = 1 // tính tích = 1*2* * n for (i = 1; i < n+1; i++) prod * = i; return prod; }
35. Hàm tính Fibonacci không đệ quy //Tính số Fibonacci sử dụng vòng lặp //hiệuquả hơnnhiềuso với dùng đệ quy int fib(int n) { int f[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]; }
36. 4. Đệ quy và Quy nạptoánhọc zChứng minh tính đúng đắncủagiảithuật Factorial
37. Đánh giá giảithuật Tháp Hà nội Gọi f(n) là số lần chuyển đĩacầnthiết để chuyểnn đĩatừ cột 1 sang cột3. f(1) = 1; f(n) = 2 * f(n – 1) + 1, if n > 1 Dựđoán: f(n) = 2 * f(n – 1) + 1 = 22 * f(n–2) + 2 + 1 = = 2n-1 * f(1) + + 2 + 1 = 2n-1 + 2n-2 + + 2 + 1 = 2n –1 Chứng minh?
38. zChứng minh bằng quy nạp f(1) = 21 –1 = 1 Giả sửđúng vớin = k f(k) = 2k –1 f(k+1) = 2*f(k) +1 = 2*(2k –1) + 1 = 2k+1 -1 => Công thức đúng Các nhà sư phảichuyển64 đĩa. Giả sử mỗilầnchuyểnmất1 giây, các nhà sư sẽ phả11imất5 * 1011 năm= 25 lầntuổicủavũ trụ. Khi chuyển xong chồng đĩathìđã đến ngày tậnthế!
39. 5. Đệ quy quay lui (back tracking) z Bài toán 8 con hậu: “Hãy xếp 8 con hậu trên bàn cờ 8x8 sao cho không có con hậu nào có thểăn con hậu nào”
40. Đệ quy quay lui z Phương pháp “thử từng bước” {Thử dựđoán {Nếudựđoán là sai, quay trở lạivàthử dựđoán khác => quay lui z Dễ dang thể hiệnphương pháp quay lui bằng đệ quy {Các biếntrạng thái củahàmđệ quy đượclưutrữ trên Stack {Quay lui lạitrạng thái ban đầu Ù Quay trở lại hàm trước đó(hàmgọihàmhiệntại)
41. Bài toán 8 con hậu zGiảithuật1: {Thử lầnlượttấtcả các trường hợp ứng vớimọi vị trí của 8 con hậu {Số phép thử = 64*63* *58*57 = 178,462,987,637,760
42. Bài toán 8 con hậu z Nhậnxét: {Mỗicộtphải có 1 con hậu zCon hậu1 nằmtrêncột1 z zCon hậuj nằmtrêncộtj z zCon hậu8 nằmtrêncột8 {Các con hậuphải không cùng hàng {Các con hậuphải không nằmtrênđường chéo của nhau
43. Bài toán 8 con hậu zBài toán: Con hậuthứ j nằmtrêncộtj {[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8] {Lựachọn hàng cho từng con hậu để mỗi con hậu không ăn nhau zGiảithuật: {Thử lầnlượttừng vị trí hàng của con hậu 1 (1-8) {Vớitừng vị trí của con hậu1 zThử lầnlượttừng vị trí hàng của con hậu2 zVớitừng vị trí củacon hậu2 • Thử lầnlượttừng vị trí hàng của con hậu3
44. Giảithuật function Try (column) { Thử lầnlượttừng vị trí hàng for (row = 1; row <= 8; row++) { if ( [row, column] là an toàn) { Đặt con hậuvàovị trí [row, column]; Nếuvị trí thử khôngif (column bị == 8) Con hậuthứ 8 là an toàn con hậunàotấncông In kếtquả; else Đệ quy để vớicon hậutiếp Try (column + 1); Xóa con hậukhỏivị trí [row, column]; } } Xóa để tiếptụcthử vị trí } [row+1, column]
45. Kiểm tra An toàn
46. Thiếtkế dữ liệu z int pos[] : lưuvị trí của con hậu {pos[column] = row Ù có con hậutạivị trí (row, column) z bool rowFlag[] : lưutrạng thái của các hàng {rowFlag[i] = false Ù không có con hậu nào chiếm hàng i z bool rowPlusCol[] : lưutrạng thái củacácđường chéo x+y (2 ≤ x+y ≤ 16) {rowPlusCol[x+y] = false Ù không có quân hậunàochiếm đường chéo x+y z bool rowMinusCol[] : lưutrạng thái củacácđường chéo y-x (-7 ≤ y-x ≤ 7) {rowMinusCol[y-x] = false Ù không có quân hậu nào chiếm đường chéo y-x
47. Kiểm tra an toàn củavị trí [row, column] zHàng row chưabị chiếm {rowFlag [row] == false ? zĐường chéo row+column chưabị chiếm {rowPlusCol [row+column] == false ? zĐường chéo row-column chưabị chiếm {rowMinusCol [row-column] == false ?
48. Đặtcon hậuvàovị trí [row, column] zLưuvị trí củacon hậu {pos[column] = row zĐánh dấu hàng row đãbị chiếm {rowFlag[row] = true zĐánh dấu đường chéo row+column đãbị chiếm {rowPlusCol [row+column] = true zĐánh dấu đường chéo row-column đãbị chiếm {rowMinusCol [row-column] = true
49. Xóa con hậukhỏivị trí [row, column] zXóa vị trí củacon hậu {pos[column] = -1 zĐánh dấulại hàng row chưabị chiếm {rowFlag[row] = false zĐánh dấulại đường chéo row+column chưabị chiếm {rowPlusCol [row+column] = false zĐánh dấulại đường chéo row-column chưabị chiếm {rowMinusCol [row-column] = false
50. In kếtquả function PrintSolution(int pos[]) { for (int col=1; col<=8; col++) printf(“Con hau thu %d nam tai hang %d”, col, pos[col] ); }
51. function Try (int column) { for (row = 1; row <= 8; row++) { if (!rowFlag [row] && !rowPlusCol [row+column] && !rowMinusCol [row-column] ) { //Đặtcon hậuvàovị trí [row, column] pos[column] = row; rowFlag[row] = true; rowPlusCol [row+column] = true; rowMinusCol [row-column] = true; if (column == 8) // con hậuthứ 8 an toàn PrintSolution(pos); else Try (column + 1); // Xóa con hậukhỏivị trí [row, column] pos[column] = -1; rowFlag[row] = false; rowPlusCol [row+column] = false; rowMinusCol [row-column] = false; } }