Kĩ thuật lập trình - Chương 1: Lập trình đệ qui

Võ Quang Hoàng Khang 1 2 Cho S(n) = 1 + 2 + 3 + + n =>S(10)? S(11)? 3 4Một hàm được gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó.  Ví dụ S(n) được tính thông qua S(n-1)  2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. 5 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. 6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ụ:      1 0! 1)! -(n *n !n 7• Công thức truy hồi tính • Hàm đệ quy: long GiaiThua( int n ) { if(n==0) return 1; else return GiaiThua(n-1)*n; }      1 0! n * 1)! -(n !n 8• 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]; } } 9 10 Trong thân hàm có duy nhất 1 lời gọi hàm gọi lại chính nó một cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 11 Ví dụ 1: Tính  Đ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 ); } nnS  321)( 12 Ví 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 5n 5n 4n 3n 2n GiaiThua(5)main() 5 4 23 1 12624120 GiaiThua(2)GiaiThua(4) GiaiThua(3) 1n GiaiThua(1) 13 Trong thân hàm có 2 lời gọi hàm gọi lại chính nó một cách tường minh. TenHam () { if (điều kiện dừng) { //Trả về giá trị hay kết thúc công việc } //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) } 14 Ví dụ: Tính sô ́ hạng thứ n của dã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); } 15 Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp. TenHam () { for (int i = 1; i<=n; i++) { //Thực hiện một số công việc (nếu có) if (điều kiện dừng) { . . . //Trả về giá trị hay kết thúc công việc } else { //Thực hiện một số công việc (nếu có) TenHam (); } } } 16 Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như sau: X0 =1 ; Xn = n 2X0 + (n-1) 2X1 + + 1 2Xn-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<=n; i++) s = s + i * i * TinhXn(n-i); return s; } 17 Trong thân của hàm này có lời gọi hàm đến hàm kia và ngược lại. g() f() h() f() f() g() 18 TenHam2 (); TenHam1 () { //Thực hiện một sô ́ công việc (nếu có) TenHam2 (); //Thực hiện một sô ́ công việc (nếu có) } TenHam2 () { //Thực hiện một sô ́ công việc (nếu có) TenHam1 (); //Thực hiện một sô ́ công việc (nếu có) } 19 Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; (n>0) Yn = n 2Xn-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; return n*n*TinhXn(n-1) + TinhYn(n-1); }  Thay vì sử dụng lời giải đệ quy cho một bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp.  Ưu và khuyết điểm của đệ quy:  Trong lập trình HẠN CHẾ viết hàm đệ quy nếu thấy không cần thiết. Ưu điểm Khuyết điểm Thuận lợi cho việc biểu diễn bài toán Gọn (đối với chương trình) Có khi không được tối ưu về thời gian Có thể gây tốn bộ nhớ 20 Ví dụ 1: Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? *Giải pháp: Gọi Vh là số vi trùng tại thời điểm h. *Ta có: •Vh= 2Vh-1 •V0= 2 *Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2 21 Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu? Giải pháp: •Gọi Tn là số tiền có được sau n năm. •Ta có: Tn= Tn-1+ 0.12Tn-1= 1.12Tn-1 V(0) = 1000 Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000 22 Ví dụ 3: Bài toán tháp Hà Nội Chuyển một chồng n đĩa với kích thước khác nhau từ cột A sang cột C theo nguyên tắc: 23  Mỗi lần chỉ chuyển 1 đĩa.  Không được đặt đĩa lớn trên đĩa nhỏ.  Có thể dùng cột B làm cột trung gian B * Tham số hoá bài toán: HaNoi (n, A, B, C) Trong đó: n: Số đĩa. A: Cọc nguồn B: Cọc trung gian C: Cọc đích (A, B, C có kiểu ký tự) 24 Giải thuật đệ quy bài toán Tháp Hà Nội: * Trường hợp suy biến: Nếu n = 1 thì chuyển đĩa từ A qua C * Trường hợp chung (n  2): Thử với n=2: + Chuyển đĩa thứ nhất từ A sang B + Chuyển đĩa thứ hai từ A sang C + Chuyển đĩa thứ nhất từ B sang C  Tổng quát: + Chuyển (n -1) đĩa từ A sang B (C làm trung gian) + Chuyển 1 đĩa từ A sang C (B làm trung gian) + Chuyển (n -1) đĩa từ B sang C (A làm trung gian) 25 A B C 1 đĩa A B C 1 đĩa A B C 2 đĩa A B C 2 đĩa A B C 2 đĩa A B C 2 đĩa A B C N đĩa A B C N đĩa A B C N đĩa Giải thuật đệ quy bài toán Tháp Hà Nội: 35 void HaNoi (int n, char A, char B, char C) { if (n==1) cout<<A<<“”<< C; else { HaNoi(n-1, A, C, B); HaNoi(1, A, B, C); HaNoi(n-1, B, A, C); } } Bài tập 1: Viết hàm đệ quy biểu diễn nhị phân của 1 số nguyên n. Ví dụ: n=13  1101 36 Xuất dạng nhị phân của n: - Nếu (n/2 > 0) thì xuất dạng nhị phân của n/2; - Xuất (n%2); void XuatNhiPhan(int n) { if (n/2>0) XuatNhiPhan(n/2); cout<<n%2; } Bài tập 2: Chuyển số giây thành giờ, phút, giây. Ví dụ: nhập 3665 -> 1: 1: 5 giây 37 void DoiGio(int n, int &h, int &m, int &s) { if (n<60) s=n; else if (n/3600>0) { h=n/3600; DoiGio(n%3600, h, m, s); } else { m=n/60; DoiGio(n%60, h, m, s); } } Bài tập 3: Tính tổng các chữ số của một số nguyên n. Ví dụ: n=1980 =>Tổng=1+9+8+0=18 38 int Tong(int n) { if (n<10) return n; else return n%10 + Tong(n/10); } + Nếu (n<10) thì Tổng = n + Nếu (n>=10) thì Tổng = n%10 + Tổng các chữ số của n/10 Bài tập 4: Xuất ngược các chữ số của số nguyên n. Ví dụ n=1980  xuất 0891 39 + Nếu n<10 thì Xuất n + Nếu n>=10 thì Xuất n%10 và Xuất ngược n/10 void XuatSoNguoc(int n) { if (n<10) cout<<n; else { cout<<n%10; XuatSoNguoc(n/10); } } Bài tập 5: Viết hàm đệ quy in đảo ngược chuỗi X - Trường hợp chung: + In ký tự cuối cùng của chuỗi X. + Lấy phần chuỗi còn lại. - Trường hợp suy biến: Nếu chuỗi rỗng thì không làm gì cả. 40 void InNguoc(char *X) { static int len=strlen(X); if (len>0) { cout<<X[len-1]; len--; InNguoc(X); } } Bài tập 6: Viết hàm đệ quy kiểm tra xem một số có phải số nguyên tố không 41 bool isPrime(int N) { if (N==1) return true; int static M=N-1; if (M==1) return true; else if (N%M==0) return false; else { M--; isPrime(N); } } Bài tập 7: In hình tam giác sau bằng cách đệ quy 42 void InSao(int n) { if (n>1) InSao(n-1); for (int i=0; i<n; i++) cout<<"*"; cout<<endl; } Bài tập 8: Cho mảng a có n phần tử, tính tổng các phần tử trong mảng bằng đệ quy 43 Điều kiện dừng: nếu n=0 thì sum(a,n)=0 Giải thuật chung: sum (a,n) = a[n-1] + sum(a, n-1), n>0 Bài tập 9: Cho mảng a có n phần tử, tìm giá trị lớn nhất trong mảng bằng đệ quy 44 Điều kiện dừng: Mảng 1 phần tử thì trị lớn nhất là a[0] Giải thuật chung: Max (a,n) = a[0] , n=1 a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1), n>1 45 1. Viết hàm đệ quy tính: xn 2. Viết hàm đệ quy đếm số lần xuất hiện của kí tự ch trong chuỗi S. 3. Viết hàm đệ quy tính giá trị phần tử thứ k của dãy số sau: 1 2 3 6 11 20 37 68 125 . Sau đó viết chương trình in ra màn hình n số của dãy số trên. 46 1. Viết hàm đệ quy tính tổng S=1+2+3+4++n (với n>0) 2. Viết hàm đệ quy tính n! (với n>=0) 3. Viết hàm đệ quy tìm số hạng thứ k của dãy Fibonaci. Sau đó viết chương trình in ra màn hình n số hạng của dãy. 4. Viết hàm đệ quy tìm ước số chung lớn nhất của 2 số nguyên dương. 5. Viết hàm đệ quy giải quyết bài toán tháp HÀ NỘI. 6. Viết hàm đệ quy biểu diễn nhị phân của 1 số nguyên n. 7. Viết hàm đệ quy chuyển số giây thành giờ, phút, giây. Ví dụ: nhập 3665 -> 1: 1: 5 giây 8. Viết hàm đệ quy tính tổng các chữ số của một số nguyên n. 47 9. Viết hàm đệ quy xuất ngược các chữ số của số nguyên n. 10.Viết hàm đệ quy in đảo ngược chuỗi X. 11.Viết hàm đệ quy kiểm tra xem một số n có phải số nguyên tố không? 12.Cho mảng a có n phần tử, tính tổng các phần tử trong mảng bằng đệ quy. 13.Cho mảng a có n phần tử, tìm giá trị lớn nhất trong mảng bằng đệ quy. 14.Làm các bài tập trên mảng 1 chiều, sử dụng kỹ thuật đệ quy. 15.Viết hàm đệ quy in các ước số của số nguyên dương n.