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,. | Kỹ thuật lập trình Bài 3 – Giải thuật đệ quy Ngô Hữu Dũng 61 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Quy 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) đúng Bướ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 62 Bướ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) = k2 Khi đó: S(k+1): 1 + 3 + 5 + . + (2k – 1) + [2(k+1) – 1] = k2 + (2k + 1) = (k + 1)2 Vậ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-2017 Ngô Hữu Dũng Lậ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) = 1 Bướ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. } 63 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô Hữu Dũng Cách hoạt động 1. 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) + 3 S(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 + 7 S(5) = 1 + 3 + 5 + 7 + 9 = 25 = 52 // Return S(5) 64 Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017 Ngô 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át Phầ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àm Thuận lợi .
