Xem mẫu

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