TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Cấu trúc dữ liệu và thuật toán
Nguyễn Khánh Phương
cuu duong than cong . co m
Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Nội dung khóa học
cuu duong than cong . co m
Chương 1. Các khái niệm cơ bản Chương 2. Các sơ đồ thuật toán Chương 3. Các cấu trúc dữ liệu cơ bản Chương 4. Cây Chương 5. Sắp xếp Chương 6. Tìm kiếm Chương 7. Đồ thị
2
CuuDuongThanCong.com https://fb.com/tailieudientucntt
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Chương 2. Các sơ đồ thuật toán
Nguyễn Khánh Phương
cuu duong than cong . co m
Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
4
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
5
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1. Khái niệm đệ qui
• Trong thực tế ta thường gặp những đối tượng bao gồm chính nó hoặc được định nghĩa dưới dạng của chính nó. Ta nói các đối tượng đó được xác định một cách đệ qui.
• Ví dụ:
– Điểm quân số
– Fractal
– Các hàm được định nghĩa đệ qui
– Tập hợp được định nghĩa đệ qui
– Định nghĩa đệ qui của cây
cuu duong than cong . co m
– ...
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Điểm quân
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Đệ qui: Fractals
fractals là ví dụ về hình ảnh được xây dựng một cách đệ qui (đối tượng lặp lại một cách đệ qui).
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hàm đệ qui (Recursive Functions)
Các hàm đệ qui được xác định phụ thuộc vào biến nguyên không âm n theo sơ đồ sau:
Bước cơ sở (Basic Step): Xác định giá trị của hàm tại n=0: f(0).
Bước đệ qui (Recursive Step): Cho giá trị của f(k), k ≤ n, đưa ra qui tắc tính giá trị của f(n+1).
Ví dụ 1:
n = 0
f(0) = 3,
n > 0
f(n+1) = 2f(n) + 3,
f(2) = 2 × 9 + 3 = 21, ...
Khi đó ta có: f(1) = 2 × 3 + 3 = 9,
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hàm đệ qui (Recursive Functions)
Ví dụ 2: Định nghĩa đệ qui của n!
f(0) = 1 f(n) = n * f(n-1)
Để tính giá trị của hàm đệ qui ta thay thế dần theo định nghĩa đệ qui để thu được biểu thức với đối số càng ngày càng nhỏ cho đến tận điều kiện đầu. Chẳng hạn:
đệ qui
5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1! = 5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120
int factorial(int n){
cuu duong than cong . co m
if (n==0)
điều kiện đầu
return 1;
else
return n*factorial(n-1);
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
n=2 Returns 2*factorial(1)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
n=2 Returns 2*factorial(1)
n=1 Returns 1*factorial(0)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
n=2 Returns 2*factorial(1)
n=1 Returns 1*factorial(0)
n=0 Returns 1
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
n=2 Returns 2*factorial(1)
n=1 Returns 1*factorial(0)
cuu duong than cong . co m
1
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
n=2 Returns 2*factorial(1)
1
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
n=3 Returns 3*factorial(2)
2
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
n=4 Returns 4*factorial(3)
6
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
factorial(4);
int factorial(int n){
if (n==0)
return 1;
factorial(4)
else
return n*factorial(n-1);
}
24
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương trình chạy theo thứ tự thế nào?
n=4 Returns 4*factorial(3)
Thực thi hàm factorial(4) sẽ dừng cho đến khi hàm factorial(3) trả về kết quả
cuu duong than cong . co m
n=3 Returns 3*factorial(2)
Khi hàm factorial(3) trả về kết quả, hàm factorial(4) tiếp tục được thực hiện
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Các hàm đệ quy đều có thể cài đặt lại bằng cách sử dụng vòng lặp while/for
• Chúng ta cũng có thể cài đặt tính n! bằng cách sử dụng vòng lặp while
int factorial (int n) {
int factorial(int n){
if (n==0)
return 1;
i=n; fact = 1; while(i >= 1) {
else
return n*factorial(n-1);
}
fact=fact*i; i--;
} return fact;
cuu duong than cong . co m
} Chú ý: Việc thay thế hàm đệ qui bởi hàm không đệ qui thường được gọi là việc khử đệ qui. Khử đệ qui không phải bao giờ cũng là dễ thực hiện như trong tình huống bài toán tính giai thừa.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 3
Viết hàm prod(list) trả về tích các số có trong danh sách list Ví dụ: prod({1,3,3,4}) = 36
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 3: Cài đặt hàm prod()
float prod(float[] list){
return helperProd(list, 0);
}
float helperProd(float[] list, int k){
if (k==list.size) return 1;
else
return list[k]*helperProd(list,k+1);
}
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 4. Fibonacci - Sự phát triển của bày thỏ Người nông dân nuôi một cặp thỏ mới sinh. Khi được 2 tháng tuổi, cứ mỗi cặp thỏ lại sinh ra một cặp thỏ khác sau mỗi tháng. Hỏi người nông dân đó có bao nhiêu con thỏ sau n tháng ?
n = 1: f1 = 1
Dãy Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...
n = 2: f2 = 1
n > 2: fn = fn-1 + fn-2
Công thức đúng cho n>2 vì mỗi cặp thỏ mới được sinh ra từ một cặp thỏ ít nhất 2 tháng tuổi
Month
>=2-month rabbits
1-month rabbits
Tổng fn
New-born rabbits
1
0
1
0
1
2
1
1
3
1
2
4
1 1 2 3
cuu duong than cong . co m
2
3
5
5
3
5
6
8
5
8
7
13
8
13
8
21
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 4. Fibonacci
Người nông dân nuôi một cặp thỏ mới sinh. Khi được 2 tháng tuổi, cứ mỗi cặp thỏ lại sinh ra một cặp thỏ khác sau mỗi tháng. Hỏi người nông dân đó có bao nhiêu con thỏ sau n tháng ?
cuu duong than cong . co m
n = 1: f1 = 1 n = 2: f2 = 1 n > 2: fn = fn-1 + fn-2
Công thức đúng cho n>2 vì mỗi cặp thỏ mới được sinh ra từ một cặp thỏ ít nhất 2 tháng tuổi
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 4. Fibonacci
Hàm đệ quy F(n) : • Giá trị đầu : F(n=0) =0; F(n=1) = 1 • Công thức đệ quy: F(n) = F(n-1) + F(n-2)
Cài đặt dùng vòng lặp
Cài đặt đệ quy int F(int n)
int F(int n)
if n < 2 then
return n;
if n < 2 then return n; else {
else
F(n-2)
F(n-1)
return F(n-1) + F(n-2);
F(n)
x= 0; y= 1; for k = 1 to n-1 { z = x+y;
cuu duong than cong . co m
x = y; y = z;
}
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
} return y; //y is F(n)
38
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hàm đệ qui (Recursive Functions)
n
Ví dụ 5: Định nghĩa đệ qui của tổng
s
a k
n
k
1
s1 = a1
sn = sn-1 + an
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 6. Tập hợp được xác định đệ qui (Recursively defined sets)
Tập hợp có thể xác định một cách đệ qui theo sơ đồ tương tự như hàm đệ qui:
Basis Step: định nghĩa tập cơ sở (chẳng hạn tập rỗng).
Recursive Step : Xác định qui tắc để sản sinh tập mới từ các tập đã có.
Ví dụ: Basis Step: 3 là phần tử của S. Recursive Step: nếu x thuộc S và y thuộc S thì x+y thuộc S. 3 S= {3} 3+3=6 S = {3, 6} 3+6 = 9 & 6+6=12 S = {3, 6, 9, 12} ...
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 7. Độ dài của xâu
• Định nghĩa đệ qui độ dài length(w) của xâu w *
– Basic step: length(l) = 0
– Recursive step: Nếu w* và x thì length(wx)= length(w)+1.
• Định nghĩa đệ qui của tập các xâu nhị phân độ dài chẵn.
– Basic step: lS (l là xâu rỗng)
– Recursive step: Nếu b S thì 0b0, 0b1, 1b0, 1b1 S .
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 8. Cây có gốc
Cây là cấu trúc dữ liệu quan trọng thường được dùng để tổ chức tìm kiếm và sắp xếp dữ liệu Cây có gốc (Rooted Trees): Cây có gốc bao gồm các nút, có một nút đặc biệt được gọi là gốc (root) và các cạnh nối các nút.
• Basic Step: Một nút là cây có gốc.
• Recursive Step: Giả sử T1,...,Tn,... là các cây với gốc là r1,....rn,...
Nếu ta tạo một gốc mới r và nối gốc này với mỗi một trong số các gốc r1,...rn,...
bởi một cạnh tương ứng, ta thu được một cây có gốc mới.
Step 2:
Basis step:
cuu duong than cong . co m
Step 1:
...
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định nghĩa đệ qui và Qui nạp
Định nghĩa đệ qui và Qui nạp toán học có những nét tương đồng và là bổ sung cho nhau:
•
Định nghĩa đệ qui thường giúp cho chứng minh bằng qui nạp các tính chất của các đối tượng được định nghĩa đệ qui.
•
Ngược lại, các chứng minh bằng qui nạp toán học thường là cơ sở để xây dựng các thuật toán đệ qui để giải quyết nhiều bài toán.
Chứng minh bằng qui nạp toán học thường bao gồm hai phần: 1. 2.
Bước cơ sở qui nạp – giống như bước cơ sở trong định nghĩa đệ qui Bước chuyển qui nạp – giống như bước đệ qui
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
44
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định nghĩa
• Thuật toán đệ qui là thuật toán tự gọi đến chính mình với đầu vào kích
thước nhỏ hơn.
• Việc phát triển thuật toán đệ qui là thuận tiện khi cần xử lý với các đối tượng được định nghĩa đệ qui (chẳng hạn: tập hợp, hàm, cây, ...trong các ví dụ nêu trong mục trước).
• Các thuật toán được phát triển dựa trên phương pháp chia để trị thông
thường được mô tả dưới dạng các thuật toán đệ qui (xem ví dụ mở đầu)
• Các ngôn ngữ lập trình cấp cao thường cho phép xây dựng các hàm (thủ tục) đệ qui, nghĩa là trong thân của hàm (thủ tục) có chứa những lệnh gọi đến chính nó. Vì thế, khi cài đặt các thuật toán đệ qui người ta thường xây dựng các hàm (thủ tục) đệ qui.
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cấu trúc của thuật toán đệ qui
Thuật toán RecAlg(input) {
if (kích thước của input là nhỏ nhất) then
Thực hiện Bước cơ sở; //giải bài toán kích thước đầu vào nhỏ nhất
else {
RecAlg(input với kích thước nhỏ hơn); // bước đệ qui // có thể có thêm những lệnh gọi đệ qui Tổng hợp lời giải của các bài toán con để thu được lời_giải; return (lời_giải) ;
}
} Thời gian tính:
T(n) = if (base case) then chi phí hằng số
else ( thời gian giải các bài toán con +
thời gian tổng hợp lời giải)
cuu duong than cong . co m
Kết quả thời gian tính phụ thuộc vào: – Số lượng bài toán con – Kích thước bài toán con – Thời gian tổng hợp lời giải các bài toán con
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
47
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cài đặt các thuật toán đệ qui
• Để cài đặt các thuật toán đệ qui trên các ngôn ngữ lập trình,
ta thường xây dựng các hàm (thủ tục) đệ qui.
• Trong mục này ta xét một số ví dụ minh hoạ cài đặt thuật
toán đệ qui:
– Hàm đệ qui tính n!
– Hàm đệ qui tính số Fibonacci
– Hàm đệ qui tính hệ số nhị thức
– Tìm kiếm nhị phân
– Bài toán tháp Hà nội
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 1: Tính hệ số nhị thức
• Hệ số nhị thức C(n,k) được định nghĩa đệ qui như sau:
C(n,0) = 1, C(n,n) =1; với mọi n >=0,
C(n,k) = C(n-1,k-1)+C(n-1,k), 0 < k < n
• Cài đặt hàm đệ qui trên C: int C(int n, int k){
if ((k==0)||(k==n)) return 1; else return C(n-1,k-1)+C(n-1,k);
cuu duong than cong . co m
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 2: Tìm kiếm nhị phân
Bài toán: Cho mảng số A[1..n] được sắp xếp theo thứ tự không giảm và số K. Cần tìm chỉ số i (1 i n) sao cho A[i] = K.
• Để đơn giản ta giả thiết rằng chỉ số như vậy là tồn tại. Thuật toán để giải bài toán được xây dựng dựa trên lập luận sau: Số K cho trước
– hoặc là bằng phần tử nằm ở vị trí ở giữa mảng A
– hoặc là nằm ở nửa bên trái (L) của mảng A
– hoặc là nằm ở nửa bên phải (R) của mảng A.
(Tình huống L (R) xảy ra chỉ khi K nhỏ hơn (lớn hơn) phần tử ở giữa của mảng A)
cuu duong than cong . co m
• Phân tích trên dẫn đến thuật toán sau đây:
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 2: Tìm kiếm nhị phân
int Bsearch(int low, int hight, int A[], int K) {
middle = (low + high)/2; if (A[middle] == K) return middle; else {
if (A[middle] > K)
return Bsearch(low, middle-1, A, K);
else
// A[middle] < K:
return Bsearch(middle+1, high, A, K)
}
}
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tìm kiếm nhị phân (xét cả trường hợp không tìm thấy)
int Bsearch(int low, int hight, int A[], int K) {
middle = (low + high)/2; if (low == high) { // Base step if (A[middle]== K) return middle; else return -1; //notFound
} if (A[middle] ==K) return middle; else if (A[middle] > K)
return Bsearch(low, middle-1, A, K);
else // A[middle] < K:
return Bsearch(middle+1, high, A, K);
}
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 3. Bài toán tháp Hà nội
Trò chơi Tháp Hà nội được trình bày như sau: “Có 3 cọc a, b, c. Trên cọc a có một chồng gồm n cái đĩa, đường kính giảm dần từ dưới lên trên. Cần phải chuyển chồng đĩa từ cọc a sang cọc c tuân thủ quy tắc:
1. Mỗi lần chỉ chuyển 1 đĩa
2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn.
Trong qu¸ trình chuyÓn ®ưîc phÐp dïng cäc b lµm cäc trung gian.
Bài toán đặt ra là: Tìm số lần di chuyển đĩa ít nhất cần thực hiện để hoàn thành nhiệm vụ đặt ra trong trò chơi Tháp Hà nội.
cuu duong than cong . co m
53
Cọc a
Cọc c
Cọc b
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tower of Hanoi: n=5
1. Mỗi lần chỉ chuyển 1 đĩa
2. Chỉ được xếp đĩa có đường kính nhỏ hơn lên trên đĩa có đường kính lớn hơn
cuu duong than cong . co m
Cọc a
Cọc c
Cọc b
54
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bài toán: chuyển n đĩa từ cọc a sang cọc c sử dụng cọc b làm trung gian
Cần tìm hn là sè lÇn di chuyÓn ®Üa Ýt nhÊt cÇn thùc hiÖn
hn = 2hn-1 + 1, n ≥ 2.
Việc di chuyển đĩa gồm 3 giai đoạn:
(1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian.
Bài toán kích thước n-1 Số lần di chuyển = hn-1
(2) ChuyÓn 1 ®Üa (®Üa víi ®ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c.
Số lần di chuyển = 1 (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian).
Bài toán kích thước n-1 Số lần di chuyển = hn-1
cuu duong than cong . co m
Cọc a
Cọc c
Cọc b
55
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tower of Hanoi: n=5
(1) ChuyÓn n-1 ®Üa tõ cäc a ®Õn cäc b sö dông cäc c lµm trung gian.
Bài toán kích thước n-1 Số lần di chuyển = hn-1
(2) ChuyÓn 1 ®Üa (®Üa víi ®ưêng kÝnh lín nhÊt) tõ cäc a ®Õn cäc c.
Số lần di chuyển = 1 (3) ChuyÓn n-1 ®Üa tõ cäc b ®Õn cäc c (sö dông cäc a lµm trung gian).
Bài toán kích thước n-1 Số lần di chuyển = hn-1
cuu duong than cong . co m
Cọc a
Cọc c
Cọc b
56
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Thuật toán tháp Hà nội
Thuật toán có thể mô tả trong thủ tục đệ qui sau đây: //chuyển n đĩa từ cọc a sang cọc c sử dụng cọc b làm trung gian: HanoiTower(n, a, b, c); {
if (n==1) then
HanoiTower(n-1,a,c,b); HanoiTower(1,a,b,c); HanoiTower(n-1,b,a,c);
}
cuu duong than cong . co m
}
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cài đặt
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 4: Palindrome
• Định nghĩa. Ta gọi palindrome là xâu mà đọc nó từ trái qua phải cũng
giống như đọc nó từ phải qua trái.
Ví dụ: NOON, DEED, RADAR, MADAM
Able was I ere I saw Elba
• Để nhận biết một xâu cho trước có phải là palindrome hay không: ta tiến
hành – So sánh kí tự đầu và kí tự cuối của xâu.
• Nếu bằng nhau: xâu mới = xâu cũ bỏ đi kí tự đầu và kí tự cuối. Lặp
lại bước so sánh.
• Nếu khác nhau: xâu đã cho không phải là palindrome
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 4: Palindrome: xau[start….end]
• Bước cơ sở (Base case) : xâu chỉ có 1 kí tự (start == end) return true if (xau[start] == xau[end])
• Bước đệ quy:
return true if (xau[start]==xau[end] &&
palindrome(xau, start+1, end-1))
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 5: Đường đi trên lưới ô
• Cho lưới ô kích thước D*C. • Bạn chỉ được phép đi từ nút này sang nút kia trên lưới theo hướng hoặc
xuống dưới hoặc sang phải.
• Hỏi có bao nhiêu đường đi từ nút (i, j) đến nút (D, C).
– Hàm: int CountPaths(int i, int j, int D, int C)
(0,C)
(0,0)
(i, j)
cuu duong than cong . co m
(D,C)
(D,0)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 5: Đường đi trên lưới ô
(0,C)
(0,0)
(i, j)
(D,C)
(D,0) • Để giải bài toán CountPaths(i,j, D, C)cần giải những bài toán con
cùng dạng nào ? – Từ ô (i, j) chỉ có 2 cách đi:
CountPaths(i+1,j, D, C)
cuu duong than cong . co m
CountPaths(i,j+1, D, C)
• Đi xuống dưới: đến ô (i+1, j) • Đi sang phải: đến ô (i, j+1)
CountPaths(i,j, D, C) = CountPaths(i+1,j, D, C)
+ CountPaths(i,j+1, D, C)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bước cơ sở
• Nếu bạn bước quá cạnh của lưới (không còn thuộc lưới), sẽ không tồn tại đường đi đến ô
(D, C): – if (i > D) OR (j > C): CountPaths(i,j, D, C)trả về giá trị 0
DONE ?
NO: vì khi đó kết quả của mọi bài toán con đều =0
cuu duong than cong . co m
Cần xét thêm 1 trường hợp đặc biệt nữa: đó là khi bạn đang ở ô (D,C) có 1 đường đi (đường đi này không cần bước bước nào)
63
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ 5: Đường đi trên lưới ô
• Cho lưới ô kích thước D*C. • Bạn chỉ được phép đi từ nút này sang nút kia trên lưới theo hướng hoặc
xuống dưới hoặc sang phải.
• Hỏi có bao nhiêu đường đi từ nút (i, j) đến nút (D, C).
– Hàm: int CountPaths(int i, int j, int D, int C)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
65
CuuDuongThanCong.com https://fb.com/tailieudientucntt
4. Phân tích thuật toán đệ qui
• Để phân tích thuật toán đệ qui ta thường tiến hành như sau:
– Gọi T(n) là thời gian tính của thuật toán
– Xây dựng công thức đệ qui cho T(n).
– Giải công thức đệ qui thu được để đưa ra đánh giá cho T(n)
• Nói chung ta chỉ cần một đánh giá sát cho tốc độ tăng của T(n) nên việc giải
công thức đệ qui đối với T(n) là đưa ra đánh giá tốc độ tăng của T(n) trong
ký hiệu tiệm cận
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ: Tìm kiếm nhị phân
int Bsearch(int low, int high, int A[],int K) {
mid = (low+high)/2; if (A[m] == K) return mid; else if (A[mid] > K)
return Bsearch(low,mid-1, A, K);
else
//A[mid] < K
return Bsearch(mid+1,high, A, K);
}
• Gọi T(n) là thời gian tính của việc thực hiện Bsearch(1, n, A, K), ta có
cuu duong than cong . co m
T(1) = c T(n) = T(n/2) + d trong đó c và d là các hằng số.
Giải công thức đệ quy trên, ta có T(n) = (log n).
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
68
CuuDuongThanCong.com https://fb.com/tailieudientucntt
5. Đệ qui có nhớ
• Trong phần trước ta đã thấy các thuật toán đệ qui để tính số
Fibonacci và tính hệ số nhị thức là kém hiệu quả.
• Để tăng hiệu quả của các thuật toán đệ qui mà không cần tiến hành xây dựng các thủ tục lặp hay khử đệ qui, ta có thể sử dụng kỹ thuật đệ qui có nhớ.
• Sử dụng kỹ thuật này,
trong nhiều trường hợp,
ta giữ nguyên được cấu trúc đệ qui của thuật toán và đồng thời lại đảm bảo được hiệu quả của nó. Nhược điểm lớn nhất của cách làm này là đòi hỏi về bộ nhớ.
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bài toán con trùng lặp
• Nhận thấy là trong các thuật toán đệ qui là mỗi khi cần đến lời giải của một bài toán con ta lại phải trị nó một cách đệ qui. Do đó, có những bài toán con bị giải đi giải lại nhiều lần. Điều đó dẫn đến tính kém hiệu quả của thuật toán. Hiện tượng này gọi là hiện tượng bài toán con trùng lặp.
Ví dụ: Thuật toán tính hệ số nhị thức C(5,3). Cây đệ qui thực hiện lệnh gọi hàm C(5,3) được chỉ ra trong hình sau đây
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ: Bài toán con trùng lặp trong việc tính C(5,3)
C(5,3)
C(4,2)
C(4,3)
C(3,2)
C(3,1)
C(3,2)
C(3,3)
C(2,1)
C(2,2)
C(2,1)
C(2,0)
C(2,1)
C(2,2)
cuu duong than cong . co m
C(1,0)
C(1,1)
C(1,0)
C(1,1)
C(1,0)
C(1,1)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ: Bài toán con trùng lặp khi tính Fibonaci F(4)
int F (int n) {
if n <2 then return n; else return F (n-1)+F(n-2);
}
F (4)
F (2)
F (3)
F(0)
F (1)
F (2)
F (1)
cuu duong than cong . co m
F (0)
F (1)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đệ qui có nhớ
• Để khắc phục hiện tượng này, ý tưởng của đệ qui có nhớ là: Ta sẽ dùng biến ghi nhớ lại thông tin về lời giải của các bài toán con ngay sau lần đầu tiên nó được giải. Điều đó cho phép rút ngắn thời gian tính của thuật toán, bởi vì, mỗi khi cần đến có thể tra cứu mà không phải giải lại những bài toán con đã được giải trước đó.
Ví dụ: Thuật toán đệ qui tính hệ số nhị thức, ta đưa vào biến • D[n][k] để ghi nhận những giá trị đã tính. • Đầu tiên D[n][k]=0, mỗi khi tính được C(n, k) giá trị này sẽ được ghi nhận vào D[n][k]. Như vậy, nếu D[n][k]>0 thì điều đó có nghĩa là không cần gọi đệ qui hàm C(n, k)
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ: Hàm tính C(n,k) có nhớ
int C(int n,int k){
if (D[n][k]>0) return D[n][k]; else{
D[n][k] = C(n-1,k-1)+C(n-1,k); return D[n][k];
}
}
Trước khi gọi hàm C(n, k) cần khởi tạo mảng D[ ][ ] như sau: • •
D[i][0] = 1, D[i][i]=1, với i = 0,1,..., n; D[i][j] = 0, với những i, j còn lại.
cuu duong than cong . co m
CuuDuongThanCong.com https://fb.com/tailieudientucntt
N i dung 1. Khái niệm đệ qui
2. Thuật toán đệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán đệ qui
5. Đệ qui có nhớ
6. Thuật toán quay lui
cuu duong than cong . co m
75
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Sơ đồ thuật toán quay lui
• Bài toán liệt kê (Q): Cho A1, A2,..., An là các tập hữu hạn. Ký hiệu A = A1 A2 ... An = { (a1, a2, ..., an): ai Ai , i=1, 2, ..., n}. Giả sử P là tính chất cho trên A. Vấn đề đặt ra là liệt kê tất cả các phần tử của A thoả mãn tính chất P:
D = { a = (a1, a2, ..., an) A: a thoả mãn tính chất P }. • Các phần tử của tập D được gọi là các lời giải chấp nhận được.
cuu duong than cong . co m
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Sơ đồ thuật toán quay lui
Tất cả các bài toán liệt kê tổ hợp cơ bản đều có thể phát biểu dưới dạng bài toán liệt kê (Q).
Ví dụ:
• Bài toán liệt kê xâu nhị phân độ dài n dẫn về việc liệt kê các phần tử
của tập
Bn = {(a1, ..., an): ai {0, 1}, i=1, 2, ..., n}.
• Bài toán liệt kê các tập con m phần tử của tập N = {1, 2, ..., n} đòi hỏi
liệt kê các phần tử của tập:
S(m,n) = {(a1,..., am)Nm: 1 ≤ a1 < ... < am ≤ n }.
cuu duong than cong . co m
• TËp c¸c ho¸n vÞ cña c¸c sè tù nhiªn 1, 2, ..., n lµ tËp
n = {(a1,..., an) Nn: ai ≠ aj ; i ≠ j }.
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Lời giải bộ phận
Lời giải của bài toán là bộ có thứ tự gồm n thành phần (a1, a2, ..., an), trong đó ai Ai , i = 1, 2, ..., n. Định nghĩa. Ta gọi lời giải bộ phận cấp k (0≤k≤ n) là bộ có thứ tự gồm k thành phần
(a1, a2, ..., ak), trong đó ai Ai , i = 1, 2, ..., k. • Khi k = 0, lời giải bộ phận cấp 0 được ký hiệu là ( ) và còn
được gọi là lời giải rỗng.
cuu duong than cong . co m
• Nếu k = n, ta có lời giải đầy đủ hay đơn giản là một lời giải
của bài toán.
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Sơ đồ thuật toán quay lui
Thuật toán quay lui được xây dựng dựa trên việc xây dựng dần từng thành phần của lời giải. • Thuật toán bắt đầu từ lời giải rỗng ( ). • Trên cơ sở tính chất P ta xác định được những phần tử nào của tập A1 có thể chọn vào vị trí thứ nhất của lời giải. Những phần tử như vậy ta sẽ gọi là những ứng cử viên (viết tắt là UCV) vào vị trí thứ nhất của lời giải. Ký hiệu tập các UCV vào vị trí thứ nhất của lời giải là S1. Lấy a1 S1, bổ sung nó vào lời giải rỗng đang có ta thu được lời giải bộ phận cấp 1: (a1).
cuu duong than cong . co m
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Sơ đồ thuật toán quay lui
• Bước tổng quát: Giả sử ta đang có lời giải bộ phận cấp k-1:
(a1, a2, ..., ak-1),
cần xây dựng lời giải bộ phận cấp k:
(a1, a2, ..., ak-1, ak)
– Trên cơ sở tính chất P, ta xác định được những phần tử nào của tập Ak có
thể chọn vào vị trí thứ k của lời giải.
– Những phần tử như vậy ta sẽ gọi là những ứng cử viên (viết tắt là UCV) vào vị trí thứ k của lời giải khi k-1 thành phần đầu của nó đã được chọn là (a1, a2, ..., ak-1). Ký hiệu tập các ứng cử viên này là Sk.
cuu duong than cong . co m
– Xét 2 tình huống:
• Sk ≠
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
• Sk =
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Sơ đồ thuật toán quay lui
• Sk ≠ : Lấy ak Sk bổ sung nó vào lời giải bộ phận cấp k-1 đang có (a1, a2, ...,
ak-1) ta thu được lời giải bộ phận cấp k (a1, a2, ..., ak-1, ak). Khi đó – Nếu k = n thì ta thu được một lời giải, – Nếu k < n, ta tiếp tục đi xây dựng thành phần thứ k+1 của lời giải.
• Sk=: Điều đó có nghĩa là lời giải bộ phận (a1, a2, ..., ak-1) không thể tiếp tục phát triển thành lời giải đầy đủ. Trong tình huống này ta quay trở lại tìm ứng cử viên mới vào vị trí thứ k-1 của lời giải (chú ý: ứng cử viên mới này nằm trong tập Sk-1) – Nếu tìm thấy UCV như vậy, thì bổ sung nó vào vị trí thứ k-1 rồi lại tiếp tục
đi xây dựng thành phần thứ k.
cuu duong than cong . co m
– Nếu không tìm được thì ta lại quay trở lại thêm một bước nữa tìm UCV mới vào vị trí thứ k-2, ... Nếu quay lại tận lời giải rỗng mà vẫn không tìm được UCV mới vào vị trí thứ 1, thì thuật toán kết thúc.
NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cây liệt kê lời giải theo thuật toán quay lui
Gốc (lời giải rỗng)
Tập UCV S1
a1
(a1)
Tập UCV S2 khi đã có (a1)
a2
(a1, a2)
Tập UCV S3 khi đã có (a1, a2)
(a1, a2, a3)
a3
cuu duong than cong . co m
Tập UCV S4 khi đã có (a1, a2 , a3)
a4
a’4
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Thuật toán quay lui (đệ qui)
Thuật toán quay lui (không đệ qui)
void Bactrack(int k) {
void Bactraking ( ) {
trí thứ k của lời giải>; k=1;
for y Sk //Với mỗi UCV y từ Sk
{ while (Sk ) { ak = y;
if (k == n) ak Sk; // Lấy ak từ Sk
if <(k == n) > then } } k = k+1;
} Lệnh gọi để thực hiện thuật toán quay lui là:
Bactrack(1); }
k = k - 1; // Quay lui } } • Nếu chỉ cần tìm một lời giải thì cần tìm cách
chấm dứt các thủ tục gọi đệ qui lồng nhau
sinh bởi lệnh gọi Backtrack(1) sau khi ghi
nhận được lời giải đầu tiên. Lệnh gọi để thực hiện thuật toán quay lui là:
Bactraking ( ); NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN • Nếu kết thúc thuật toán mà ta không thu
được một lời giải nào thì điều đó có nghĩa là
bài toán không có lời giải. CuuDuongThanCong.com https://fb.com/tailieudientucntt Hai vấn đề mấu chốt • Để cài đặt thuật toán quay lui giải các bài toán tổ hợp cụ thể ta cần giải quyết hai vấn đề cơ bản sau: – Tìm thuật toán xây dựng các tập UCV Sk
– Tìm cách mô tả các tập này để có thể cài đặt thao tác liệt kê
các phần tử của chúng (cài đặt vòng lặp qui ước for y Sk ). • Hiệu quả của thuật toán liệt kê phụ thuộc vào việc ta có xác định được chính xác các tập UCV này hay không. NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Chú ý • Thuật toán dễ dàng mở rộng cho bài toán liệt kê trong đó lời giải có
thể mô tả như là bộ (a1, a2, ..., an,...) độ dài hữu hạn, tuy nhiên giá trị
của độ dài là không biết trước và các lời giải cũng không nhất thiết
phải có cùng độ dài. Khi đó chỉ cần sửa lại câu lệnh
if (k == n) thành if <(a1, a2, ..., ak) là lời giải> Cần xây dựng hàm nhận biết (a1, a2, ..., ak) đã là lời giải hay chưa. NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Ví dụ 1: LiÖt kª x©u nhÞ ph©n ®é dµi n • Bài toán liệt kê xâu nhị phân độ dài n dẫn về việc liệt kê các phần tử của tập Bn = {(b1, ..., bn): bi {0, 1}, i=1, 2, ..., n}. • Ta xét cách giải quyết hai vấn đề cơ bản để cài đặt thuật toán quay lui:
– Xây dựng tập ứng cử viên Sk: Rõ ràng ta có S1 = {0, 1}. Giả sử đã
có xâu nhị phân cấp k-1 (b1, ..., bk-1), khi đó rõ ràng Sk = {0,1}.
Như vậy, tập các UCV vào các vị trí của lời giải đã được xác định.
– Cài đặt vòng lặp liệt kê các phần tử của Sk: ta có thể sử dụng vòng lặp for for (y=0;y<=1;y++) NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt C©y liÖt kª d·y nhÞ ph©n ®é dµi 3 Sk = {0,1} ( ) 0 1 (0) (1)
1 0 0 (00) (10) (11)
1 1 0 0 1
(01)
0 1 0 1 (000) (001) (010) (011) (100) (111) (101) (110) NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương trình trên C++ (Đệ qui) void Xau(int i){ int j;
for (j = 0; j<=1; j++) { #include void Ghinhan() { b[i] = j;
if (i==n) Ghinhan();
else Xau(i+1); } } int main() { int i, j;
count++;
cout<<"Xau thu " << count<<": ";
for (i=1 ; i<= n ;i++) { j=b[i];
cout< cout<<"Nhap n = ";cin>>n;
count = 0; Xau(1);
cout<<"So luong xau = "< } }
cout< } NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương trình trên C++ (không đệ qui) void Xau( ) { k=1; s[k]=0;
while (k > 0) { #include void Ghinhan() { while (s[k] <= 1) {
b[k]=s[k];
s[k]=s[k]+1;
if (k==n) Ghinhan();
else { k++;
s[k]=0; int i, j;
count++;
cout<<"Xau thu " << count<<":
";
for (i=1 ; i<= n ;i++) { } j=b[i];
cout< }
k--; // Quay lui } }
cout< } } NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương trình trên C++ (không đệ qui) int main() { cout<<"Nhap n = ";cin>>n;
count = 0; Xau();
cout<<"So luong xau = "< } NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Ví dụ 2. Liệt kê các m-tập con của n-tập Bài toán: Liệt kê các tập con m phần tử của tập N = {1, 2, ..., n}. Ví dụ: Liệt kê các tập con 3 phần tử của tập N = {1, 2, 3, 4, 5}
Giải: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5),
(2, 4, 5), (3, 4, 5) Bài toán dẫn về: Liệt kê các phần tử của tập:
S(m,n)={(a1,..., am)Nm: 1 ≤ a1<... NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Ví dụ 2. Liệt kê các m-tập con của n-tập Ta xét cách giải quyết 2 vấn đề cơ bản để cài đặt thuật toán quay lui:
• Xây dựng tập ứng cử viên Sk: S1 = {1, 2, ..., n-(m-1) }. – Từ điều kiện: 1 a1 < a2 < ... < am n
suy ra
– Giả sử có tập con (a1, ..., ak-1). Từ điều kiện ak-1 < ak < . . . < am ≤ n, ta suy ra:
Sk = {ak-1+1, ak-1+2, ..., n-(m-k)}.
• Cài đặt vòng lặp liệt kê các phần tử của Sk:
for (y=a[k-1]+1;y<=n-m+k;y++) ... NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương trình trên C++ (Đệ qui) void MSet(int i){ #include int j;
for (j = a[i-1] +1; j<= n-m+i; j++) { a[i] = j;
if (i==m) Ghinhan();
else MSet(i+1); int n, m, count;
int a[100];
void Ghinhan() { } }
int main() { int i;
count++;
cout<<"Tap con thu " < cout<<"Nhap n, m = "; cin>>n; cin>>m;
a[0]=0; count = 0; MSet(1);
cout<<"So tap con "< cout< } cout<<"Nhap n, m = "; cin>>n; cin>>m;
a[0]=0; count = 0; MSet();
cout<<"So tap con "< cout< } NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt int main() { void Hoanvi(int i)
{ int j;
for (j = 1; j<=n; j++) cout<<("Nhap n = "); cin>>n;
count = 0; Hoanvi(1);
cout<<"So hoan vi = " << count; } if (UCV(j,i))
{ a[i] = j; if (i==n) Ghinhan( );
else Hoanvi(i+1); } } NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Cây liệt kê hoán vị của 1, 2, 3 ( ) Hoanvi(1); S1 = ? 3 1 2 (1) (3) (2) S2 = ? 3 2 1 3 1 2 (2,1) (3,1) (1,2) (2,3) (3,2) 3 1 2 (1,3)
S3 = ?
2 3 1 (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) Sk = N \ { a1, a2, ..., ak-1} CuuDuongThanCong.com https://fb.com/tailieudientucntt Ví dụ 4. Bài toán xếp hậu • Liệt kê tất cả các cách xếp n quân Hậu trên bàn cờ nn sao
cho chúng không ăn được lẫn nhau, nghĩa là sao cho không
có hai con nào trong số chúng nằm trên cùng một dòng hay
một cột hay một đường chéo của bàn cờ. n cột CuuDuongThanCong.com https://fb.com/tailieudientucntt The n-Queens Problem Hai con hậu bất kỳ không được xếp
trên cùng một dòng ... CuuDuongThanCong.com https://fb.com/tailieudientucntt The n-Queens Problem Hai con hậu bất kỳ không được xếp
trên cùng một cột ... CuuDuongThanCong.com https://fb.com/tailieudientucntt The n-Queens Problem Hai con hậu bất kỳ không được
xếp trên cùng một dòng, một cột
hay một đường chéo! CuuDuongThanCong.com https://fb.com/tailieudientucntt Biểu diễn lời giải • Đánh số các cột và dòng của bàn cờ từ 1 đến n.
• Một cách xếp hậu có thể biểu diễn bởi bộ có n thành phần
(a1, a2 ,..., an), trong đó ai là toạ độ cột của con hậu ở dòng i. • Các điều kiện đặt ra đối với bộ (a1, a2 ,..., an): – ai aj , với mọi i j (nghĩa là hai con hậu ở hai dòng i và j không được nằm trên cùng một cột); – | ai – aj | | i – j |, với mọi i j (nghĩa là hai con hậu ở hai ô (i, ai) và (j, aj) không được nằm trên cùng một đường chéo). CuuDuongThanCong.com https://fb.com/tailieudientucntt Phát biểu bài toán • Như vậy bài toán xếp Hậu dẫn về bài toán liệt kê các phần tử của tập: D={(a1, a2, ..., an)Nn: ai ≠ aj và |ai – aj| ≠ |i – j|, i ≠ j } CuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán xếp hậu: Duyệt toàn bộ • Cần xếp N quân hậu lên bàn cờ có tất cả NxN ô, hỏi có tất cả bao nhiêu cách xếp ? – Quân thứ 1 có thể đặt vào 1 trong số N*N ô có N2 cách – Sau khi đặt quân thứ 1, tiến hành đặt quân thứ 2: bỏ qua ô đã đặt quân thứ 1 chỉ còn N2 – 1 ô có thể đặt quân thứ 2 có N2 – 1 cách – … ==> tổng cộng có tất cả (N2)! cách đặt. Với mỗi cách ta kiểm tra xem có
thỏa mãn điều kiện không có quân nào cùng dòng/cột/đường chéo; nếu
thỏa mãn thì thu được lời giải tương ứng. • Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N! CuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán xếp hậu: Duyệt toàn bộ • Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N! – Mỗi cách xếp N quân hậu lên bàn cờ sao cho không có quân nào cùng dòng, cùng cột ~ một hoán vị N phần tử Mảng a gồm 4 phần tử
a[1] =3; a[2] = 1; a[2] = 4; a[4] = 2
Dòng 1: xếp quân hậu ở cột 3
Dòng 2: xếp quân hậu ở cột 1
Dòng 3: xếp quân hậu ở cột 4
Dòng 4: xếp quân hậu ở cột 2 Hoán vị: (3, 1, 4, 2) – Chú ý: không phải hoán vị nào cũng là lời giải của bài toán xếp hậu: Thuật toán: Liệt kê tất cả N! hoán vị;
kiểm tra điều kiện không cùng đường
chéo tại mỗi hoán vị. Nếu hoán vị nào
thỏa mãn điều kiện cho ta 1 lời giải ? Làm thế nào để kiểm tra được điều kiện
Không cùng đường chéo Hoán vị: (3, 1, 4, 2)
=> lời giải Hoán vị: (3, 2, 1, 4)
=> Không phải là lời giải Vì còn phải kiểm tra điều kiện: không có quân hậu nào cùng đường chéo CuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán xếp hậu: Duyệt toàn bộ • Có một cách khác: giảm không gian xét duyệt từ (N2)! xuống còn N! – Kiểm tra hai quân hậu đặt ở ô (i1, j1) và ô (i2, j2) không thuộc cùng một đường chéo 8 7 |i1-i2| ≠ |j1-j2| 6 5 4 3 2 1 1 2 3 4 5 6 7 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán xếp hậu: Thuật toán quay lui Thuật toán: Xếp từng quân hậu lên lần lượt từng dòng của bàn cờ: tại bước lặp thứ
k (k=1,..,n): ta cần tìm tọa độ cột ak để đặt quân cờ lên dòng k [tức là đặt lên ô
(dòng k, cột ak)] • Giả sử đã xây dựng được lời giải bộ phận (a1, a2, …, ak-1): tức là đã xếp được (k-1) quân hậu lần lượt vào các ô (1, a1), (2, a2), …(k-1, ak-1) thỏa mãn điều kiện
đề bài. • Giờ tiếp tục xây dựng thành phần thứ k của lời giải: tức là cần tìm tọa độ cột để xếp quân hậu lên dòng thứ k của bàn cờ. Ta tiến hành như sau: – Duyệt lần lượt từng cột j =1,2,..,n: • Kiểm tra xem có thể xếp quân hậu lên ô (k, j) - dòng k cột j hay không: bằng cách dùng hàm nhận biết ứng cử viên UCVh(int j, int k) trả về giá trị 1 nếu xếp được; ngược lại hàm trả
về giá trị 0 UCVh nhận giá trị 1 khi và chỉ khi jSk CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán quay lui: Hàm nhận biết ứng cử viên int UCVh(int j, int k) //check xếp quân hậu vào ô (k, j) { // UCVh nhận giá trị 1 khi và chỉ khi j Sk
for (i=1; i if ((j == a[i]) || (fabs(j-a[i])== k-i)) return 0; return 1; } void Hau(int k) //tìm a[k]: cột xếp quân hậu thứ k lên dòng k { for (int j=1; j<=n; j++) //duyệt qua lần lượt từ cột 1..n: xem có xếp được lên ô (k, j) không if (UCVh(j,k)) //nếu xếp được quân hậu lên ô (k, j) { a[k]=j; if (k==n) Ghinhan(); //nếu đã xếp được đủ cả n quân hậu thì in ra lời giải else Hau(k+1); //nếu không thì tiếp tục tìm vị trí xếp quân hậu thứ k+1 lên dòng thứ k+1 } CuuDuongThanCong.com https://fb.com/tailieudientucntt 114 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chú ý • Rõ ràng là bài toán xếp hậu không phải là luôn có lời giải,
chẳng hạn bài toán không có lời giải khi n = 2, 3. Do đó
điều này cần được thông báo khi kết thúc thuật toán. CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào ROW 1, COL 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Xếp con hậu ở dòng 1
vào vị trí cột 1 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử xếp con hậu ở dòng 2
vào vị trí cột 1 ROW 2, COL 1 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử xếp con hậu ở dòng 2
vào vị trí cột 2 ROW 2, COL 2 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử xếp con hậu ở dòng 2
vào vị trí cột 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Chấp nhận xếp con hậu ở dòng 2
vào vị trí cột 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử xếp con hậu ở dòng 3
vào cột đầu tiên ROW 3, COL 1 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử cột tiếp theo ROW 3, COL 2 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử cột tiếp theo ROW 3, COL 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Thử cột tiếp theo ROW 3, COL 4 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào ...không có vị trí đặt
con hậu ở dòng 3. ROW 3, COL 4 ROW 2, COL 3 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Quay lại dịch
chuyển con hậu ở
dòng 2 ROW 2, COL 3 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Đẩy con hậu ở dòng
2 sang cột thứ 4. ROW 2, COL 4 ROW 1, COL 1 đã đặt 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt Thuật toán làm việc như thế nào Xếp được con hậu ở
dòng 2 ta tiếp tục xếp
con hậu ở dòng 3
. . . ROW 2, COL 4 ROW 1, COL 1 đã đặt 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Mét lêi gi¶i cña bµi to¸n xÕp hËu khi n = 8 CuuDuongThanCong.com https://fb.com/tailieudientucnttcuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
cuu duong than cong . co m
