Bài giảng Toán rời rạc: Công thức truy hồi - Trần Vĩnh Đức

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

76
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Công thức truy hồi cung cấp cho người học những nội dung kiến thức như: Công thức truy hồi, công thức truy hồi và hàm sinh, số Catalan, công thức truy hồi tuyến tính. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Công thức truy hồi - Trần Vĩnh Đức

Công thức truy hồi Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 45
Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví dụ Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ. Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao nhiêu? { an = 2an−1 a0 = 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 / 45
Bài tập Hãy tìm công thức tường minh cho dãy { an = 2an a0 = 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 45
Ví dụ Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi bước? S1 = 1 S2 = 2 Sn+2 = Sn+1 + Sn với n≥1 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 45
Ví dụ Có bao nhiêu xâu nhị phân độ dài n không chứa hai bit 0 liên tiếp?   an+1 = an + an−1 a1 = 2   a2 = 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 45
Bài tập Hãy dùng kỹ thuật hàm sinh để tìm công thức tường minh cho dãy   an+1 = an + an−1 a1 = 2   a2 = 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 45
Ví dụ Có bao nhiêu xâu tam phân độ dài n không chứa dãy con ”012”?   an+3 = 3an+2 − an a1 = 3   a2 = 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 45
Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính CuuDuongThanCong.com https://fb.com/tailieudientucntt
Công thức truy hồi Định nghĩa Công thức truy hồi đối với dãy số ⟨an ⟩ là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 45
Ví dụ Xét dãy số ⟨an ⟩ thỏa mãn công thức { an = an−1 − an−2 a0 = 3a1 = 5 Từ công thức truy hồi ta có a2 = a1 − a0 = 5 − 3 = 2 a3 = a2 − a1 = 2 − 5 = −3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 45
Định nghĩa Một dãy số được gọi là nghiệm của công thức truy hồi nếu các số hạng của nó thỏa mãn công thức truy hồi này. CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 45
Ví dụ ▶ Xét công thức truy hồi an = 2an−1 − an−2 với n ≥ 2. ▶ Dãy số ⟨an ⟩ với an = 3n có phải là nghiệm của hệ thức truy hồi trên hay không? ▶ Còn dãy an = 2n ? ▶ Còn dãy an = 5? CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 45
Ví dụ Giả sử một người gửi 10, 000 đô la vào tài khoản của mình tại một ngân hàng với lãi kép 11% mỗi năm. Hỏi sau 30 năm anh ta có bao nhiêu tiền trong tài khoản ngân hàng. { Pn = Pn−1 + 0.11Pn−1 = 1.11Pn−1 P0 = 10, 000 đô la. CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 45
Ví dụ ▶ Một hệ máy tính coi một xâu các chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số chẵn chữ số 0. ▶ Chẳng hạn, 1230407869 là hợp lệ, còn 120987045608 là không hợp lệ. ▶ Giả sử an là số các từ mã độ dài n. ▶ Hãy tìm công thức truy hồi cho an . an = 9an−1 + (10n−1 − an−1 ) = 8an−1 + 10n−1 . CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 45
e get four regions—that is, a2 = 4. See Figure 7.2a. From Figure 7.2b, we see that = 7. The skeptical reader may ask: how do we know that three intersecting lines ll always Ví create dụ seven regions? Let us go back one step, then. Clearly two intersecting lines will always yield four regions, as shown in Figure 2a. Now ▶ Chúng let us ta vẽthe examine n effect đườngofthẳng trênthe drawing giấy saoline third cho(labeled mọi cặp“3”đường in Figure 2b). It must cross thẳngeach đềuofcắtthenhau othervàtwo lines có không (at ba different đườngpoints). thẳng Before, nào đồngbetween, d after thesequy. two intersection points, the third line cuts through three of the regions rmed by the ▶ Các two first linesthẳng đường (this action of the này chia mặtthird linethành phẳng does not baodepend nhiêuon how it is miền? awn, just that it intersects the other two lines). So in severing three regions, the third e must form three new regions, actually creating six new regions out of three old gions. Thus a3 = a2 + 3 = 4 + 3 = 7, independently of how the third line is drawn. 2 2 3 2 3 4 1 1 1 gure 7.2 (a) (b) (c) CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 45
Ví dụ (Chọn không lặp) Đặt an,k là số cách chọn tập con k phần tử từ tập n phần tử. Hãy tìm công thức truy hồi cho ak,n . an,k = an−1,k + an−1,k−1 (Đẳng thức Pascal) CuuDuongThanCong.com https://fb.com/tailieudientucntt 17 / 45
Ví dụ (Bỏ bóng) Hãy tìm công thức truy hồi cho số cách bỏ n quả bóng giống nhau và k chiếc hộp phân biệt sao cho mỗi hộp chỉ có 2 hoặc 3 hoặc 4 quả bóng. an,k = an−2,k−1 + an−3,k−1 + an−4,k−1 . CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 45
Ví dụ (Hệ thức truy hồi) Tìm công thức truy hồi cho: Số xâu tam phân độ dài n với một số chẵn 0 và một số lẻ 1. an = bn−1 + cn−1 + an−1 bn = 3n−1 − cn−1 cn = 3n−1 − bn−1 CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 45
Nội dung Ví dụ Công thức truy hồi Công thức truy hồi và hàm sinh Số Catalan Công thức truy hồi tuyến tính CuuDuongThanCong.com https://fb.com/tailieudientucntt