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

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

1. Kỹ thuật lập trình Bài 3 – Giải thuật đệ quy Ngô Hữu Dũng 61 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
2. Quy nạp toán học  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. 62 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
3. Lập trình đệ quy  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) 1. int S(int n) 2. {  Áp dụng vào lập trình: 3. if (n==1) return 1; 4. else return S(n-1) + (2*n – 1); 5. } 63 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
4. Cách hoạt động  Giả sử n = 5, 1. int S(int n) 2. { hàm đệ quy chạy như sau: 3. if (n==1) return 1; S(5) = S(4) + 9 // Gọi hàm S(4) 4. else return S(n-1) + (2*n–1); S(4) = S(3) + 7 // Gọi hàm S(3) 5. } 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) 64 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
5. Khái niệm đệ quy  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ớ 65 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
6. Một số loại đệ quy  Đệ 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 66 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
7. Đệ quy tuyến tính 1. int Fact(int n)  Chỉ có một lời gọi đệ quy 2. {  Được dùng thông dụng 3. if (n==1)  Ví dụ 4. return 1; 5.  Tính giai thừa Fact(n) với n > 0 else 6. return n * Fact(n-1);  Fact(n) = 1 * 2 * 3 * * n 7. }  Phần cơ sở: Fact(1) = 1  Phần đệ quy: Fact(n)=n*Fact(n-1) 1. int T(int n)  Tính T(n) = 1 + 2 + 3 + + n 2. {  Phần cơ sở: T(1) = 1 3. if (n==1)  Phần đệ quy: T(n) = T(n-1) + n 4. return 1; 5. else 6. return T(n-1) + n; 7. } 67 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
8. Đệ quy nhị phân  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 1. int Fib(int n)  Fib(n) = Fib(n-1) + Fib(n-2) 2. { 3. if (n==1 || n==2) 4. return 1;  Tính Fib(5) = ? 5. else  = Fib(4)+Fib(3) 6. return Fib(n-1)+Fib(n-2);  = Fib(3)+Fib(2) + Fib(2)+Fib(1) 7. }  = Fib(2)+Fib(1)+1+1+1 Fib(1) Fib(2) Fib(3) Fib(4) Fib(5)  = 5 1 1 2 3 5 68 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
9. Đệ quy nhiều lần  Lời gọi đệ quy được thực hiện nhiều lần trong hàm 1. int mystery(int a, int b)  Ví dụ: Tính hàm mystery 2. {  Hàm có hai lời gọi đệ quy 3. if (b == 0)  Hàm trả về kết quả ? 4. return 0; 5. if (b % 2 == 0)  Tính mystery(2,4) = ? 6. return mystery(a+a, b/2);  = mystery(4, 2) 7. else  = mystery(8, 1) 8. return mystery(a+a, b/2)+a;  = mystery(16, 0) + 8 = 8 9. }  Vậy mystery(2,4) = ? 69 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
10. Đệ quy nhiều lần (tt)  Thay dòng số 4 thành return 1; và thay dấu + bằng dấu * 1. int mystery(int a, int b)  Hàm trả về kết quả? 2. { 3. if (b == 0)  Tính mystery(2,4) = ? 4. return 1;  = mystery(4,2) 5. if (b % 2 == 0)  = mystery(16,1) 6. return mystery(a*a, b/2);  = mystery(256,0)*16 7. else  = 16 8. return mystery(a*a, b/2)*a; 9. }  Vậy mystery(2,4) = ? 70 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
11. Đệ quy đuôi  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 1. int Fib(int n, int x, int y)  Tính Fib(5,1,1) = ? 2. {  = Fib(5,1,1) 3. if (n==1)  = Fib(4,1,2) 4. return x;  = Fib(3,2,3) 5. else 6. return Fib(n-1, y, x+y);  = Fib(2,3,5) 7. }  = Fib(1,5,8)  = 5 Fib(1) Fib(2) Fib(3) Fib(4) Fib(5) 1 1 2 3 5 71 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
12. Đệ quy lồng  Lời gọi đệ quy là tham số của một lời gọi đệ quy  Ví dụ + 1 = 0  Tính hàm Ackermann , = ( 1,1) > 0 à = 0 ( 1, , 1 ) > 0 à > 0  Trường hợp m>0 và n>0, lời gọi đệ quy chính là tham 1. int A(int m, int n) số của một lời gọi đệ quy. 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. } 72 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
13. Đệ quy hỗ tương  Các hàm gọi lẫn nhau 1. bool SoLe(int n) 2. {  Hàm A gọi B và hàm B gọi lại A. 3. if (n==0)  Ví dụ 4. return 0; 5. else  Tìm số n là chẵn hay lẻ 6. return SoChan(n-1); 7. } 8.  Ví dụ SoLe(5) = ? 9. bool SoChan(int n)  = SoChan(4) 10. {  = SoLe(3) 11. if (n==0) 12. return 1;  = SoChan(2) 13. else  = SoLe(1) 14. return SoLe(n-1);  = SoChan(0) = 1 15. } 73 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
14. Đệ quy quay lui – thử và sai  Liệt kê các kết quả thỏa mãn những điều 1. int so[10]; 2. void in(int n) // In số kiện ràng buộc nào đó 3. { 4. for (int i=1;i<=n;i++)  Mỗi kết quả được xây dựng từ các phần tử 5. printf("%d",so[i]);  Mỗi phần tử của kết quả được chọn bằng 6. printf(" "); 7. } cách thử tất cả các khả năng 8. void lietke(int i, int n) 9. { 10. for (int j=1;j<=n;j++)  Ví dụ: Liệt kê tất cả các số có n chữ số, 11. { được hình thành từ các chữ số từ 1 đến n 12. so[i] = j; // Chọn số j 13. if (i==n) // Đủ n số  Gọi lietke(1,2) 14. in(n); 15. else  Kết quả: 11 12 21 22 16. lietke(i+1,n);//next 17. } 18. } 74 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
15. Cách hoạt động  Lần lượt xét các trường hợp cho số thứ nhất 1. int so[10];  Ứng với mỗi trường hợp của số thứ nhất, tìm 2. void in(int n) // In số số thứ hai 3. { 4. for (int i=1;i<=n;i++)  Cứ như vậy cho đến khi tìm được n số thì 5. printf("%d",so[i]); xuất kết quả ra màn hình 6. printf(" "); 7. } lietke(1,2) 8. void lietke(int i, int n) 9. { 10. for (int j=1;j<=n;j++) so[1]=1 so[1]=2 11. { 12. so[i] = j; // Chọn số j lietke(2,2) lietke(2,2) 13. if (i==n) // Đủ n số 14. in(n); so[2]=1 so[2]=2 so[2]=1 so[2]=2 15. else 16. lietke(i+1,n);//next 17. } 11 12 21 22 18. } 75 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
16. Liệt kê các dãy nhị phân có độ dài n  Dãy nhị phân gồm các phần tử là số nhị 1. int so[10]; 2. void in(int n) // In số phân 3. {  Có giá trị 0 hoặc 1 4. for (int i=1;i<=n;i++) 5. printf("%d",so[i]);  Ở dòng 10, biến j chạy từ 0 đến 1 6. printf(" ");  Bài trước, slide 74-75, biến j chạy từ 1 đến n 7. } 8. void nhiphan(int i, int n)  Tương tự, nếu liệt kê dãy bát phân 9. {  Biến j chạy từ 0 đến 7 10. for (int j=0;j<=1;j++) 11. {  Tương tự, nếu liệt kê dãy thập lục phân 12. so[i] = j; // Chọn số j  Biến j chạy từ 0 đến 15, tức từ 0 đến F (!?) 13. if (i==n) // Đủ n số 14. in(n);  nhiphan(1,4) 15. else  0000 0001 0010 0011 0100 0101 0110 0111 16. nhiphan(i+1,n); 1000 1001 1010 1011 1100 1101 1110 1111 17. } 18. } 76 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
17. Liệt kê các dãy thập lục phân có độ dài n 1. char so[10];  Dãy thập lục phân gồm các 2. char so_hexa[16]={'0','1','2','3','4','5', phần tử là số thập lục phân 3. '6','7','8','9','A','B','C','D','E','F'}; 4. void in_hexa(int n) // In số hexa  Giá trị từ 0 đến F 5. {  Mảng so_hexa khai báo các 6. for (int i=1;i<=n;i++) chữ số thập lục phân (dòng 2-3) 7. printf("%c",so[i]);// In kiểu ký tự 8. printf(" ");  Thay số thành ký tự 9. }  hexa(1,2) 10. void hexa(int i, int n)  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 11. { 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20 21 22 23 24 25 26 27 12. for (int j=0;j<=15;j++) 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 13. { 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 60 61 14. so[i] = so_hexa[j];// Chọn chữ số j 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 15. if (i==n) // Đủ n số 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 16. in_hexa(n); AE AF B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE 17. else 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 18. hexa(i+1,n); E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF F0 F1 F2 19. } F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 20. } 77 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
18. Liệt kê các tập con k phần tử của dãy số từ 1 đến n (1≤k≤n)  Còn gọi là tổ hợp chập k của n phần tử 1. char so[10];  Các tập con không trùng nhau, không phân 2. void in(int k) biệt thứ tự, vị trí 3. { 4. for (int i=1;i<=k;i++)  {1,2,3} = {2,1,3} = {2,3,1} 5. printf("%d",so[i]);  Các phần tử được chọn từ so[i-1]+1 đến 6. printf(" "); n-k+i 7. }  i có giá trị từ 1 đến k 8. void tapcon(int i, int k, int n)  Phần tử cuối cùng, tức i = k, biến j chạy đến n 9. { 10. so[0] = 0;  Ví dụ ! 11. for (int j=so[i-1]+1;j<=n-k+i;j++)  tapcon(1,2,3) = = 3 ! ! 12. {  12 13 23 13. so[i] = j; 14. if (i==k)  tapcon(1,5,5) = 1 15. in(k);  12345 16. else  tapcon(1,3,6) = 20 17. tapcon(i+1,k,n);  123 124 125 126 134 135 136 145 146 156 234 18. } 235 236 245 246 256 345 346 356 456 19. } 78 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
19. Liệt kê các hoán vị  Liệt kê các hoán vị của các số 1. int so[10]; 2. bool kt[10]={1,1,1,1,1,1,1,1,1,1} từ 1 đến n 3. void hoanvi(int i, int n) 4. {  Các chữ số không được trùng 5. for (int j=1;j<=n;j++) nhau 6. if (kt[j]) // Số j chưa được dùng  Phải kiểm tra xem một số đã 7. { 8. so[i] = j; // Chọn j được chọn hay chưa? 9. if (i==n) // Đủ n số  Dùng mảng kiểu bool để đánh 10. in(n); dấu và bỏ đánh dấu một số 11. else 12. { được chọn hoặc bỏ chọn 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  hoanvi(1,3): 16. } 17. }  123 132 213 231 312 321 18. } 79 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
20. Chỉnh hợp chập k của n phần tử (1≤k≤n)  Lấy k phần tử trong số n phần tử, 1. int so[10]; mỗi cách sắp xếp là một chỉnh hợp 2. bool kt[10]={1,1,1,1,1,1,1,1,1,1}  Tổ hợp không phân biệt cách sắp 3. void chinhhop(int i, int k, int n) xếp. 4. {  Chỉnh hợp phân biệt vị trí, thứ tự, 5. for (int j=1;j<=n;j++) cách sắp xếp 6. if (kt[j]) // Số j chưa được dùng 7. {  Tương tự bài liệt kê hoán vị ở slide trước nhưng chỉ lấy k số trong n 8. so[i] = j; // Chọn j phần tử 9. if (i==k) // Đủ k số 10. in(k);  Bài trước hoán vị n phần tử 11. else 12. { ! 13. kt[j]=false; // Đánh dấu  chinhhop(1,2,3) = = 6 ! 14. chinhhop(i+1,k,n);  12 13 21 23 31 32 15. kt[j]=true; // Bỏ đánh dấu  chinhhop(1,3,3) = 6 16. }  123 132 213 231 312 321 17. }  Chính là hoanvi(1,3) 18. } 80 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
21. Bài toán xếp quân hậu  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 h[x]=y  Dùng giải thuật đệ quy quay lui lần lượt thử chọn h[1]=1 vị trí các cột trên từng hàng h[2]=5 h[3]=8  Khi một quân hậu được được đặt lên bàn cờ, các h[4]=6 vị trí liên quan theo chiều ngang, dọc, chéo cần h[5]=3 h[6]=7 được đánh dấu để tránh đặt quân cờ khác h[7]=2 h[8]=4 81 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
22. Bài toán xếp quân hậu (2)  Đá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; 82 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
23. Bài toán xếp quân hậu (3) 1. #include 1. void quan_hau(int x, int n) 2. void quan_hau(int, int); 2. { 3. void in_banco(int); 3. for(int y=1; y<=n; y++) 4. #define max 10 4. if(d[y]&&cl[x+y]&&cx[x-y+n]) 5. int h[max]; 5. { 6. bool d[max]; 6. hau[x] = y; 7. bool cl[2*max]; 7. if(x==n)in_banco(n); 8. bool cx[2*max]; 8. else 9. 9. { 10. int main() 10. d[y] = false; 11. { 11. cl[x+y] = false; 12. int i; 12. cx[x-y+n] = false; 13. for(i=0;i<max;i++) d[i]=true; 13. quan_hau(x+1,n); 14. for(i=0;i<2*max;i++) 14. d[y] = true; 15. { 15. cl[x+y] = true; 16. cl[i]=true;cx[i]=true; 16. cx[x-y+n] = true; 17. } 17. } 18. quan_hau(1,8); 18. } 19. } 19. } 83 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
24. Bài toán xếp quân hậu (4) 1. void#includein_banco 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. } 84 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
25. Trò chơi Sudoku  Điền các số từ 1 đến 9 vào bàn cờ 9 x 9, sao cho 3 x 3  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 85 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
26. Trò chơi Sudoku (2) 1. void sudoku(int banco[size][size],int x,int y) 2 x 2 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) 4 x 4 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. } 86 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
27. Trò chơi Sudoku (3) 1. #include 1. void in() 2. #define s 3 2. { 3. #define size s*s 3. int i,j; 4. int banco[size][size]; 4. printf("\n"); 5. bool kt(int k, int x, int y) 5. for(i=0; i<size; i++) 6. { 6. { 7. int i,j; 7. for(j=0;j<size;j++) 8. for(i=0; i<size; i++) 8. printf(" %d",banco[i][j]); 9. if(banco[x][i]==k 9. printf("\n"); 10. || banco[i][y]==k) 10. } 11. return 0; 11. getchar(); 12. x=x/s,y=y/s; 12. } 13. for(i=x*s; i<x*s+s; i++) 14. for(j=y*s; j<y*s+s; j++) 13. int main() 15. if(banco[i][j]==k) 14. { 16. return 0; 15. sudoku(banco,0,0); 17. return 1; 16. } 18. } 87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
28. Tháp Hà Nội  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) 88 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
29. Tháp Hà Nội (2)  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. } 89 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
30. Hết bài 3  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 90 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng