Tài liệu cấu trúc dữ liệu và giải thuật

Một số vấn đề cơ sở
của Tin học
Buổi 3:
Cấu trúc dữ liệu và thuật giải
Giáo viên: Tạ Thúc Nhu
Khoa CNTT trường ĐH Lạc Hồng
ĐỆ QUI
RECURVE
2 Mã hóa
Khái niệm Đệ Qui
Một đối tượng được gọi là đệ qui nếu nó hoặc 1 phần của nó
được định nghiã thông qua khái niệm về chính nó.
Ví dụ: Định nghiã phép toán giai thừa, ký hiệu: N!
• (a) Nếu N = 0, thì N! = 1
• (b) nếu N > 0 thì N! = N*(N-1)!
Ví dụ: Định nghiã UCLN của 2 số x và y, ký hiệu: UCLN(x, y)
• (a)UCLN(x,y) = x nếu y = 0
• (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y<>0
3 Mã hóa
Chương trình đệ qui
• Một chương trình là đệ qui nếu trong chương trình có lời
gọi đến chính nó.
Ví dụ: Định nghĩa hàm tính N! theo đệ qui.
int GiaiThua(int N)
{
if (N == 0) return 1;
return N * GiaiThua(N - 1);
}
4 Mã hóa
Một định nghiã đệ qui phải có 2 thành phần:
• Thành phần dừng: Không chứa khái niệm đang định nghiã
Ví dụ: N! = 1
• Thành phần đệ qui: có chứa khái niệm đang định nghiã
5 Mã hóa
Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide
• (a)UCLN(x,y) = x nếu y = 0
• (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y<>0
int UCLN(int x, int y)
{
if (y == 0) return x;
return UCLN(y, x % y);
}
6 Mã hóa
THUẬT GIẢI QUAY LUI
BACK TRACKING
7 Mã hóa
Tổng quan thuật giải Quay lui (Back Tracking)
• Dùng giải bài toán liệt kê các cấu hình
• Mỗi cấu hình được xác định bằng cách xây dựng tuần tự từng thành
phần trong cấu hình.
• Mỗi thành phần được xác định bằng cách chọn lựa dữ liệu trong tập khả
năng được đề xuất.
Cấu hình một lời giải X1 X2 X3 … Xn
Tập khả năng K1 K2 … … Km
8 Mã hóa
Mô hình thuật giải quay lui:
Xác định phần tử Xi bằng đệ quy
void Try( int i )
{
If (Xi là phần tử cuối cùng trong cấu hình)
< Thông báo cấu hình tìm được>;
else
for ( mọi Kj thuộc tập khả năng đề cử cho Xi)
[ if ( Chấp nhận Kj ) ]
{
Thử chọn Kj cho Xi;
Try( i+1); //Gọi đệ quy để xác định phần tử Xi+1
Bỏ ghi nhận Kj đã chọn cho Xi để chọn khả năng khác;
}
}
9 Mã hóa
Hai điểm mấu chốt quyết định độ phức tạp của bài toán là:
1. Xác định tập khả năng đề cử: Phụ thuộc vào việc phân tích
nhu cầu dữ liệu của từng thành phần trong cấu hình
2. Kiểm tra khả năng đề cử phải phù hợp với thành phần cần
xác định.
10 Mã hóa
Bài toán: Liệt kê các dãy nhị phân có độ dài n
Phân tích:
• Biểu diến cấu hình dãy nhị phân dưới dạng: X[1..n]
• Tập khả năng đề cử cho mỗi phần tử Xi là {0, 1}
• Thuật giải xác định phần tử Xi của dãy nhị phân như sau:
void Try(int i)
{
if ( i > n ) ;
else
for (int j =0; j<= 1; j++)
{
X[ i ] = j;
Try( i + 1 );
}
}
11 Mã hóa
Mã đi tuần: chỉ ra hành trình của quân Mã xuất phát
từ một ô trên bàn cờ đi qua tất cả các ô còn lại của
bàn cờ, mỗi ô đúng 1 lần.
Phân tích:
• Cấu hình lời giải là BC[1..n][1..n]
chứa số thứ tự hành trình của 2
(u, v)
quân Mã.
• Tập khả năng chứa các giá trị
dùng tính tọa độ các ô kế tiếp 1
(x, y)
dx[1..8] = {-2,-1, 1, 2, 2, 1, -1, -2}
dy[1..8] = { 1, 2, 2, 1, -1, -2, -2, -1}
• Điều kiện chọn khả năng cho
bước đi thứ i là Ô được chọn
phải :
– Thuộc bàn cờ
– Và chưa đi qua
12 Mã hóa
Thuật giải xác định bước đi thứ i của quân Mã
void Try(int i)
{ int j,u,v;
if (i > n*n) ;
else
for ( j =1; j <= 8 ; j++)
{
u =x+dx[j]; v = y+dy[j];
if (u >= 1 && u <= n && v >= 1 && v<=n && BC[u,v] = 0)
{
x = u; y = v;
BC[u,v] = i;
Try(i+1);
x = u-dx[j]; y = v-dy[j];
BC[u,v] = 0;
}
}
}
13 Mã hóa
Bài toán:
Liệt kê các hoán vị của dãy số {1, 2, .., n}
• Biểu diễn cấu hình một hoán vị: X[1..n]
• Tập khả năng đề cử: { 1, 2, .., n }
• Nhưng do Xi <> Xj với i <> j. Nên phải kiểm tra giá trị đề cử
cho Xi phải khác với các giá trị đã chọn cho các thành phần
trước đó.
Hướng giải quyết chung là tổ chức các biến trạng thái lưu
trữ thông tin phục vụ cho việc kiểm tra:
Dùng mảng F[1..n] để ghi nhớ tình trạng sử dụng của từng
khả năng trong tập S={1, 2, .., n}, với qui ước:
F[ j ] = 0 nếu j chưa sử dụng
F[ j ] = 1 nếu j đã sử dụng
14 Mã hóa
Thuật giải xác định phần tử Xi của một hoán vị
void Try(int i)
{ if ( i > n ) ;
else
for (int j = 1; j<= n; j++)
if (F[j] = 0)
{
X[i] = j;
F[j] = 1;
Try( i + 1 );
F[j] = 0;
}
}
15 Mã hóa
Ví dụ: Liệt kê các tập con k phần tử
của tập S = {1, 2, .., n}. Trong đó (k <= n)
• Biểu diễn cấu hình một tập con K phần tử: X[1..K]
• Tập khả năng đề cử: { 1, 2, .., n }
• Nhưng do Xi <> Xj với i <> j. Nên các giá trị đề cử cho Xi
phải khác với các giá trị đề cử cho các thành phần trước đó
Hướng giải quyết:
Dùng mảng F[1..N] để ghi nhớ tình trạng sử dụng của từng
khả năng trong tập S={1, 2, .., N}, với qui ước:
F[ j ] = 0 nếu j chưa sử dụng
F[ j ] = 1 nếu j đã sử dụng
16 Mã hóa
Thuật giải xác định phần tử Xi của một tập con
void Try(int i)
{ if ( i > K ) ;
else
for (int j = 1; j<= N; j++)
if (F[j] = 0)
{
X[i] = j;
F[j] = 1;
Try( i + 1 );
F[j] = 0;
}
}
17 Mã hóa
Một cách giải khác của bài toán tập con
Đưa ra điều kiện cho mỗi tập con là :
1 <= X[1] < X[2] < .. < X[ i ] < .. < X[K-1] < X[K] <= N
• Nhận xét:
X[K] <= N
X[K-1] <= X[K] - 1 <= N - 1
…
X[ i ] = X[K-(K-i)] <= N - (K - i)
• Do đó, ta có thể giới hạn giá trị đề cử cho thành phần X[i]
trong khoảng từ : X[i-1]+1 đến (N – K + i)
• Để điều này cũng đúng cho cả trường hợp i = 1, ta thêm vào
X[0] = 0.
18 Mã hóa
Thuật giải xác định phần tử Xi của một tập con
void Try(int i)
{
if ( i > K ) ;
else
for (int j = X[i-1]+1; j<= N-K+i; j++)
{
X[i] = j;
Try( i + 1 );
}
}
19 Mã hóa
KỸ THUẬT NHÁNH CẬN
20 Mã hóa