Xem mẫu
- 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
nguon tai.lieu . vn
