Download miễn phí Bài giảng Nhập môn lập trình - Kỹ thuật lập trình đệ quy
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Trường Đại học Khoa học Tự nhiênKhoa Công nghệ thông tin
Bộ môn Tin học cơ sở
1
Đặng Bình Phương
[email protected]
NHẬP MÔN LẬP TRÌNH
KỸ THUẬT LẬP TRÌNH
ĐỆ QUY
VC
&
BB
2
Nội dung
Kỹ thuật lập trình đệ quy
T ng quan v ổ ề đệ quy1
Các v n ấ đề đệ quy thông d ngụ2
Phân tích gi i thu t & kh ả ậ ử đệ
quy
3
Các bài toán kinh đi nể4
VC
&
BB
3
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
=
=
S(10)
S(11)
S(10)= + 11
= + 1155 = 66
VC
&
BB
4
2 bước giải bài toán
Kỹ thuật lập trình đệ quy
=S(n) + nS(n1)
=S(n1) + n1S(n2)
=… + ……
=S(1) + 1S(0)
=S(0) 0
Bước 1. Phân tích
hân tích thành bài toán đồng
dạng nhưng đơn giản hơn.
ừ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
á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.
VC
&
BB
5
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(n1).
2 điều kiện quan trọng
Tồn tại bước đệ quy.
Điều kiện dừng.
VC
&
BB
6
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
… Hàm(…)
{
…
…
L i g i Hàmờ ọ
…
…
…
}
ĐQ trực tiếp
… Hàm1(…)
{
…
…
L i g i Hàm2ờ ọ
…
…
…
}
ĐQ gián tiếp
… Hàm2(…)
{
…
…
L i g i Hàmxờ ọ
…
…
…
}
VC
&
BB
7
Cấu trúc hàm đệ quy
Kỹ thuật lập trình đệ quy
{
if ()
{
…
return ;
}
…
… Lời gọi Hàm
…
}
ể
(TS)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.
VC
&
BB
8
Phân loại
Kỹ thuật lập trình đệ quy
2
TUY N TÍNHẾ
NH PHÂNỊ
H TỖ ƯƠNG
PHI TUY NẾ
1
3
4
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.
VC
&
BB
9
TênHàm() {
if () {
…
return ;
}
… TênHàm(); …
}
C u trúc chấ ương trình
Đệ quy tuyến tính
Kỹ thuật lập trình đệ quy
Tính S(n) = 1 + 2 + … + n
S(n) = S(n – 1) + n
ĐK dừng: S(0) = 0
.: Chương trình :.
long Tong(int n)
{
if (n == 0)
return 0;
return Tong(n–1) + n;
}
Ví dụ
VC
&
BB
10
TênHàm() {
if () {
…
return ;
}
… TênHàm();
…
… TênHàm();
…
}
C u trúc chấ ương trình
Đệ quy nhị phân
Kỹ thuật lập trình đệ quy
Tính số hạng thứ n của dãy
Fibonacy:
f(0) = f(1) = 1
f(n) = f(n – 1) + f(n – 2) n > 1
ĐK dừng: f(0) = 1 và f(1) = 1
.: Chương trình :.
long Fibo(int n)
{
if (n == 0 || n == 1)
return 1;
return Fibo(n–1)+Fibo(n–2);
}
Ví dụ
VC
&
BB
11
TênHàm1() {
if ()
return ;
… TênHàm2(); …
}
TênHàm2() {
if ()
return ;
… TênHàm1(); …
}
C u trúc chấ ương trình
Đệ quy hỗ tương
Kỹ thuật lập trình đệ quy
Tính số hạng thứ n của dãy:
x(0) = 1, y(0) = 0
x(n) = x(n – 1) + y(n – 1)
y(n) = 3*x(n – 1) + 2*y(n – 1)
ĐK dừng: x(0) = 1, y(0) = 0
.: Chương trình :.
long yn(int n);
long xn(int n) {
if (n == 0) return 1;
return xn(n1)+yn(n1);
}
long yn(int n) {
if (n == 0) return 0;
return 3*xn(n1)+2*yn(n1);
}
Ví dụ
VC
&
BB
12
TênHàm() {
if () {
…
return ;
}
… Vòng lặp {
… TênHàm(); …
}
…
}
C u trúc chấ ương trình
Đệ quy phi tuyến
Kỹ thuật lập trình đệ quy
Tính số hạng thứ n của dãy:
x(0) = 1
x(n) = n
2
x(0) + (n1)
2
x(1) + … +
2
2
x(n – 2) + 1
2
x(n – 1)
ĐK dừng: x(0) = 1
.: Chương trình :.
long xn(int n)
{
if (n == 0) return 1;
long s = 0;
for (int i=1; i<=n; i++)
s = s + i*i*xn(n–i);
return s;
}
Ví dụ
VC
&
BB
13
Các bước xây dựng hàm đệ quy
Kỹ thuật lập trình đệ quy
Tìm các trường
h p suy bi n (neo)ợ ế
T ng quát hóa bài toán c th thành ổ ụ ể
bài toán t ng quát.ổ
Thông s hóa cho bài toán t ng quátố ổ
VD: n trong hàm tính t ng S(ổ n), …
Chia bài toán t ng quát ra thành:ổ
Ph n không ầ đệ quy.
Ph n nhầ ư bài toán trên nhưng
kích thước nh hỏ ơn.
VD: S(n) = S(n – 1) + n, …
Các trường h p suy bi n c a bài toán.ợ ế ủ
Kích thước bài toán trong trường h p ợ
này là nh nh t.ỏ ấ
VD: S(0) = 0
Tìm thu t gi iậ ả
t ng quátổ
Thông s hóaố
bài toán
VC
&
BB
14
Cơ chế gọi hàm và STACK
Kỹ thuật lập trình đệ quy
{
…;
A();
…;
D();
…;
}
main()
{
…;
B();
…;
C();
…;
}
A()
{
…;
}
C()
{
…;
D();
…;
}
B()
{
…;
}
D()
main
A
B C
D
D
M M
A
M
A
B
M
A
M
A
B
M
A
M
A
C
M M M
D
B
D
A
M
ST
A
C
K
Th i gianờ
VC
&
BB
15
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
VC
&
BB
16
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
F(4)
F(2)
F(3)
F(1)
F(2)
F(1) F(0)
+
+
+1 12
2 13
3
F(1) F(0)+1 12
25
5
VC
&
BB
17
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
VC
&
BB
18
Các vấn đề đệ quy thông dụng
Kỹ thuật lập trình đệ quy
Đệ
quy??
VC
&
BB
19
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 ...