ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HỌC TƯ NHIÊN
BÀI TẬP LỚN
TỔNG QUAN VỀ KỸ THUẬT
ĐỆ QUY
GIẢNG VIÊN : Nguyễn Bích Thuỷ
Lớp K52A3,Toán-Tin ứng dụng
M c l cụ ụ

GIỚI THIỆU CHUNG VỀ KỸ THUẬT ĐỆ QUY

KỸ THUẬT ĐỆ QUY.

Khái niệm kỹ thuật đệ quy, các loại đệ quy.

Khái niệm đệ quy.

Phương pháp sử dụng kỹ thuật đệ quy trong một bài toán.

Cơ chế thực hiện giải thuật đệ quy.

Ví dụ minh họa

KHỬ ĐỆ QUY.

Tổng quan về vấn đề giải thuật đệ quy.

Các trường hợp khử đệ quy đơn giản.

Ví dụ minh họa.


n
Các loại đệ quy( tiếp)
Phân loại theo cách gọi hàm
a) Đệ quy tuyến tính
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.
b) Đệ quy nhị phân
Trong thân của hàm có hai lời
gọi hàm gọi lại chính nó một
cách tường minh.
HÀM(tham sô 2)HÀM(tham số1)
HÀM ( tham số 2)
HÀM( tham số 3)
…
HÀM( tham sô 1)
Các loại đệ quy
c)Đệ quy phi tuyến
Trong thân hàm này có lời gọi hàm gọi lại chính nó đặt bên trong vòng
lặp.
d) Đệ quy hỗ tương
Trong thân hàm này có lời gọi hàm đến hàm kia và ngược lại.
HÀM 1( TS )
HÀM 2(TS )
HÀM 3( TS)
HÀM(TS)
HÀM1(TS)
HÀM2(TS)
Phương pháp sử dụng kỹ thuật
đệ quy

G
i
á

t
r
ị

n
e
o
F(n)=T.F(n-1) F(2)=T.(F(1)=a)
Lưu trong bộ nhớ máy
Bài toán tháp Hà Nội

Input: n: số đĩa cần chuyển từ cột A->C qua trung gian
B

Output: in ra cách di chuyển n đĩa
A-Nguồn B-TG C-ĐÍCH
Bài toán tháp Hà Nội
1. Phân tích:
Xét: hàm THN(char A;charB;char C;int n) hàm xử lý chương trình
Move(char A,char C): phép di chuyển cơ bản từ A->C

Thông số bài toán: xét bài toán ở mức độ tổng quát THN(A,B,C,n)

Trưòng hợp suy biến và cách giải
–
n=0: TNH(A,B,C,0)={Φ}

•
Bài toán tìm đường đi, chu trình. Vd: halminton
Lưu ý:
1.đệ qui sử dụng bộ nhớ kiểu LIFO chứa kết quả trung gian và do
đó thận trọng lường trước việc kết thúc quá trình đệ qui.
2.Tránh dùng đệ qui khi có thể dùng phép lặp tính toán
Nhận xét về kỹ thuật đệ quy
Ưu điểm
Điểm mạnh lớn nhất: làm chương trình, code, trở lên ngắn gọn.
Dễ chuyển thành chương trình trên các ngôn ngữ lập trình.
Nhược điểm
Nhược điểm lớn nhất là tốn bộ nhớ,
Mất nhiều thời gian xử lý, làm giảm tốc độ chạy chương trình.
Không áp dụng cho mọi ngôn ngữ lập trình.
BACK
KHỬ ĐỆ QUY

Tổng quan về vấn đề giải thuật đệ quy
Giải thuật giải bài toán bằng đệ quy thường rất đẹp, nhưng…

Các trường hợp khử đệ quy đơn giản.
•
Khử đệ quy bằng vòng lặp.
•
Khử đệ quy hàm đệ quy arsac.
•
Khử đệ quy bằng các phương pháp khác
Khử đệ quy bằng vòng lặp
•
W(V,U) với U là các biến thay đổi

Không thỏa điều kiện
while
Khái niệm hàm
ARSAC
Dạng mã giả:
A(X)=if (C(X))
return( DS (A(CS(X)) ,FS(CS(X),X) )
else (return (BS(X ) )
Trong đó DS,FS,BS,CS là các giải thuật không đệ quy.
•
BS(X) , CS(Y) , DS(U,V) , FS(U,V) là các hàm đơn giản không có lệnh gọi
hàm con.
•
X,Y,U,V là các biến véc tơ hoặc các biến đơn trị.

•
Cơ chế hàm arsac :
u
1
u
x
u
n
u
2
U
n+1
v
n
v

bài toán phức tạp một cách đơn giản
•
Xây dựng đệ quy thông qua việc xác định
điều kiện dừng và bước thực hiên tiếp
theo
•
Chỉ nên cài dặt phương pháp đệ quy khi
không còn cách giải quyết bằng cách lặp
thông thường
Thank you for listening