GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_4

Phương pháp cơ bản để giải hệ thức truy hồi tuyến tính thuần nhất là tìm nghiệm dưới dạng an = rn, trong đó r là hằng số. Chú ý rằng an = rn là nghiệm của hệ thức truy hồi
Nội dung trích xuất từ tài liệu:
GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_4 CHƯƠNG II BÀI TOÁN ĐẾM Phương pháp cơ bản để giải hệ thức truy hồi tuyến tính thuần nhấtlà tìm nghiệm dưới dạng an = rn, trong đó r là hằng số. Chú ý rằng an =rn là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 + ... + ckan-k nếu vàchỉ nếurn = c1rn-1 + c2rn-2 + ... + ckrn-k hay rk  c1rk-1  c2rk-2  ...  ck-1r – ck = 0.Phương trình này được gọi là phương trình đặc trưng của hệ thức truyhồi, nghiệm của nó gọi là nghiệm đặc trưng của hệ thức truy hồi.Mệnh đề: Cho c1, c2, ..., ck là các số thực. Giả sử rằng phương trình đặctrưng rk  c1rk-1  c2rk-2  ...  ck-1r – ck = 0có k nghiệm phân biệt r1, r2, ..., rk. Khi đó dãy {an} là nghiệm của hệthức truy hồi an = c1an-1 + c2an-2 + ... + ckan-k nếu và chỉ nếu an = 1r1n +2r2n + ... + krkn, với n = 1, 2, ... trong đó 1, 2, ..., k là các hằng số.Thí dụ 14: 1) Tìm công thức hiển của các số Fibonacci. Dãy các số Fibonacci thỏa mãn hệ thức fn = fn-1 + fn-2 và các điều 1 5kiện đầu f0 = 0 và f1 = 1. Các nghiệm đặc trưng là r1 = và r2 = 2 221 5 1 5 n . Do đó các số Fibonacci được cho bởi công thức fn = 1( ) + 2 2 1 5 n 1 52( ). Các điều kiện ban đầu f0 = 0 = 1 + 2 và f1 = 1 = 1( ) 2 2 1 5 1 1+ 2( Từ hai phương trình này cho ta 1 = 2 = - . Do đó ). , 2 5 5các số Fibonacci được cho bởi công thức hiển sau: 1 1 5 n 1 1 5 n fn = ( ) - ( ). 2 2 5 5 2) Hãy tìm nghiệm của hệ thức truy hồi an = 6an-1 - 11an-2 + 6an-3với điều kiện ban đầu a0 = 2, a1 = 5 và a2 = 15. Đa thức đặc trưng của hệ thức truy hồi này là r3 - 6r2 + 11r - 6.Các nghiệm đặc trưng là r = 1, r = 2, r = 3. Do vậy nghiệm của hệ thứctruy hồi có dạng an = 11n + 22n + 33n.Các điều kiện ban đầu a0 = 2 = 1 + 2 + 3 a1 = 5 = 1 + 22 + 33 a2 = 15 = 1 + 24 + 39.Giải hệ các phương trình này ta nhận được 1= 1, 2 = 1, 3 = 2. Vìthế, nghiệm duy nhất của hệ thức truy hồi này và các điều kiện ban đầuđã cho là dãy {an} với an = 1  2n + 2.3n. 232.6. QUAN HỆ CHIA ĐỂ TRỊ.2.6.1. Mở đầu: Nhiều thuật toán đệ quy chia bài toán với các thông tin vào đã chothành một hay nhiều bài toán nhỏ hơn. Sự phân chia này được áp dụngliên tiếp cho tới khi có thể tìm được lời giải của bài toán nhỏ một cáchdễ dàng. Chẳng hạn, ta tiến hành việc tìm kiếm nhị phân bằng cách rútgọn việc tìm kiếm một phần tử trong một danh sách tới việc tìm phần tửđó trong một danh sách có độ dài giảm đi một nửa. Ta rút gọn liên tiếpnhư vậy cho tới khi còn lại một phần tử. Một ví dụ khác là thủ tục nhâncác số nguyên. Thủ tục này rút gọn bài toán nhân hai số nguyên tới baphép nhân hai số nguyên với số bit giảm đi một nửa. Phép rút gọn nàyđược dùng liên tiếp cho tới khi nhận được các số nguyên có một bit.Các thủ tục này gọi là các thuật toán chia để trị.2.6.2. Hệ thức chia để trị: Giả sử rằng một thuật toán phân chia một bài toán cỡ n thành a nbài toán nhỏ, trong đó mỗi bài toán nhỏ có cỡ (để đơn giản giả sử b nrằng n chia hết cho b; trong thực tế các bài toán nhỏ thường có cỡ [ ] b nhoặc ] [). Giả sử rằng tổng các phép toán thêm vào khi thực hiện bphân chia bài toán cỡ n thành các bài toán có cỡ nhỏ hơn là g(n). Khiđó, nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho thì fthỏa mãn hệ thức truy hồi sau: 24 n f(n) = af( ) ...