NMLT_C19_KyThuatLapTrinhDeQuy_#REF

NHẬP MÔN LẬP TRÌNH
KỸ THUẬT LẬP TRÌNH
ĐỆ QUY

Nội dung
Kỹ thuật lập trình đệ quy
Bài toán
Cho S(n) = 1 + 2 + 3 + … + n
=>S(10)? S(11)?
Kỹ thuật lập trình đệ quy
1
+
2
+
…
+
10
1
+
2
+
…
+
10
=
55
+
11
=
66
1
+
2
+
…
+
10
=
=
S(10)
S(11)
1
+
2
+
…
+
10
S(10)
=
+
11
=
+
11
55
=
66
S(10)
+
11
55
+
11
2 bước giải bài toán
Kỹ thuật lập trình đệ quy
=
S(n)
+
n
S(n-1)
=
S(n-1)
+
n-1
S(n-2)
=
…
+
…
…
=
S(1)
+
1
S(0)
=
S(0)
0
Bước 1. Phân tích
Phân tích thành bài toán đồng dạng nhưng đơn giản hơn.
Dừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả.
Bước 2. Thế ngược
Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp  Kết quả cuối cùng.
Khái niệm đệ quy
Kỹ thuật lập trình đệ quy
Khái niệm
Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó.
Ví dụ
Tổng S(n) được tính thông qua tổng S(n-1).
2 điều kiện quan trọng
Tồn tại bước đệ quy.
Điều kiện dừng.
Đệ quy
Hàm đệ quy trong NNLT C
Khái niệm
Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp.
Kỹ thuật lập trình đệ quy
ĐQ trực tiếp
ĐQ gián tiếp
Cấu trúc hàm đệ quy
Kỹ thuật lập trình đệ quy
Phần dừng
(Base step)
Phần khởi tính toán hoặc điểm kết thúc của thuật toán
Không chứa phần đang được định nghĩa
Phần đệ quy
(Recursion step)
Có sử dụng thuật toán đang được định nghĩa.
Phân loại
Kỹ thuật lập trình đệ quy
TUYẾN TÍNH
NHỊ PHÂN
HỖ TƯƠNG
PHI TUYẾN
Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách tường minh.
Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh.
Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này.
Trong thân hàm có lời gọi hàm lại chính nó được đặt bên trong thân vòng lặp.
Đệ quy tuyến tính
Kỹ thuật lập trình đệ quy
Đệ quy nhị phân
Kỹ thuật lập trình đệ quy
Đệ quy hỗ tương
Kỹ thuật lập trình đệ quy
Đệ quy phi tuyến
Kỹ thuật lập trình đệ quy
Các bước xây dựng hàm đệ quy
Kỹ thuật lập trình đệ quy
Cơ chế gọi hàm và STACK
Kỹ thuật lập trình đệ quy
M
M
A
M
A
B
M
A
M
A
B
M
A
M
A
C
M
M
M
D
B
D
A
M
STACK
Thời gian
Nhận xét
Cơ chế gọi hàm dùng STACK trong C phù hợp cho giải thuật đệ quy vì:
Lưu thông tin trạng thái còn dở dang mỗi khi gọi đệ quy.
Thực hiện xong một lần gọi cần khôi phục thông tin trạng thái trước khi gọi.
Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên.
Kỹ thuật lập trình đệ quy
Ví dụ gọi hàm đệ quy
Tính số hạng thứ 4 của dãy Fibonacy
Kỹ thuật lập trình đệ quy
+
+
+
+
Một số lỗi thường gặp
Công thức đệ quy chưa đúng, không tìm được bài toán đồng dạng đơn giản hơn (không hội tụ) nên không giải quyết được vấn đề.
Không xác định các trường hợp suy biến – neo (điều kiện dừng).
Thông điệp thường gặp là StackOverflow do:
Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm tràn STACK.
Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện dừng.
Kỹ thuật lập trình đệ quy
Các vấn đề đệ quy thông dụng
Kỹ thuật lập trình đệ quy
Đệ quy??
1.Hệ thức truy hồi
Khái niệm
Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy.
Kỹ thuật lập trình đệ quy
A0
A1
…
An-1
An-2
An-1
An
Hàm truy hồi
A0
A1
…
An-1
An-2
An-1
An
An-2
Hàm truy hồi
1.Hệ thức truy hồi
Ví dụ 1
Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con?
Giải pháp
Gọi Vh là số vi trùng tại thời điểm h.
Ta có:
Vh = 2Vh-1
V0 = 2
 Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2
Kỹ thuật lập trình đệ quy
1.Hệ thức truy hồi
Ví dụ 2
Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu?
Giải pháp
Gọi Tn là số tiền có được sau n năm.
Ta có:
Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1
V(0) = 1000
 Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000
Kỹ thuật lập trình đệ quy
2.Chia để trị (divide & conquer)
Khái niệm
Chia bài toán thành nhiều bài toán con.
Giải quyết từng bài toán con.
Tổng hợp kết quả từng bài toán con để ra lời giải.
Kỹ thuật lập trình đệ quy
2.Chia để trị (divide & conquer)
Ví dụ 1
Cho dãy A đã sắp xếp thứ tự tăng. Tìm vị trí phần tử x trong dãy (nếu có)
Giải pháp
mid = (l + r) / 2;
Nếu A[mid] = x  trả về mid.
Ngược lại
Nếu x < A[mid]  tìm trong đoạn [l, mid – 1]
Ngược lại  tìm trong đoạn [mid + 1, r]
 Sử dụng đệ quy nhị phân.
Kỹ thuật lập trình đệ quy
2.Chia để trị (divide & conquer)
Ví dụ 2
Tính tích 2 chuỗi số cực lớn X và Y
Giải pháp
X = X2n-1…XnXn-1…X0, Y = Y2n-1…YnYn-1…Y0
Đặt XL=X2n-1…Xn, XN=Xn-1…X0  X=10nXL+XN
Đặt YL=Y2n-1…Yn, YN=Yn-1…Y0  Y=10nYL+YN
 X*Y = 102nXLYL + 10n(XLYL+XNYN)+XNYN
và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN
 Nhân 3 số nhỏ hơn (độ dài ½) đến khi có thể nhân được ngay.
Kỹ thuật lập trình đệ quy
2.Chia để trị (divide & conquer)
Một số bài toán khác
Bài toán tháp Hà Nội
Các giải thuật sắp xếp: QuickSort, MergeSort
Các giải thuật tìm kiếm trên cây nhị phân tìm kiếm, cây nhị phân nhiều nhánh tìm kiếm.
Lưu ý
Khi bài toán lớn được chia thành các bài toán nhỏ hơn mà những bài toán nhỏ hơn này không đơn giản nhiều so với bài toán gốc thì không nên dùng kỹ thuật chia để trị.
Kỹ thuật lập trình đệ quy
3.Lần ngược (Backtracking)
Khái niệm
Tại bước có nhiều lựa chọn, ta chọn thử 1 bước để đi tiếp.
Nếu không thành công thì “lần ngược” chọn bước khác.
Nếu đã thành công thì ghi nhận lời giải này đồng thời “lần ngược” để truy tìm lời giải mới.
Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã đi tuần.
Kỹ thuật lập trình đệ quy
3.Lần ngược (Backtracking)
Ví dụ
Tìm đường đi từ X đến Y.
Kỹ thuật lập trình đệ quy
X
B
Y
X
B
C
Y
Một số bài toán kinh điển
Kỹ thuật lập trình đệ quy
TÁM HẬU
…
THÁP HÀ NỘI
PHÁT SINH HOÁN VỊ
MÃ ĐI TUẦN
Tháp Hà Nội
Mô tả bài toán
Có 3 cột A, B và C và cột A hiện có N đĩa.
Tìm cách chuyển N đĩa từ cột A sang cột C sao cho:
Một lần chuyển 1 đĩa
Đĩa lớn hơn phải nằm dưới.
Có thể sử dụng các cột A, B, C làm cột trung gian.
Kỹ thuật lập trình đệ quy
Tháp Hà Nội
Kỹ thuật lập trình đệ quy
Cột nguồn A
Cột trung gian B
Cột đích C
1
…
N-1
N
N-1 đĩa A  B
N đĩa A  C
N-1 đĩa B  C
Đĩa N A  C
=
+
+
?
Tám hậu
Mô tả bài toán
Cho bàn cờ vua kích thước 8x8
Hãy đặt 8 hoàng hậu lên bàn cờ này sao cho không có hoàng hậu nào “ăn” nhau:
Không nằm trên cùng dòng, cùng cột
Không nằm trên cùng đường chéo xuôi, ngược.
Kỹ thuật lập trình đệ quy
Tám hậu – Các dòng
Kỹ thuật lập trình đệ quy
0
1
2
3
4
5
6
7
Tám hậu – Các cột
Kỹ thuật lập trình đệ quy
0
1
2
3
4
5
6
7
Tám hậu – Các đường chéo xuôi
Kỹ thuật lập trình đệ quy
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Tám hậu – Các đường chéo ngược
Kỹ thuật lập trình đệ quy
0
1
2
3
4
5
6
7
14
13
12
11
10
9
8
Tám hậu – Các dòng
Kỹ thuật lập trình đệ quy
j = 3
i = 2
j-i+n-1=8
j+i=5
Mã đi tuần
Mô tả bài toán
Cho bàn cờ vua kích thước 8x8 (64 ô)
Hãy đi con mã 64 nước sao cho mỗi ô chỉ đi qua 1 lần (xuất phát từ ô bất kỳ) theo luật:
Kỹ thuật lập trình đệ quy
4
7
3
8
5
6
2
1
Phân tích giải thuật đệ quy
Sử dụng cây đệ quy
(recursive tree)
Giúp hình dung bước phân tích và thế ngược.
Bước phân tích: đi từ trên xuống dưới.
Bước thế ngược đi từ trái sang phải, từ dưới lên trên.
Ý nghĩa
Chiều cao của cây  Độ lớn trong STACK.
Số nút  Số lời gọi hàm.
Kỹ thuật lập trình đệ quy
Nhận xét
Ưu điểm
Sáng sủa, dễ hiểu, nêu rõ bản chất vấn đề.
Tiết kiệm thời gian thực hiện mã nguồn.
Một số bài toán rất khó giải nếu không dùng đệ qui.
Khuyết điểm
Tốn nhiều bộ nhớ, thời gian thực thi lâu.
Một số tính toán có thể bị lặp lại nhiều lần.
Một số bài toán không có lời giải đệ quy.
Kỹ thuật lập trình đệ quy
Ví dụ cây đệ quy Fibonacy
Kỹ thuật lập trình đệ quy
Lặp lại
Khử đệ quy (tham khảo)
Khái niệm
Đưa các bài toán đệ quy về các bài toán không sử dụng đệ quy.
Thường sử dụng vòng lặp hoặc STACK tự tạo.
…
Kỹ thuật lập trình đệ quy
Tổng kết
Nhận xét
Chỉ nên dùng phương pháp đệ quy để giải các bài toán kinh điển như giải các vấn đề “chia để trị”, “lần ngược”.
Vấn đề đệ quy không nhất thiết phải giải bằng phương pháp đệ quy, có thể sử dụng phương pháp khác thay thế (khử đệ quy)
Tiện cho người lập trình nhưng không tối ưu khi chạy trên máy.
Bước đầu nên giải bằng đệ quy nhưng từng bước khử đệ quy để nâng cao hiệu quả.
Kỹ thuật lập trình đệ quy
Bài tập
Bài 1: Các bài tập trên mảng sử dụng đệ quy.
Bài 2: Viết hàm đệ quy xác định chiều dài chuỗi.
Bài 3: Hiển thị n dòng của tam giác Pascal.
a[i][0] = a[i][i] = 1
a[i][k] = a[i-1][k-1] + a[i-1][k]
Dòng 0: 1
Dòng 1: 1 1
Dòng 2: 1 2 1
Dòng 3: 1 3 3 1
Dòng 4: 1 4 6 4 1
…
Kỹ thuật lập trình đệ quy
Bài tập
Bài 4: Viết hàm đệ quy tính C(n, k) biết
C(n, k) = 1 nếu k = 0 hoặc k = n
C(n, k) = 0 nếu k > n
C(n ,k) = C(n-1, k) + C(n-1, k-1) nếu 0Bài 5: Đổi 1 số thập phân sang cơ số khác.
Bài 6: Tính các tổng truy hồi.
Bài 7: Bài toán “Tháp Hà Nội”.
Bài 8: Bài toán “8 hậu”.
Bài 9: Bài toán “Mã đi tuần”.
Kỹ thuật lập trình đệ quy