Bài giảng Kỹ thuật lập trình: Bài 3 - TS. Ngô Hữu Dũng

Bài giảng Kỹ thuật lập trình: Bài 3 do TS. Ngô Hữu Dũng biên soạn cung cấp cho người học các kiến thức: Quy nạp toán học, lập trình đệ quy, cách hoạt động, khái niệm đệ quy, một số loại đệ quy, đệ quy tuyến tính,...
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Bài 3 - TS. Ngô Hữu DũngKỹ thuật lập trìnhBài 3 – Giải thuật đệ quyNgô Hữu Dũng61Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017Ngô Hữu DũngQuy nạp toán họcChứng minh hàm F(n) đúng với mọi số tự nhiên n ≥ N0.Phương pháp quy nạp:Bước cơ sở: Chỉ ra trường hợp ban đầu F(N0) đúngBước quy nạp: Chứng minh rằng giả sử F(k) đúng thì F(k+1) đúng.Ví dụ: Chứng minh S(n): 1 + 3 + 5 + 7 + …+ (2n-1) = n2 (*), với n ≥ 162Bước cơ sở: Trường hợp n = 1, ta có (2n-1) = n2 = 1 là đúng hiển nhiên.Bước quy nạp: Giả sử S(k) đúng, ta có 1 + 3 + 5 + ... + (2k – 1) = k2Khi đó: S(k+1): 1 + 3 + 5 + ... + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1)= (k + 1)2Vậy S(k + 1) = (k + 1)2 là đúng. Suy ra S(n) đúng với mọi n ≥ 1.Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017Ngô Hữu DũngLập trình đệ quyLập trình tính S(n) = 1 + 3 + 5 + … + (2n – 1) = n2 với n ≥ 1.Từ bài toán quy nạp ta có:Bước cơ sở: S(1) = 1Bước quy nạp: S(k+1) = S(k) + [2(k + 1) – 1] hay S(k) = S(k – 1) + (2k – 1)Phương pháp lập trình đệ quy:Phần cơ sở: S(1) = 1 Phần đệ quy: S(n) = S(n – 1) + (2n – 1)1. int S(int n)2. { Áp dụng vào lập trình:if (n==1) return 1;3.4.else return S(n-1) + (2*n – 1);5. }63Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017Ngô Hữu DũngCách hoạt động1. int S(int n)Giả sử n = 5,2. {hàm đệ quy chạy như sau:3.if (n==1) return 1;4.else return S(n-1) +S(5) = S(4) + 9 // Gọi hàm S(4)S(4) = S(3) + 7 // Gọi hàm S(3) 5. }// Gọi hàm S(2)S(3) = S(2) + 5// Gọi hàm S(1)S(2) = S(1) + 3S(1) = 1// Return S(1)S(2) = 1 + 3 // Return S(2)// Return S(3)S(3) = 1 + 3 + 5// Return S(4)S(4) = 1 + 3 + 5 + 7S(5) = 1 + 3 + 5 + 7 + 9 = 25 = 52 // Return S(5)64Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017Ngô Hữu Dũng(2*n–1);Khái niệm đệ quyKhái niệmThành phầnPhần cơ sở: Điều kiện thoátPhần đệ quy: Có phép gọi lại chính nóƯu điểmMột hàm gọi là đệ quy khi có phép gọi lại chính nó trong thân hàmThuận lợi trong việc giải những bài toán có tính chất quy nạpLàm gọn chương trìnhNhược điểm65Không tối ưu, tốn bộ nhớKỹ thuật lập trình | DHTH11C | HK1 | 2016-2017Ngô Hữu Dũng