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
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
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)
Áp dụng vào lập trình:
1. int S(int n) 2. { 3.
if (n==1) return 1; else return S(n-1) + (2*n – 1);
4. 5. }
63 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
1. int S(int n) 2. { 3.
if (n==1) return 1; else return S(n-1) + (2*n–1);
Cách hoạt động Giả sử n = 5, hàm đệ quy chạy như sau: S(5) = S(4) + 9 // Gọi hàm S(4)
4. 5. }
S(4) = S(3) + 7 // Gọi hàm S(3)
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
// Return S(1)
S(2) = S(1) + 3 S(1) = 1
S(2) = 1 + 3 // Return S(2) // Return S(3)
S(3) = 1 + 3 + 5
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
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
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
Đệ quy tuyến tính
1. int Fact(int n) 2. { 3.
if (n==1)
4.
return 1;
Chỉ có một lời gọi đệ quy Được dùng thông dụng Ví dụ
5.
else
Tính giai thừa Fact(n) với n > 0
return n * Fact(n-1);
6. 7. }
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
1. int T(int n) 2. { 3.
if (n==1)
4.
return 1;
Phần cơ sở: T(1) = 1 Phần đệ quy: T(n) = T(n-1) + n
5.
else
return T(n-1) + n;
6. 7. }
67 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ 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 Fib(n) = Fib(n-1) + Fib(n-2)
1. int Fib(int n) 2. { 3.
if (n==1 || n==2)
4.
return 1;
5.
else
return Fib(n-1)+Fib(n-2);
6. 7. }
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(5)
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
1
2
3
5
68 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ 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) 2. {
3.
if (b == 0)
Ví dụ: Tính hàm mystery Hàm có hai lời gọi đệ quy 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);
7.
else
8.
return mystery(a+a, b/2)+a;
9. }
= mystery(4, 2) = mystery(8, 1) = mystery(16, 0) + 8 = 8 Vậy mystery(2,4) = ?
69 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ quy nhiều lần (tt)
Thay dòng số 4 thành return 1;
và thay dấu + bằng dấu *
Hàm trả về kết quả?
1. int mystery(int a, int b) 2. {
3.
if (b == 0)
4.
return 1;
Tính mystery(2,4) = ?
5.
if (b % 2 == 0)
6.
return mystery(a*a, b/2);
7.
else
8.
return mystery(a*a, b/2)*a;
= mystery(4,2) = mystery(16,1) = mystery(256,0)*16 = 16
9. }
Vậy mystery(2,4) = ?
70 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ 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
Tính Fib(5,1,1) = ?
1. int Fib(int n, int x, int y) 2. { 3.
if (n==1)
4.
return x;
5.
else
return Fib(n-1, y, x+y);
6. 7. }
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(5)
= Fib(5,1,1) = Fib(4,1,2) = Fib(3,2,3) = Fib(2,3,5) = Fib(1,5,8) = 5
1
1
2
3
5
71 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ quy lồng
Lời gọi đệ quy là tham số của một lời gọi đệ quy Ví dụ
, =
+ 1 ( 1,1) ( 1, ,
1 )
= 0 > 0 à = 0 > 0 à > 0
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)
return A(m-1, A(m, n - 1));
8. 9. }
72 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ quy hỗ tương
1. bool SoLe(int n) 2. { 3.
if (n==0)
4.
return 0;
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ụ
5.
else
Tìm số n là chẵn hay lẻ
return SoChan(n-1);
Ví dụ SoLe(5) = ?
6. 7. } 8. 9. bool SoChan(int n) 10. { 11.
if (n==0)
12.
return 1;
13.
else
return SoLe(n-1);
14. 15. }
= SoChan(4) = SoLe(3) = SoChan(2) = SoLe(1) = SoChan(0) = 1
73 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Đệ quy quay lui – thử và sai
1.
Liệt kê các kết quả thỏa mãn những điều
2.
kiện ràng buộc nào đó
3.
int so[10]; void in(int n) // In số {
4.
5.
for (int i=1;i<=n;i++) printf("%d",so[i]);
6.
printf(" ");
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
7.
cách thử tất cả các khả năng
8.
9.
} void lietke(int i, int n) {
10.
11.
for (int j=1;j<=n;j++) {
12.
13.
so[i] = j; // Chọn số j if (i==n) // Đủ n số
14.
in(n);
15.
else
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
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
1.
2.
Cách hoạt động 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
3.
int so[10]; void in(int n) // In số {
số thứ hai
4.
Cứ như vậy cho đến khi tìm được n số thì
5.
for (int i=1;i<=n;i++) printf("%d",so[i]);
xuất kết quả ra màn hình
6.
printf(" ");
7.
8.
lietke(1,2)
9.
} void lietke(int i, int n) {
10.
so[1]=1
so[1]=2
11.
for (int j=1;j<=n;j++) {
12.
13.
lietke(2,2)
lietke(2,2)
so[i] = j; // Chọn số j if (i==n) // Đủ n số
14.
in(n);
so[2]=2
so[2]=1
so[2]=2
so[2]=1
15.
else
16.
lietke(i+1,n);//next
}
11
12
21
22
17. 18. }
75 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Liệt kê các dãy nhị phân có độ dài n
1.
Dãy nhị phân gồm các phần tử là số nhị
2.
3.
int so[10]; void in(int n) // In số {
4.
5.
for (int i=1;i<=n;i++) printf("%d",so[i]);
phân Có giá trị 0 hoặc 1 Ở dòng 10, biến j chạy từ 0 đến 1
6.
printf(" ");
7.
Bài trước, slide 74-75, biến j chạy từ 1 đến n
8.
Tương tự, nếu liệt kê dãy bát phân
9.
} void nhiphan(int i, int n) {
10.
Biến j chạy từ 0 đến 7
11.
for (int j=0;j<=1;j++) {
12.
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 (!?)
13.
so[i] = j; // Chọn số j if (i==n) // Đủ n số
14.
in(n);
nhiphan(1,4)
15.
else
16.
nhiphan(i+1,n);
}
0000 0001 0010 0011 0100 0101 0110 0111 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
1.
2.
3.
4.
5.
6.
for (int i=1;i<=n;i++)
Liệt kê các dãy thập lục phân có độ dài n char so[10]; Dãy thập lục phân gồm các char so_hexa[16]={'0','1','2','3','4','5', phần tử là số thập lục phân '6','7','8','9','A','B','C','D','E','F'}; void in_hexa(int n) // In số hexa Giá trị từ 0 đến F { Mảng so_hexa khai báo các
7.
printf("%c",so[i]);// In kiểu ký tự
8.
printf(" ");
chữ số thập lục phân (dòng 2-3) Thay số thành ký tự
}
hexa(1,2)
9. 10. void hexa(int i, int n) 11. { 12.
13.
for (int j=0;j<=15;j++) {
14.
15.
so[i] = so_hexa[j];// Chọn chữ số j if (i==n)
// Đủ n số
16.
in_hexa(n);
17.
else
18.
hexa(i+1,n);
}
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
19. 20. }
77 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
1.
2.
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ử Các tập con không trùng nhau, không phân
3.
char so[10]; void in(int k) {
4.
biệt thứ tự, vị trí {1,2,3} = {2,1,3} = {2,3,1}…
5.
for (int i=1;i<=k;i++) printf("%d",so[i]);
Các phần tử được chọn từ so[i-1]+1 đến
6.
printf(" ");
7.
8.
n-k+i i có giá trị từ 1 đến k
9.
} 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
10.
Ví dụ
11.
tapcon(1,2,3)
=
= 3
12.
so[0] = 0; for (int j=so[i-1]+1;j<=n-k+i;j++) {
! ! !
13.
14.
so[i] = j; if (i==k)
= 1
15.
in(k);
16.
else
12 13 23 tapcon(1,5,5) 12345 tapcon(1,3,6)
= 20
17.
tapcon(i+1,k,n);
123 124 125 126 134 135 136 145 146 156 234
}
235 236 245 246 256 345 346 356 456
18. 19. }
78 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Liệt kê các hoán vị
1.
Liệt kê các hoán vị của các số
2.
3.
4.
int so[10]; bool kt[10]={1,1,1,1,1,1,1,1,1,1} void hoanvi(int i, int n) {
từ 1 đến n Các chữ số không được trùng
5.
for (int j=1;j<=n;j++)
nhau
6.
7.
if (kt[j]) // Số j chưa được dùng {
Phải kiểm tra xem một số đã
8.
được chọn hay chưa?
9.
// Chọn j // Đủ n số
so[i] = j; if (i==n)
10.
in(n);
11.
12.
else {
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
13.
14.
15.
kt[j]=false; // Đánh dấu hoanvi(i+1,n); // Tìm số tiếp kt[j]=true; // Bỏ đánh dấu
16.
}
hoanvi(1,3):
}
123 132 213 231 312 321
17. 18. }
79 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
1.
2.
3.
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ử, 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
4.
int so[10]; bool kt[10]={1,1,1,1,1,1,1,1,1,1} void chinhhop(int i, int k, int n) {
xếp.
5.
for (int j=1;j<=n;j++)
Chỉnh hợp phân biệt vị trí, thứ tự,
6.
cách sắp xếp
7.
if (kt[j]) // Số j chưa được dùng {
8.
9.
// Chọn j // Đủ k số
so[i] = j; if (i==k)
10.
in(k);
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ử
11.
12.
else {
13.
=
= 6
! !
14.
15.
kt[j]=false; // Đánh dấu chinhhop(i+1,k,n); kt[j]=true; // Bỏ đánh dấu
16.
}
= 6
chinhhop(1,2,3) 12 13 21 23 31 32 chinhhop(1,3,3)
}
17. 18. }
123 132 213 231 312 321 Chính là hoanvi(1,3)
80 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
h[2]=5
vị trí các cột trên từng hàng
h[3]=8
h[4]=6
h[5]=3
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[6]=7
h[7]=2
h[8]=4
81 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Bài toán xếp quân hậu (3)
1.
1.
2.
2.
void quan_hau(int x, int n) {
3.
3.
for(int y=1; y<=n; y++)
4.
4.
5.
5.
if(d[y]&&cl[x+y]&&cx[x-y+n]) {
6.
6.
7.
7.
8.
8.
#include
void quan_hau(int, int);
void in_banco(int);
#define max 10
int h[max];
bool d[max];
bool cl[2*max];
bool cx[2*max];
9.
hau[x] = y; if(x==n)in_banco(n); else {
10.
11.
9. 10. int main() 11. { 12.
12.
13.
13.
14.
14.
15.
15.
int i;
for(i=0;i
16.
16.
cl[i]=true;cx[i]=true;
d[y] = false;
cl[x+y] = false;
cx[x-y+n] = false;
quan_hau(x+1,n);
d[y] = true;
cl[x+y] = true;
cx[x-y+n] = true;
17.
17.
}
}
quan_hau(1,8);
}
18.
19. }
18.
19. }
83 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Bài toán xếp quân hậu (4)
1.
1.
2.
#include
void in_banco(int n)
{
3.
4.
5.
6.
7.
int i,j,k;
for(k=1;k<=n;k++) printf("+----");
printf("+\n");
for(i=1; i<=n; i++)
{
8.
9.
printf("| ");
for(j=1;j<=n;j++)
10.
if(j==h[i])
11.
printf("%c%c | ",219,219);
12.
else
13.
printf(" | ");
14.
15.
16.
printf("\n");
for(k=1;k<=n;k++) printf("+----");
printf("+\n");
17.
}
getchar();
18.
19. }
84 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Trò chơi Sudoku (2)
1.
2 x 2
2.
void sudoku(int banco[size][size],int x,int y)
{
3.
4.
int i;
for(i=1; i<=size; i++)
5.
6.
if(kt(i,x,y))
{
7.
8.
banco[x][y]=i;
if(y
4 x 4
9.
sudoku(banco,x,y+1);
10.
else
11.
if(x
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
Trò chơi Sudoku (3)
1.
1.
2.
2.
void in()
{
3.
3.
4.
4.
5.
5.
6.
#include
#define s 3
#define size s*s
int banco[size][size];
bool kt(int k, int x, int y)
{
6.
int i,j;
printf("\n");
for(i=0; i
7.
7.
for(j=0;j
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
16.
16.
cl[i]=true;cx[i]=true;
d[y] = false; cl[x+y] = false; cx[x-y+n] = false; quan_hau(x+1,n); d[y] = true; cl[x+y] = true; cx[x-y+n] = true;
17.
17.
}
} quan_hau(1,8);
}
18. 19. }
18. 19. }
83 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
Bài toán xếp quân hậu (4)
1. 1.
2.
#include
void in_banco(int n)
{
3.
4.
5.
6.
7.
int i,j,k; for(k=1;k<=n;k++) printf("+----"); printf("+\n"); for(i=1; i<=n; i++) {
8.
9.
printf("| "); for(j=1;j<=n;j++)
10.
if(j==h[i])
11.
printf("%c%c | ",219,219);
12.
else
13.
printf(" | ");
14.
15.
16.
printf("\n"); for(k=1;k<=n;k++) printf("+----"); printf("+\n");
17.
} getchar();
18. 19. }
84 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Trò chơi Sudoku (2)
1.
2 x 2
2.
void sudoku(int banco[size][size],int x,int y) {
3.
4.
int i; for(i=1; i<=size; i++)
5.
6.
if(kt(i,x,y)) {
7.
8.
banco[x][y]=i;
if(y
4 x 4
9.
sudoku(banco,x,y+1);
10.
else
11.
if(x
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
Trò chơi Sudoku (3)
1.
1.
2.
2.
void in()
{
3.
3.
4.
4.
5.
5.
6.
#include
#define s 3
#define size s*s
int banco[size][size];
bool kt(int k, int x, int y)
{
6.
int i,j;
printf("\n");
for(i=0; i
7.
7.
for(j=0;j
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
4 x 4
9.
sudoku(banco,x,y+1);
10.
else
11.
if(x
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
Trò chơi Sudoku (3)
1.
1.
2.
2.
void in()
{
3.
3.
4.
4.
5.
5.
6.
#include
#define s 3
#define size s*s
int banco[size][size];
bool kt(int k, int x, int y)
{
6.
int i,j;
printf("\n");
for(i=0; i
7.
7.
for(j=0;j
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
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
Trò chơi Sudoku (3)
1.
1.
2.
2.
void in() {
3.
3.
4.
4.
5.
5.
6.
#include
#define s 3
#define size s*s
int banco[size][size];
bool kt(int k, int x, int y)
{
6.
int i,j;
printf("\n");
for(i=0; i
7.
7.
for(j=0;j
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
7.
7.
for(j=0;j
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
8.
8.
printf(" %d",banco[i][j]);
9.
int i,j;
for(i=0; i
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k)
return 0;
}
getchar();
12.
11.
12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
9.
printf("\n");
10.
10.
11.
|| banco[i][y]==k) return 0;
} getchar();
12.
11. 12. }
13.
x=x/s,y=y/s;
for(i=x*s; i
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
14.
for(j=y*s; j
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main()
14. {
15.
16. }
17.
18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa)
2. {
3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa);
else
{
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai);
chuyen(toaMot, toaBa);
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
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
15.
if(banco[i][j]==k)
16.
return 0;
sudoku(banco,0,0);
return 1;
13. int main() 14. { 15. 16. }
17. 18. }
87 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng
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
Tháp Hà Nội (2)
1. void chuyendia(int sodia, int toaMot, int toaHai, int toaBa) 2. { 3.
4.
5.
if (sodia==1)chuyen(toaMot, toaBa); else {
6.
7.
8.
chuyendia(sodia-1,toaMot,toaBa,toaHai); chuyen(toaMot, toaBa); 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
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
![Bài tập Lập trình C++: Tổng hợp [kinh nghiệm/mới nhất/chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250826/signuptrendienthoai@gmail.com/135x160/45781756259145.jpg)
