Bài giảng Tin học - Giải thuật đệ quy

GIẢI THUẬT ĐỆ QUY1Mục tiêuĐến cuối chương, bạn có thể:Giải thích được giải thuật đệ quy là gì.Biết cách diễn đạt 1 tác vụ hướng đệ quy.Biết cách hiện thực hàm đệ quyPhân loại được các loại đệ quyGiải thích được cách chạy một hàm đệ quy.Biết cách khử một số giải thuật đệ quy.21- Đệ quy là gì (Recursion)Định nghĩa tường minh: Giải thích khái niệm mới bằng những khái niệm đã có.Người = Động vật cấp cao.Định nghĩa lòng vòng: Giải thích 1 khái niệm bằng chính khái niệm đó.Đệ quy: Đưa ra 1 định nghĩa có sử dụng chính khái niệm đang cần định nghĩa( quay về ).Người = con của hai người khác.3Đệ quy là gì?...Con người hiểu được định nghĩa đệ quy vì đệ quy có chặn (điều kiện biên, điều kiện suy biến) – có thể là biên ngầm định.Người = con của hai người khác  Ngầm hiểu là có 2 người đầu tiên.Thư mục = các thư mục con + các tập tin  Ngầm hiểu: Hiển nhiên tồn tại thư mục gốc là cả ổ đĩa.42- Kiểu dữ liệu đệ quyMột người được mô tả bằng: tên, năm sinh, cha (một người khác), mẹ (một người khác).struct NGUOI { char Ten[51]; int namsinh; NGUOI cha; NGUOI me;};Cấu trúc này không khả thi trong máy tính vì không thể cấp bộ nhớ5Kiểu dữ liệu đệ quy...Sửa lại:struct NGUOI { char Ten[51]; int namsinh; NGUOI* pCha; NGUOI* pMe;};NGUOI x;Ten (51 bytes)namsinh (2 bytes)pCha (4 bytes)pMe (4 butes)x63- Tác vụ đệ quyCó thể diễn đạt nhiều tác vụ hướng đệ quy.1+2+3+...+ (n-2) + (n-1) + nCộng( 1 tới n) = n + Cộng (1 tới n-1)Điều kiện biên là điều kiện ngưng không đệ quy nữa.Điều kiện biên: Cộng (1 tới 1) là 1Cộng (1 tới n) = 1, n=1 n + Cộng (1 tới n-1) 74- Cách viết hàm đệ quy Định nghĩa tác vụ đệ quy theo ngôn ngữ tự nhiên thế nào thì hàm cũng viết như thế.Thí dụ: 	n! = 1*2*3*4*5*... * n	n! = 1, n=0) { Nếu (n/2>0) Xuất dạng nhị phân của n/2; Xuất (n%2); }Bạn tự viết11Luyện tập viết hàm đệ quy...Viết 2 hàm xuất hệ 8, hệ 16 cho 1 số long n125- Phân loại hàm đệ quyTùy thuộc cách diễn đạt tác vụ đệ quy mà có các loại đệ quy sau.Đệ quy tuyến tính.Đệ quy nhị phân.Đệ quy phi tuyếnĐệ quy hỗ tương.135.1-Đệ quy tuyến tínhThân hàm gọi 1 lần chính nóUn = a , n=1 ( trị thứ n của cấp số cộng) r + Un-1 , n>1double U (int n, double a, double r){ 	if (n==1) return a; 	return r + U(n-1,a,r);}145.2-Đệ quy nhị phânThân hàm gọi 2 lần chính nó.Chuỗi số Fibonacci: 1 1 2 3 5 8 13 ...Un = 1, n=1,2 Un-2 + Un-1 , n>2long Fibo (int n){ 	if (n6long U ( int n){ if (n0; i--) S+= U(n-i); return S;}165.4 - Đệ quy hỗ tương2 hàm đệ quy gọi nhau Un = n , n=5 Gn = n-3 , n8long G(int n);long U ( int n){ if (n Max(a, n-1)? a[n-1] : Max(a,n-1)Thuật toán đệ quy tìm trị nhỏ nhất của mảng?Do yourself.20Xuất ngược 1 chuỗiS= “QWERT”  TREWQKý tự đầu của SKết qủa xuất ngược chuỗi &S[1]Xuất_ngược (S) : L= strlen(S); if (L>1) Xuất_ngược (S+1); if (L) Xuất (*S); Nghĩa là có chuỗi con21Bài toán xuất ngược 1 chuỗi227- Bài toán Tháp Hà NộiABC23Bài toán Tháp Hà NộiChuyển n đĩa từ cột X sang cột Z nhờ cột trung gian Y(1) Chuyển n-1 đĩa từ cột X sang cột Y nhờ cột trung gian Z vì các đĩa bên trên là các đĩa nhỏ.(2) Chuyển đĩa n (to nhất) từ cột X sang cột đích Z.(3) Làm lại cho n-1 đĩa còn lại đang ở cột Y sang cột Z với X là cột trung gian.24Tháp Hà Nội...321ACB321321321258- Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kqn: 4Kqn: 3Kqn: 2Kqn: 1Kq26Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq:n: 4Kq:n: 3Kq:n: 2Kq:n: 1Kq 127Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq:n: 4Kq:n: 3Kq:n: 2Kq:n: 1Kq 1n: 2Kq: 2*1=228Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq:n: 4Kq:n: 3Kq:n: 2Kq: 2 n: 3Kq: 3*2=629Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq:n: 4Kq:n: 3Kq: 6n: 4Kq: 4*6=2430Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq:n: 4Kq: 24n: 5Kq:5*24=12031Cách thực thi 1 hàm đệ quyXét hàm tính giai thừa của 5n: 5Kq: 120329- Nhận xét về hàm đệ quyHÀM ĐỆ QUY: Vừa tốn bộ nhớ vừa chạy chậm Giải thuật đệ quy đẹp (gọn gàng), dễ chuyển thành chương trình. Nhiều ngôn ngữ không hỗ trợ giải thuật đệ quy (Fortran).Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng lại rất khó mô tả với giải thuật không-đệ-quy.3310- Khử đệ quyLà quá trình chuyển đổi 1 giải thuật đệ quy thành giải thuật không đệ quy.Chưa có giải pháp cho việc chuyển đổi này một cách tổng quát.Cách tiếp cận:Dùng quan điểm đệ quy để tìm giải thuật cho bài toán.Mã hóa giải thuật đệ quy.Khử đệ quy để có giải thuật không-đệ-quy.3410.1- Khử đệ quy bằng vòng lặpÝ tưởng: Lưu lại các trị của các lần tính toán trước làm dữ liệu cho việc tính toán của lần sau.Đi từ điều kiện biên đi tới điều kiện kết thúc.35Thí dụ: Hàm tính giai thừa của nlong GiaiThua( int n){ if (n0) return NULL (không có nghiệm) else if (b-a có x dùng kỹ thuật đệ quy.Tìm vị trí có x trong ma trận m,nNULL, nếu n<1nếu có x trong cột cuối thì return vị trí nàynếu có x trong hàng cuối thì return vị trí nàyreturn Tìm vị trí có x trong m,n-142