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

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