Bài giảng Cấu trúc dữ liệu và giải thuật - Đệ qui

ĐỆ QUIKhái niệmCấu trúc chương trìnhNguyên lý hoạt độngƯu và nhược điểmBài toán minh hoạTính N!Tìm số hạng thứ n của dãy FibonacciBài toán tháp Hà NộiKhử đệ qui1Khái niệm	Một khái niệm X gọi là định nghĩa theo đệ qui nếu trong chính định nghĩa X có sử dụng khái niệm X	Ví dụ:Định nghĩa Số tự nhiên:0 là một số tự nhiênn > 0 là số tự nhiên nếu n – 1 là số tự nhiên	Định nghĩa n giai thừa0! = 1Nếu n >0 thì n! = n* (n-1)!2Cấu trúc chương trìnhChương trình đệ qui gồm hai phần chính:Điều kiện thoát khỏi đệ quiTrong phần thân chương trình có lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu.3Cấu trúc chương trình( tiếp)Chươngtrình A(x) {	If (điều kiện thoát đệ qui)	Kết thúc đệ qui;	.	ChươngtrìnhA(x’);	.}Với x’ 0, N! = N*(N-1)!Ví dụ: Tính 5!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 = 1206Bài toán tính N!(tiếp)GiaiThừa(n)Bước 1: Nếu n = 0 thì GiaiThừa =1,ngược lại	GiaiThừa = n*GiaiThừa(n-1)	7Bài toán tính N!(tiếp)Function GiaiThua(n: interger) : integer; Begin	if(n=0) then GiaiThua =1	else	GiaiThua = n*GiaiThua(n-1);End;8Bài toán tính N!(tiếp)Program GiaiThua;Uses crt;Var n,kq: integer;Begin	Clrscr;	Write(‘Moi ngai nhap so n=‘);readln(n);	Kq=GiaiThua(n);	Write(‘Gia tri’, n,’!’, = ‘,kq :5);	Readln;End. 9GIAITHUA(3)Nguyên lý hoạt độngKhi ta thực hiện gọi hàm Giai thừa: GiaiThừa(5)GIAITHUA(5)GIAITHUA(4)GIAITHUA(2)GIAITHUA(1)GIAITHUA(0)GIAITHUA(3)GIAITHUA(5)GIAITHUA(4)GIAITHUA(2)GIAITHUA(1)GIAITHUA(0)GIAITHUA(3)GIAITHUA(5)GIAITHUA(4)GIAITHUA(2)GIAITHUA(1)GIAITHUA(3)GIAITHUA(5)GIAITHUA(4)GIAITHUA(2)GIAITHUA(3)GIAITHUA(5)GIAITHUA(4)GIAITHUA(5)GIAITHUA(4)GIAITHUA(5)10Nguyên lý hoạt động (tiếp)Các lời gọi hàm lần lượt được cất vào bộ nhớ Khi thực hiện, lần lượt thực hiện theo thứ tự “vào sau ra trước” 11Ưu điểmThích hợp với các bài toán có bản chất đệ quySáng sủaDễ hiểuThể hiện được bản chất của bài toánChương trình ngắn gọn12Nhược điểmTốc độ thực hiện chương trình chậmLỗi “Tràn stack”13Bài toán tìm số hạng thứ n của dãy FibonacciSố hạng thứ n của dãy fibonacci được định nghĩa:F0 = 1F1 = 1Fn =Fn-1 + Fn-2Ví dụ:1,1,2,3,5,8,13,21,34,55,. là dãy fibonacci14Bài toán tìm số hạng thứ n của dãy Fibonacci (tiếp)InputCho n là số tự nhiênOutputTính số hạng thứ n của dãy fibonacci15Bài toán tìm số hạng thứ n của dãy Fibonacci (tiếp)Điều kiện thoát khỏi đệ quiN0) then	begin	ChuyenDia(n-1,A,B,C);	Chuyen1Dia(A,B);	ChuyenDia(n-1,C,A,B);	end;	End;Procedure Chuyen1Dia( A :char, B: char);begin	write(‘Chuyển từ dia‘,A,’ -> sang dia’,B);End;32Bài toán tháp Hà nội - Thuật toán (tiếp)Program ThapHaNoi;Uses crt;Var i:integer; A,B,C :char;	Begin	clrscr;	Write(‘Mời ngài cho biết số đĩa’);readln(n);	ChuyenDia(n,A,B,C);	Readln;End.33Khử đệ qui Thay thế lời gọi đệ qui trong chưong trình bằng các lệnh khác để giải quyết bài toán.VD: Khử đệ qui bài tính n!function GiaiThua(n: integer): integer;Var T,i:integer;Begin	T=1;	if (n>0) then	for i=0 to n do T = T*i;	GiaiThua =T;End;34Khử đệ qui (tiếp) Khử đệ qui: tìm số thứ n của dãy fibonacci:Function Fibonacci(n: integer): integer;Var i,a,b,kq: integer;Begin	if (n=0) then kq=1	else if(n=1) then kq=1	 else	begin	 i=1;a =0;b=1;	 while(i<=n) do	 begin	 	i++;	a =a+b;b= a-b;	 end;	 kq=x;	 	end;	Fibonacci = kq;	End;35Bài tậpViết chương trình sử dụng đệ qui để tìm USCLN của hai số tự nhiên a,b.Viết chương trình sử dụng đệ qui để tính C(n,k) = n! / (n-k)!k!Với:	C(n,n)=1	C(n,0)=1	C(n,k) = C(n-1,k-1) +C(n-1,k) 0<k<nViết thủ tục đệ qui thực hiện in ngược một dòng ký tự cho trước. (vd: “PASCAL” thì in ra “LACSAP”)36