Bài giảng Cấu trúc dữ liệu và giải thuật: Hệ thức đệ qui - Lê Thị Ngọc Hạnh

Chương này cung cấp những kiến thức về hệ thức đệ qui. Thông qua chương này người học có thể nắm bắt được: Định nghĩa hệ thức đệ qui, nghiệm tổng quát, nghiệm riêng, mục đích giải hệ thức đệ qui, hệ thức đệ qui tuyến tính thuần nhất,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Hệ thức đệ qui - Lê Thị Ngọc Hạnh HỆ THỨC ĐỆ QUI 1 6/3/2015 ĐỊNH NGHĨA  Một hệ thức đệ qui tuyến tính cấp k là hệ thức có dạng: Trong đó: ak ≠ 0, a1,…, ak-1 là các số thực {fn} là một dãy số thực cho trước {xn} là dãy ẩn nhận các giá trị thực 6/3/2015 2 ĐỊNH NGHĨA Trường hợp dãy fn = 0 với mọi n thì (1) trở thành: Ta nói (2) là một hệ thức đệ qui tuyến tính thuần nhất cấp k. 6/3/2015 3 NGHIỆM TỔNG QUÁT Mỗi dãy {fn} thỏa (1) được gọi là một nghiệm của (1). Nhận xét rằng mỗi nghiệm {xn} của (1) được hoàn toàn xác định bởi k giá trị đầu x0, x1, …, xk-1  Họ dãy số { xn = xn(C1, C2, …, Ck)} phụ thuộc vào k họ tham số C1, C2, …, Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãy của họ này đều là nghiệm của (1) 6/3/2015 4 NGHIỆM RIÊNG  Cho {xn} là nghiệm tổng quát của (1) và với mọi k giá trị ban đầu y0, y1, …, yk-1, tồn tại duy nhất các giá trị của k tham số C1, C2, …, Ck sao cho nghiệm {xn} tương ứng thỏa: x0 = y0, x1=y1, …, xk-1 = yk-1 (*) Khi đó, nghiệm {xn} tương ứng được gọi là nghiệm riêng ứng với điều kiện ban đầu (*). 6/3/2015 5 MỤC ĐÍCH GIẢI HỆ THỨC ĐỆ QUI  Giải một hệ thức đệ qui là đi tìm nghiệm tổng quát của nó. Nếu hệ thức đệ qui có kèm điều kiện ban đầu, ta phải tìm nghiệm riêng thỏa điều kiện ban đầu đó. 6/3/2015 6 VÍ DỤ Ví dụ 1: (Dãy Fibonacci) Bài toán: Một đôi thỏ con (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một đực và một cái), mỗi đôi thỏ con, khi tròn hai tháng tuổi, lại mỗi tháng đẻ ra một đôi thỏ con và quá trình sinh nở cứ thế tiếp tục tiếp diễn. Tính Fn là số đôi thỏ có ở tháng thứ n? 6/3/2015 7 VÍ DỤ Giải: Tháng đầu tiên và tháng thứ 2 chỉ có một đôi thỏ. Sang tháng thứ 3, đôi thỏ này sẻ đẻ ra một đôi thỏ, vì thế tháng này sẽ có hai đôi thỏ. Với n>= 3, ta có Fn = Fn-1 + số đôi thỏ được sinh ra ở tháng thứ n. Do các đôi thỏ được sinh ra ở tháng thứ n-1 chưa đẻ con ở tháng thứ n, và ở tháng này mỗi đôi thỏ có ở tháng thứ n-2 sẽ đẻ ra được một đôi thỏ con nên số đôi thỏ được sinh ra ở tháng thứ n chính bằng Fn-2 6/3/2015 8 VÍ DỤ Như vậy, việc giải bài toán Fibonacci dẫn ta tới việc khảo sát dãy số (Fn), xác định bởi: F1=1 F2=1 Fn=Fn-1 + Fn-2 với n>2 6/3/2015 9 VÍ DỤ Ví dụ 2: Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm một hệ thức đệ qui cho xn . 6/3/2015 10 VÍ DỤ  Với n=1, ta có x1=1  Với n=2, ta có x2=2 Với n>2, để khảo sát xn ta chia thành hai trường hợp loại trừ lẫn nhau: 6/3/2015 11 VÍ DỤ Trường hợp 1: Bước đầu tiên gồm 1 bậc. Khi đó, cầu thang còn n-1 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-1 6/3/2015 12 VÍ DỤ Trường hợp 2: Bước đầu tiên là 2 bậc. Khi đó, cầu thang còn n-2 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-2 Theo nguyên lý cộng, số cách đi hết cầu thang là xn-1 + xn-2. Do đó ta có: xn= xn-1 + xn-2 6/3/2015 13 VÍ DỤ Vậy ta có hệ thức đệ quy tuyến tính thuần nhất cấp 2: 6/3/2015 14 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Xét hệ thức đệ qui tuyến tính thuần nhất Phương trình đặc trưng của (2) là phương trình bậc k định bởi: 6/3/2015 15 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Trường hợp k=1: Phương trình đặc trưng (*) trở thành λ – a1 = 0 nên có nghiệm là λ = a1 ; Khi đó, (2) có nghiệm tổng quát là: 6/3/2015 16 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Ví dụ: Hệ thức đệ qui Là một hệ thức đệ qui tuyến tính thuần nhất cấp 1. 6/3/2015 17 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Phương trình đặc trưng: 2λ - 3 = 0 có nghiệm là λ0 = 3/2 Do đó nghiệm tổng quát là: 6/3/2015 18 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Từ điều kiện ban đầu x1 = 1, ta có: C*3/2 = 1 Suy ra: C = 2/3 Do đó, nghiệm của hệ thức đệ qui đã cho là: xn = (3/2)n-1 6/3/2015 19 HỆ THỨC ĐỆ QUI TUYẾN TÍNH THUẦN NHẤT Trường hợp k=2: Phương trình đặc trưng (*) trở thành: λ2 - a1λ - a2 = 0 (*) Nếu (*) có hai nghiệm thực phân biệt λ1 và λ2 thì (2) có nghiệm tổng quát là: 6/3/2015 20 ...