Bài giảng Kỹ thuật lập trình: Chương 1 - Võ Quang Hoàng Khang

Chia sẻ: 5A4F5AFSDG 5A4F5AFSDG | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

132
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 1 trang bị cho người học kiến thức cơ bản về lập trình đệ quy. Nội dung chính trong chương này gồm có: Khái niệm, thiết kế giải thuật đệ quy, cấu trúc hàm đệ quy, phân loại đệ quy, đệ quy tuyến tính, đệ quy nhị phân, đệ quy hỗ tương,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Chương 1 - Võ Quang Hoàng Khang

Võ Quang Hoàng Khang 1
 Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)? 2
3
 Một hàm được gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó.  Ví dụ S(n) được tính thông qua S(n-1)  2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. 4
 B1. Tham số hoá bài toán.  B2. Phân tích trường hợp chung: đưa bài toán về dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghĩa dần tiến đến trường hợp suy biến.  B3. Tìm trường hợp suy biến. 5
Hàm đệ quy gồm 2 phần:  Phần cơ sở: Điều kiện để thoát khỏi đệ quy (điểm dừng)  Phần đệ quy: gọi đến chính nó với giá trị mới của tham số nhỏ hơn giá trị ban đầu.  Ví dụ: n * (n - 1)! n!  0!  1 6
(n - 1)!* n • Công thức truy hồi tính n!  0!  1 • Hàm đệ quy: long GiaiThua( int n ) { if(n==0) return 1; else return GiaiThua(n-1)*n; } 7
• Hàm đệ quy nhập mảng 1 chiều: void NhapMang(int a[],int n) { if(n>0) { NhapMang(a,n-1); cin>>a[n-1]; } } 8
9
Trong thân hàm có duy nhất 1 lời gọi hàm gọi lại chính nó một cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 10
Ví dụ 1: Tính S (n)  1  2  3    n  Điều kiện dừng: S(0) = 0.  Công thức truy hồi: S(n) = S(n-1) + n. int TongS (int n) { if(n==0) //điểm dừng return 0; return ( TongS(n-1) + n ); } 11
Ví dụ 2: Tính n! long GiaiThua(int n) { if (n==0) //điểm dừng return 1; else return n*GiaiThua(n-1); } với n=5 main() GiaiThua(5) GiaiThua(4) GiaiThua(3) GiaiThua(2) GiaiThua(1) 5 4 3 2 1 n 5 n 5 n 4 n 3 n 2 n 1 120 24 6 2 1 12
Trong thân hàm có 2 lời gọi hàm gọi lại chính nó một cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 13
Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩa bởi công thức truy hồi: f0=f1=1 ; fn = fn-1 + fn-2 ; (n>1) Điều kiện dừng: f(0) = f(1) = 1. long Fibonaci(int n) { if(n==0 || n==1) return 1; return Fibonaci(n-1)+ Fibonaci(n-2); } 14
Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp. TenHam () { for (int i = 1; i
Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như sau: X0 =1 ; Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ; (n≥1) Điều kiện dừng: X(0) = 1. long TinhXn(int n) { if(n==0) return 1; long s = 0; for (int i=1; i
Trong thân của hàm này có lời gọi hàm đến hàm kia và ngược lại. g() f() f() f() g() h() 17
TenHam2 (); TenHam1 () { //Thực hiện một số công việc (nếu có) …TenHam2 (); //Thực hiện một số công việc (nếu có) } TenHam2 () { //Thực hiện một số công việc (nếu có) …TenHam1 (); //Thực hiện một số công việc (nếu có) } 18
Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; (n>0) Yn = n2Xn-1 + Yn-1; (n>0) - Điều kiện dừng: X(0) = Y(0) = 1. long TinhYn(int n); long TinhXn (int n) { if(n==0) return 1; return TinhXn(n-1) + TinhYn(n-1); } //---------------------------------------------------------------------- long TinhYn (int n) { if(n==0) return 1; 19 return n*n*TinhXn(n-1) + TinhYn(n-1); }
 Thay vì sử dụng lời giải đệ quy cho một bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp.  Ưu và khuyết điểm của đệ quy: Ưu điểm Khuyết điểm Thuận lợi cho việc biểu diễn Có khi không được tối ưu về bài toán thời gian Gọn (đối với chương trình) Có thể gây tốn bộ nhớ  Trong lập trình HẠN CHẾ viết hàm đệ quy nếu thấy không cần thiết. 20