Bài giảng Kỹ thuật lập trình: Bài 3 - TS. Ngô Hữu Dũng
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (648.65 KB, 30 trang )
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
62
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.
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)
1. int S(int n)
2. {
Áp dụng vào lập trình:
if (n==1) return 1;
3.
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
Cách hoạt động
1. int S(int n)
Giả sử n = 5,
2. {
hàm đệ quy chạy như sau:
3.
if (n==1) return 1;
4.
else return S(n-1) +
S(5) = S(4) + 9 // Gọi hàm S(4)
S(4) = S(3) + 7 // Gọi hàm S(3) 5. }
// Gọi hàm S(2)
S(3) = S(2) + 5
// Gọi hàm S(1)
S(2) = S(1) + 3
S(1) = 1
// Return S(1)
S(2) = 1 + 3 // Return S(2)
// Return S(3)
S(3) = 1 + 3 + 5
// Return S(4)
S(4) = 1 + 3 + 5 + 7
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
(2*n–1);
Khái niệm đệ quy
Khái niệm
Thành phần
Phần cơ sở: Điều kiện thốt
Phần đệ quy: Có phép gọi lại chính nó
Ưu điể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
Thuận lợi trong việc giải những bài tốn có tính chất quy nạp
Làm gọn chương trình
Nhược điểm
65
Khơng tối ưu, tốn bộ nhớ
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)
Đệ quy nhị phân, đa đệ quy (Binary Recursion, Multiple 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)
Lời gọi đệ quy được thực hiện ở cuối hàm đệ quy
Đệ quy lồng (Nested 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)
Hàm đệ quy chỉ gọi lại chính nó một lần
Hai hàm đệ quy gọi lẫn nhau
Đệ quy quay lui (Backtracking)
66
Là hàm đệ quy có phép thử và sai
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Đệ quy tuyến tính
1.
Chỉ có một lời gọi đệ quy
Được dùng thơng dụng
Ví dụ
3.
4.
Tính giai thừa Fact(n) với n > 0
5.
Fact(n) = 1 * 2 * 3 *… * n
Phần cơ sở: Fact(1) = 1
Phần đệ quy: Fact(n)=n*Fact(n-1)
6.
2.
Tính T(n) = 1 + 2 + 3 + … + n
Phần cơ sở: T(1) = 1
Phần đệ quy: T(n) = T(n-1) + n
7.
1.
2.
3.
4.
5.
6.
7.
67
int Fact(int n)
{
if (n==1)
return 1;
else
return n * Fact(n-1);
}
int T(int n)
{
if (n==1)
return 1;
else
return T(n-1) + n;
}
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 tố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.
2.
3.
4.
Tính Fib(5) = ?
68
5.
= Fib(4)+Fib(3)
= Fib(3)+Fib(2) + Fib(2)+Fib(1)
= Fib(2)+Fib(1)+1+1+1
=5
6.
7.
int Fib(int n)
{
if (n==1 || n==2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(5)
1
1
2
3
5
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
Ví dụ: Tính hàm mystery
Hàm có hai lời gọi đệ quy
Hàm trả về kết quả ?
1.
2.
3.
4.
5.
Tính mystery(2,4) = ?
69
= mystery(4, 2)
= mystery(8, 1)
= mystery(16, 0) + 8 = 8
Vậy mystery(2,4) = ?
6.
7.
8.
9.
int mystery(int a, int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(a+a, b/2);
else
return mystery(a+a, b/2)+a;
}
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 *
1. int mystery(int a, int b)
Hàm trả về kết quả?
2. {
if (b == 0)
return 1;
if (b % 2 == 0)
return mystery(a*a, b/2);
else
return mystery(a*a, b/2)*a;
3.
Tính mystery(2,4) = ?
4.
= mystery(4,2)
= mystery(16,1)
= mystery(256,0)*16
= 16
5.
6.
7.
8.
9.
70
}
Vậy mystery(2,4) = ?
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngơ Hữu Dũng
Đệ quy đ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.
Tính Fib(5,1,1) = ?
71
= Fib(5,1,1)
= Fib(4,1,2)
= Fib(3,2,3)
= Fib(2,3,5)
= Fib(1,5,8)
=5
2.
3.
4.
5.
6.
7.
int Fib(int n, int x, int y)
{
if (n==1)
return x;
else
return Fib(n-1, y, x+y);
}
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(5)
1
1
2
3
5
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ụ
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.
2.
3.
4.
5.
6.
7.
8.
9.
72
=
+1
(
1,1)
1,
,
1 )
=0
>0 à =0
>0 à >0
int A(int m, int n)
{
if (m==0)
return n + 1;
if (m>0 && n==0)
return A(m-1, 1);
if (m>0 && n>0)
return A(m-1, A(m, n - 1));
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngơ Hữu Dũng
Đệ quy hỗ tương
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ẻ
1.
2.
3.
4.
5.
6.
7.
Ví dụ SoLe(5) = ?
73
= SoChan(4)
= SoLe(3)
= SoChan(2)
= SoLe(1)
= SoChan(0) = 1
bool SoLe(int n)
{
if (n==0)
return 0;
else
return SoChan(n-1);
}
8.
9.
10.
11.
12.
13.
14.
15.
bool SoChan(int n)
{
if (n==0)
return 1;
else
return SoLe(n-1);
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Đệ quy quay lui – thử và sai
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
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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
11.
12.
13.
14.
15.
16.
17.
18.
74
int so[10];
void in(int n) // In số
{
for (int i=1;i<=n;i++)
printf("%d",so[i]);
printf(" ");
}
void lietke(int i, int n)
{
for (int j=1;j<=n;j++)
{
so[i] = j; // Chọn số j
if (i==n)
// Đủ n số
in(n);
else
lietke(i+1,n);//next
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
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
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
1.
2.
3.
4.
5.
6.
7.
8.
lietke(1,2)
9.
so[1]=1
10.
so[1]=2
11.
12.
lietke(2,2)
lietke(2,2)
13.
14.
so[2]=1
so[2]=2
so[2]=1
so[2]=2
15.
16.
11
75
12
21
22
17.
18.
int so[10];
void in(int n) // In số
{
for (int i=1;i<=n;i++)
printf("%d",so[i]);
printf(" ");
}
void lietke(int i, int n)
{
for (int j=1;j<=n;j++)
{
so[i] = j; // Chọn số j
if (i==n)
// Đủ n số
in(n);
else
lietke(i+1,n);//next
}
}
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
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
Tương tự, nếu liệt kê dãy bát phân
Biến j chạy từ 0 đến 7
Biến j chạy từ 0 đến 15, tức từ 0 đến F (!?)
76
3.
4.
5.
6.
7.
8.
9.
11.
12.
13.
14.
nhiphan(1,4)
2.
10.
Tương tự, nếu liệt kê dãy thập lục phân
Bài trước, slide 74-75, biến j chạy từ 1 đến n
1.
15.
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
16.
17.
18.
int so[10];
void in(int n) // In số
{
for (int i=1;i<=n;i++)
printf("%d",so[i]);
printf(" ");
}
void nhiphan(int i, int n)
{
for (int j=0;j<=1;j++)
{
so[i] = j; // Chọn số j
if (i==n)
// Đủ n số
in(n);
else
nhiphan(i+1,n);
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Liệt kê các dãy thập lục phân có độ dài n
2.
3.
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)
1.
Dãy thập lục phân gồm các
phần tử là số thập lục phân
5.
6.
7.
8.
Thay số thành ký tự
9.
hexa(1,2)
4.
10.
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
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
77
char so[10];
char so_hexa[16]={'0','1','2','3','4','5',
'6','7','8','9','A','B','C','D','E','F'};
void in_hexa(int n) // In số hexa
{
for (int i=1;i<=n;i++)
printf("%c",so[i]);// In kiểu ký tự
printf(" ");
}
void hexa(int i, int n)
{
for (int j=0;j<=15;j++)
{
so[i] = so_hexa[j];// Chọn chữ số j
if (i==n)
// Đủ n số
in_hexa(n);
else
hexa(i+1,n);
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
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
biệt thứ tự, vị trí
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
tapcon(1,2,3)
78
=
!
!
!
=3
6.
7.
9.
11.
12.
13.
=1
14.
= 20
16.
15.
12345
tapcon(1,3,6)
5.
10.
12 13 23
tapcon(1,5,5)
3.
8.
Ví dụ
2.
4.
{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
1.
17.
123 124 125 126 134 135 136 145 146 156 234
235 236 245 246 256 345 346 356 456
18.
19.
char so[10];
void in(int k)
{
for (int i=1;i<=k;i++)
printf("%d",so[i]);
printf(" ");
}
void tapcon(int i, int k, int n)
{
so[0] = 0;
for (int j=so[i-1]+1;j<=n-k+i;j++)
{
so[i] = j;
if (i==k)
in(k);
else
tapcon(i+1,k,n);
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngơ Hữu Dũng
Liệt kê các hoán vị
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
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
hoanvi(1,3):
79
123 132 213 231 312 321
16.
17.
18.
int so[10];
bool kt[10]={1,1,1,1,1,1,1,1,1,1}
void hoanvi(int i, int n)
{
for (int j=1;j<=n;j++)
if (kt[j]) // Số j chưa được dùng
{
so[i] = j;
// Chọn j
if (i==n)
// Đủ n số
in(n);
else
{
kt[j]=false;
// Đánh dấu
hoanvi(i+1,n); // Tìm số tiếp
kt[j]=true;
// Bỏ đánh dấu
}
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngơ Hữu Dũng
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
3.
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ử
7.
Bài trước hốn vị n phần tử
chinhhop(1,2,3)
2.
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
1.
12 13 21 23 31 32
chinhhop(1,3,3)
80
=
4.
5.
6.
8.
9.
10.
11.
12.
!
!
=6
13.
14.
15.
=6
123 132 213 231 312 321
Chính là hoanvi(1,3)
16.
17.
18.
int so[10];
bool kt[10]={1,1,1,1,1,1,1,1,1,1}
void chinhhop(int i, int k, int n)
{
for (int j=1;j<=n;j++)
if (kt[j]) // Số j chưa được dùng
{
so[i] = j;
// Chọn j
if (i==k)
// Đủ k số
in(k);
else
{
kt[j]=false;
// Đánh dấu
chinhhop(i+1,k,n);
kt[j]=true;
// Bỏ đánh dấu
}
}
}
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
Bài tốn xếp qn hậu
Tìm các cách xếp n qn hậu trên bàn cờ n x n sao
cho các quân cờ khơng ăn được nhau
Lưu vị trí các qn hậu trên bàn cờ (x,y)
Quân hậu có thể ăn ngang, dọc, chéo
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
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
Chéo xuống: 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
(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)
82
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;
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.
2.
3.
4.
5.
6.
7.
8.
#include <stdio.h>
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];
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
83
9.
int main()
{
int i;
for(i=0;i
{
cl[i]=true;cx[i]=true;
}
quan_hau(1,8);
}
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
void quan_hau(int x, int n)
{
for(int y=1; y<=n; y++)
if(d[y]&&cl[x+y]&&cx[x-y+n])
{
hau[x] = y;
if(x==n)in_banco(n);
else
{
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;
}
}
}
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.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
84
#include
<stdio.h>n)
void
in_banco(int
{
int i,j,k;
for(k=1;k<=n;k++) printf("+----");
printf("+\n");
for(i=1; i<=n; i++)
{
printf("| ");
for(j=1;j<=n;j++)
if(j==h[i])
printf("%c%c | ",219,219);
else
printf("
| ");
printf("\n");
for(k=1;k<=n;k++) printf("+----");
printf("+\n");
}
getchar();
}
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
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 tốn tương tự với các kích cỡ khác
85
3x3
2x2=4
4 x 4 =16
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
