Kỹ thuật lập trình - Bài 3: Giải thuật đệ quy - Ngô Hữu Dũng

Kỹ thuật lập trình Bài 3 – Giải thuật đệ quy Ngô Hữu Dũng Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201761 Quy nạp toán học Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201762  Chứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.  Phương pháp quy nạp:  Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúng  Bước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.  Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + + (2n-1) = n2 (*), với n ≥ 1  Bước cơ sở: Trường hợp n = 1, ta có (2n-1) = n2 = 1 là đúng hiển nhiên.  Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2  Khi đó: S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1) = (k + 1)2  Vậy S(k + 1) = (k + 1)2 là đúng. Suy ra S(n) đúng với mọi n ≥ 1. Ngô Hữu Dũng Lập trình đệ quy Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201763  Lập trình tính S(n) = 1 + 3 + 5 + + (2n – 1) = n2 với n ≥ 1.  Từ bài toán quy nạp ta có:  Bước cơ sở: S(1) = 1  Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1] hay S(k) = S(k – 1) + (2k – 1)  Phương pháp lập trình đệ quy:  Phần cơ sở: S(1) = 1  Phần đệ quy: S(n) = S(n – 1) + (2n – 1)  Áp dụng vào lập trình: 1. int S(int n) 2. { 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } Ngô Hữu Dũng Cách hoạt động Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201764  Giả sử n = 5, hàm đệ quy chạy như sau: S(5) = S(4) + 9 // Gọi hàm S(4) S(4) = S(3) + 7 // Gọi hàm S(3) S(3) = S(2) + 5 // Gọi hàm S(2) S(2) = S(1) + 3 // Gọi hàm S(1) S(1) = 1 // Return S(1) S(2) = 1 + 3 // Return S(2) S(3) = 1 + 3 + 5 // Return S(3) S(4) = 1 + 3 + 5 + 7 // Return S(4) S(5) = 1 + 3 + 5 + 7 + 9 = 25 = 52 // Return S(5) 1. int S(int n) 2. { 3. if (n==1) return 1; 4. else return S(n-1) + (2*n–1); 5. } Ngô Hữu Dũng Khái niệm đệ quy Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201765  Khái niệm  Một hàm gọi là đệ quy khi có phép gọi lại chính nó trong thân hàm  Thành phần  Phần cơ sở: Điều kiện thoát  Phần đệ quy: Có phép gọi lại chính nó  Ưu điểm  Thuận lợi trong việc giải những bài toán có tính chất quy nạp  Làm gọn chương trình  Nhược điểm  Không tối ưu, tốn bộ nhớ Ngô Hữu Dũng Một số loại đệ quy Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201766  Đệ quy tuyến tính (Linear Recursion)  Hàm đệ quy chỉ gọi lại chính nó một lần  Đệ quy nhị phân, đa đệ quy (Binary Recursion, Multiple Recursion)  Hàm đệ quy gọi lại chính nó hai lần hoặc nhiều hơn hai lần  Đệ quy đuôi (Tail Recursion)  Lời gọi đệ quy được thực hiện ở cuối hàm đệ quy  Đệ quy lồng (Nested Recursion)  Tham số của một lời gọi đệ quy là một lời gọi đệ quy  Đệ quy hỗ tương (Mutual Recursion)  Hai hàm đệ quy gọi lẫn nhau  Đệ quy quay lui (Backtracking)  Là hàm đệ quy có phép thử và sai Ngô Hữu Dũng Đệ quy tuyến tính Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201767  Chỉ có một lời gọi đệ quy  Được dùng thông dụng  Ví dụ  Tính giai thừa Fact(n) với n > 0  Fact(n) = 1 * 2 * 3 * * n  Phần cơ sở: Fact(1) = 1  Phần đệ quy: Fact(n)=n*Fact(n-1)  Tính T(n) = 1 + 2 + 3 + + n  Phần cơ sở: T(1) = 1  Phần đệ quy: T(n) = T(n-1) + n 1. int Fact(int n) 2. { 3. if (n==1) 4. return 1; 5. else 6. return n * Fact(n-1); 7. } Ngô Hữu Dũng 1. int T(int n) 2. { 3. if (n==1) 4. return 1; 5. else 6. return T(n-1) + n; 7. } Đệ quy nhị phân Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201768  Hàm đệ quy có hai lời gọi đệ quy tại một thời điểm  Thường dùng trong các bài toán kiểu cấu trúc cây  Ví dụ: Tính số Fibonacci thứ n, với n > 0  Fib(1) = 1, Fib(2) = 1  Fib(n) = Fib(n-1) + Fib(n-2)  Tính Fib(5) = ?  = Fib(4)+Fib(3)  = Fib(3)+Fib(2) + Fib(2)+Fib(1)  = Fib(2)+Fib(1)+1+1+1  = 5 1. int Fib(int n) 2. { 3. if (n==1 || n==2) 4. return 1; 5. else 6. return Fib(n-1)+Fib(n-2); 7. } Ngô Hữu Dũng Fib(1) Fib(2) Fib(3) Fib(4) Fib(5) 1 1 2 3 5 Đệ quy nhiều lần Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201769  Lời gọi đệ quy được thực hiện nhiều lần trong hàm  Ví dụ: Tính hàm mystery  Hàm có hai lời gọi đệ quy  Hàm trả về kết quả ?  Tính mystery(2,4) = ?  = mystery(4, 2)  = mystery(8, 1)  = mystery(16, 0) + 8 = 8  Vậy mystery(2,4) = ? 1. int mystery(int a, int b) 2. { 3. if (b == 0) 4. return 0; 5. if (b % 2 == 0) 6. return mystery(a+a, b/2); 7. else 8. return mystery(a+a, b/2)+a; 9. } Ngô Hữu Dũng Đệ quy nhiều lần (tt) Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201770  Thay dòng số 4 thành return 1; và thay dấu + bằng dấu *  Hàm trả về kết quả?  Tính mystery(2,4) = ?  = mystery(4,2)  = mystery(16,1)  = mystery(256,0)*16  = 16  Vậy mystery(2,4) = ? 1. int mystery(int a, int b) 2. { 3. if (b == 0) 4. return 1; 5. if (b % 2 == 0) 6. return mystery(a*a, b/2); 7. else 8. return mystery(a*a, b/2)*a; 9. } Ngô Hữu Dũng Đệ quy đuôi Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201771  Hàm đệ quy có lời gọi đệ quy ở cuối hàm  Ví dụ  Tính số Fibonacci thứ n, với n > 0  Tính Fib(5,1,1) = ?  = Fib(5,1,1)  = Fib(4,1,2)  = Fib(3,2,3)  = Fib(2,3,5)  = Fib(1,5,8)  = 5 1. int Fib(int n, int x, int y) 2. { 3. if (n==1) 4. return x; 5. else 6. return Fib(n-1, y, x+y); 7. } Ngô Hữu Dũng Fib(1) Fib(2) Fib(3) Fib(4) Fib(5) 1 1 2 3 5 Đệ quy lồng Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201772  Lời gọi đệ quy là tham số của một lời gọi đệ quy  Ví dụ  Tính hàm Ackermann  Trường hợp m>0 và n>0, lời gọi đệ quy chính là tham số của một lời gọi đệ quy. 1. int A(int m, int n) 2. { 3. if (m==0) 4. return n + 1; 5. if (m>0 && n==0) 6. return A(m-1, 1); 7. if (m>0 && n>0) 8. return A(m-1, A(m, n - 1)); 9. } , = + 1 ( 1,1) ( 1, , 1 ) = 0 > 0 à = 0 > 0 à > 0 Đệ quy hỗ tương Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201773  Các hàm gọi lẫn nhau  Hàm A gọi B và hàm B gọi lại A.  Ví dụ  Tìm số n là chẵn hay lẻ  Ví dụ SoLe(5) = ?  = SoChan(4)  = SoLe(3)  = SoChan(2)  = SoLe(1)  = SoChan(0) = 1 1. bool SoLe(int n) 2. { 3. if (n==0) 4. return 0; 5. else 6. return SoChan(n-1); 7. } 8. 9. bool SoChan(int n) 10. { 11. if (n==0) 12. return 1; 13. else 14. return SoLe(n-1); 15. } Ngô Hữu Dũng Đệ quy quay lui – thử và sai Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201774  Liệt kê các kết quả thỏa mãn những điều kiện ràng buộc nào đó  Mỗi kết quả được xây dựng từ các phần tử  Mỗi phần tử của kết quả được chọn bằng cách thử tất cả các khả năng  Ví dụ: Liệt kê tất cả các số có n chữ số, được hình thành từ các chữ số từ 1 đến n  Gọi lietke(1,2)  Kết quả: 11 12 21 22 Ngô Hữu Dũng 1. int so[10]; 2. void in(int n) // In số 3. { 4. for (int i=1;i<=n;i++) 5. printf("%d",so[i]); 6. printf(" "); 7. } 8. void lietke(int i, int n) 9. { 10. for (int j=1;j<=n;j++) 11. { 12. so[i] = j; // Chọn số j 13. if (i==n) // Đủ n số 14. in(n); 15. else 16. lietke(i+1,n);//next 17. } 18. } Cách hoạt động Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201775  Lần lượt xét các trường hợp cho số thứ nhất  Ứng với mỗi trường hợp của số thứ nhất, tìm số thứ hai  Cứ như vậy cho đến khi tìm được n số thì xuất kết quả ra màn hình Ngô Hữu Dũng lietke(1,2) lietke(2,2) lietke(2,2) so[1]=1 so[1]=2 11 so[2]=1 so[2]=2 so[2]=1 so[2]=2 12 21 22 1. int so[10]; 2. void in(int n) // In số 3. { 4. for (int i=1;i<=n;i++) 5. printf("%d",so[i]); 6. printf(" "); 7. } 8. void lietke(int i, int n) 9. { 10. for (int j=1;j<=n;j++) 11. { 12. so[i] = j; // Chọn số j 13. if (i==n) // Đủ n số 14. in(n); 15. else 16. lietke(i+1,n);//next 17. } 18. } Liệt kê các dãy nhị phân có độ dài n Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201776  Dãy nhị phân gồm các phần tử là số nhị phân  Có giá trị 0 hoặc 1  Ở dòng 10, biến j chạy từ 0 đến 1  Bài trước, slide 74-75, biến j chạy từ 1 đến n  Tương tự, nếu liệt kê dãy bát phân  Biến j chạy từ 0 đến 7  Tương tự, nếu liệt kê dãy thập lục phân  Biến j chạy từ 0 đến 15, tức từ 0 đến F (!?)  nhiphan(1,4)  0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1. int so[10]; 2. void in(int n) // In số 3. { 4. for (int i=1;i<=n;i++) 5. printf("%d",so[i]); 6. printf(" "); 7. } 8. void nhiphan(int i, int n) 9. { 10. for (int j=0;j<=1;j++) 11. { 12. so[i] = j; // Chọn số j 13. if (i==n) // Đủ n số 14. in(n); 15. else 16. nhiphan(i+1,n); 17. } 18. } Liệt kê các dãy thập lục phân có độ dài n Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201777  Dãy thập lục phân gồm các phần tử là số thập lục phân  Giá trị từ 0 đến F  Mảng so_hexa khai báo các chữ số thập lục phân (dòng 2-3)  Thay số thành ký tự  hexa(1,2)  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB AC AD AE AF B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE BF C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 1. char so[10]; 2. char so_hexa[16]={'0','1','2','3','4','5', 3. '6','7','8','9','A','B','C','D','E','F'}; 4. void in_hexa(int n) // In số hexa 5. { 6. for (int i=1;i<=n;i++) 7. printf("%c",so[i]);// In kiểu ký tự 8. printf(" "); 9. } 10. void hexa(int i, int n) 11. { 12. for (int j=0;j<=15;j++) 13. { 14. so[i] = so_hexa[j];// Chọn chữ số j 15. if (i==n) // Đủ n số 16. in_hexa(n); 17. else 18. hexa(i+1,n); 19. } 20. } Liệt kê các tập con k phần tử của dãy số từ 1 đến n (1≤k≤n) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201778  Còn gọi là tổ hợp chập k của n phần tử  Các tập con không trùng nhau, không phân biệt thứ tự, vị trí  {1,2,3} = {2,1,3} = {2,3,1}  Các phần tử được chọn từ so[i-1]+1 đến n-k+i  i có giá trị từ 1 đến k  Phần tử cuối cùng, tức i = k, biến j chạy đến n  Ví dụ  tapcon(1,2,3) = ! ! ! = 3  12 13 23  tapcon(1,5,5) = 1  12345  tapcon(1,3,6) = 20  123 124 125 126 134 135 136 145 146 156 234 235 236 245 246 256 345 346 356 456 1. char so[10]; 2. void in(int k) 3. { 4. for (int i=1;i<=k;i++) 5. printf("%d",so[i]); 6. printf(" "); 7. } 8. void tapcon(int i, int k, int n) 9. { 10. so[0] = 0; 11. for (int j=so[i-1]+1;j<=n-k+i;j++) 12. { 13. so[i] = j; 14. if (i==k) 15. in(k); 16. else 17. tapcon(i+1,k,n); 18. } 19. } Liệt kê các hoán vị Kỹ thuật lập trình | DHTH11C | HK1 | 2016-201779  Liệt kê các hoán vị của các số từ 1 đến n  Các chữ số không được trùng nhau  Phải kiểm tra xem một số đã được chọn hay chưa?  Dùng mảng kiểu bool để đánh dấu và bỏ đánh dấu một số được chọn hoặc bỏ chọn  hoanvi(1,3):  123 132 213 231 312 321 Ngô Hữu Dũng 1. int so[10]; 2. bool kt[10]={1,1,1,1,1,1,1,1,1,1} 3. void hoanvi(int i, int n) 4. { 5. for (int j=1;j<=n;j++) 6. if (kt[j]) // Số j chưa được dùng 7. { 8. so[i] = j; // Chọn j 9. if (i==n) // Đủ n số 10. in(n); 11. else 12. { 13. kt[j]=false; // Đánh dấu 14. hoanvi(i+1,n); // Tìm số tiếp 15. kt[j]=true; // Bỏ đánh dấu 16. } 17. } 18. } Chỉnh hợp chập k của n phần tử (1≤k≤n) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201780  Lấy k phần tử trong số n phần tử, mỗi cách sắp xếp là một chỉnh hợp  Tổ hợp không phân biệt cách sắp xếp.  Chỉnh hợp phân biệt vị trí, thứ tự, cách sắp xếp  Tương tự bài liệt kê hoán vị ở slide trước nhưng chỉ lấy k số trong n phần tử  Bài trước hoán vị n phần tử  chinhhop(1,2,3) = ! ! = 6  12 13 21 23 31 32  chinhhop(1,3,3) = 6  123 132 213 231 312 321  Chính là hoanvi(1,3) 1. int so[10]; 2. bool kt[10]={1,1,1,1,1,1,1,1,1,1} 3. void chinhhop(int i, int k, int n) 4. { 5. for (int j=1;j<=n;j++) 6. if (kt[j]) // Số j chưa được dùng 7. { 8. so[i] = j; // Chọn j 9. if (i==k) // Đủ k số 10. in(k); 11. else 12. { 13. kt[j]=false; // Đánh dấu 14. chinhhop(i+1,k,n); 15. kt[j]=true; // Bỏ đánh dấu 16. } 17. } 18. } Bài toán xếp quân hậu Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201781  Tìm các cách xếp n quân hậu trên bàn cờ n x n sao cho các quân cờ không ăn được nhau  Quân hậu có thể ăn ngang, dọc, chéo  Lưu vị trí các quân hậu trên bàn cờ (x,y)  Mảng h (hậu) gồm n phần tử tương ứng với n hàng, mỗi phần tử lưu vị trí cột có giá trị từ 1 đến n  Dùng giải thuật đệ quy quay lui lần lượt thử chọn vị trí các cột trên từng hàng  Khi một quân hậu được được đặt lên bàn cờ, các vị trí liên quan theo chiều ngang, dọc, chéo cần được đánh dấu để tránh đặt quân cờ khác h[x]=y h[1]=1 h[2]=5 h[3]=8 h[4]=6 h[5]=3 h[6]=7 h[7]=2 h[8]=4 Bài toán xếp quân hậu (2) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201782  Đánh dấu  Chiều ngang: Mỗi quân cờ được đặt trên một hàng khác nhau tương ứng với mỗi phần tử ở mảng h  Chiều dọc: Dùng một mảng kiểu bool d[1→n] để đánh dấu  Chéo lên: Có tính chất (x + y) là một số cố định  Dùng một mảng kiểu bool cl[2→2n] để đánh dấu  Chéo xuống: Có tính chất x – y là một số cố định  (x – y) cố định nên (x – y + n) cũng cố định  Dùng một mảng kiểu bool cx[1→2n-1] để đánh dấu  Ví dụ quân hậu được đặt ở vị trí: h[x]=y (h[5]=3)  d[y] = d[3] = false  cl[x+y] = cl[5+3] = cl[8] = false  cx[x-y+n] = cx[5-3+8] = cx[10] = false; Bài toán xếp quân hậu (3) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201783 1. void quan_hau(int x, int n) 2. { 3. for(int y=1; y<=n; y++) 4. if(d[y]&&cl[x+y]&&cx[x-y+n]) 5. { 6. hau[x] = y; 7. if(x==n)in_banco(n); 8. else 9. { 10. d[y] = false; 11. cl[x+y] = false; 12. cx[x-y+n] = false; 13. quan_hau(x+1,n); 14. d[y] = true; 15. cl[x+y] = true; 16. cx[x-y+n] = true; 17. } 18. } 19. } 1. #include 2. void quan_hau(int, int); 3. void in_banco(int); 4. #define max 10 5. int h[max]; 6. bool d[max]; 7. bool cl[2*max]; 8. bool cx[2*max]; 9. 10. int main() 11. { 12. int i; 13. for(i=0;i<max;i++) d[i]=true; 14. for(i=0;i<2*max;i++) 15. { 16. cl[i]=true;cx[i]=true; 17. } 18. quan_hau(1,8); 19. } Bài toán xếp quân hậu (4) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201784 1. #include void in_banco(int n) 2. { 3. int i,j,k; 4. for(k=1;k<=n;k++) printf("+----"); 5. printf("+\n"); 6. for(i=1; i<=n; i++) 7. { 8. printf("| "); 9. for(j=1;j<=n;j++) 10. if(j==h[i]) 11. printf("%c%c | ",219,219); 12. else 13. printf(" | "); 14. printf("\n"); 15. for(k=1;k<=n;k++) printf("+----"); 16. printf("+\n"); 17. } 18. getchar(); 19. } Trò chơi Sudoku Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201785  Điền các số từ 1 đến 9 vào bàn cờ 9 x 9, sao cho  Các số trên cùng hàng khác nhau  Các số trên cùng cột khác nhau  Các số trong mỗi vùng 3 x 3 khác nhau  Dùng mảng hai chiều để lưu bàn cờ  Dùng thuật toán đệ quy quay lui để chọn giá trị cho từng ô  Kiểm tra chiều ngang, dọc và ô 3 x 3 tránh trùng số  Xuất mảng hai chiều để in kết quả  Nhận xét  Kích cỡ bàn cờ có dạng: 3 x 3 = 9  Ta có thể làm bài toán tương tự với các kích cỡ khác  2 x 2 = 4  4 x 4 =16 3 x 3 Trò chơi Sudoku (2) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201786 1. void sudoku(int banco[size][size],int x,int y) 2. { 3. int i; 4. for(i=1; i<=size; i++) 5. if(kt(i,x,y)) 6. { 7. banco[x][y]=i; 8. if(y<size-1) 9. sudoku(banco,x,y+1); 10. else 11. if(x<size-1) 12. sudoku(banco,x+1,0); 13. else 14. in(); 15. banco[x][y]=0; 16. } 17. } 2 x 2 4 x 4 Trò chơi Sudoku (3) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201787 1. #include 2. #define s 3 3. #define size s*s 4. int banco[size][size]; 5. bool kt(int k, int x, int y) 6. { 7. int i,j; 8. for(i=0; i<size; i++) 9. if(banco[x][i]==k 10. || banco[i][y]==k) 11. return 0; 12. x=x/s,y=y/s; 13. for(i=x*s; i<x*s+s; i++) 14. for(j=y*s; j<y*s+s; j++) 15. if(banco[i][j]==k) 16. return 0; 17. return 1; 18. } 1. void in() 2. { 3. int i,j; 4. printf("\n"); 5. for(i=0; i<size; i++) 6. { 7. for(j=0;j<size;j++) 8. printf(" %d",banco[i][j]); 9. printf("\n"); 10. } 11. getchar(); 12. } 13. int main() 14. { 15. sudoku(banco,0,0); 16. } Tháp Hà Nội Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201788  Chuyển chồng đĩa từ cột 1 sang cột 3 theo quy tắc:  Mỗi lần chỉ được di chuyển 1 đĩa từ cột này sang cột khác  Chỉ được di chuyển đĩa trên cùng của cột  Đĩa có kích thước lớn hơn luôn nằm dưới.  Tính đệ quy của bài toán, để chuyển n đĩa từ cột một sang cột 3  Bước cơ sở, n =1: Ta chuyển một đĩa từ cột 1 sang cột 3  Bước đệ quy: n > 1  Chuyển n-1 đĩa sang cột trung gian (đệ quy)  Chuyển 1 đĩa dưới cùng từ cột 1 sang cột 3  Chuyển n-1 đĩa từ cột trung gian sang cột 3 (đệ quy) Tháp Hà Nội (2) Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201789  1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa) 2. { 3. if (sodia==1)chuyen(toaMot, toaBa); 4. else 5. { 6. chuyendia(sodia-1,toaMot,toaBa,toaHai); 7. chuyen(toaMot, toaBa); 8. chuyendia(sodia-1,toaHai,toaMot,toaBa); 9. } 10. } Hết bài 3 Ngô Hữu DũngKỹ thuật lập trình | DHTH11C | HK1 | 2016-201790  Quy nạp toán học  Giải thuật đệ quy  Các loại đệ quy  Tuyến tính  Nhị phân  Đệ quy đuôi  Hỗ tương  Quay lui  Một số bài toán