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 trong việc giải những bài toán có tính chất quy nạp
Làm gọn chương trình
Nhược điểm
65
Không tối ưu, tốn bộ nhớ
Kỹ thuật lập trình | DHTH11C | HK1 | 2016-2017
Ngô Hữu Dũng
nguon tai.lieu . vn