- Trang Chủ
- Toán học
- Bài giảng Toán rời rạc - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông)
Xem mẫu
- Phần IV
Hệ thức đệ quy
Biên soạn:
TS.Nguyễn Viết Đông
1
- Tài liệu tham khảo
[1] TS. Trần Ngọc Hội, Toán rời rạc
[2] GS.TS. Nguyễn Hữu Anh, Toán rời rạc,
Nhà xuất bản giáo dục.
[3] Nguyễn Viết Hưng’s Slides
2
- Định nghĩa
Moät heä thöùc ñeä qui tuyeán tính caáp
k laø moät
heä thöùc coù daïng:
xn = a1xn1 +… + akxnk + fn (1)
trong ñoù :
•
ak 0, a1,…, ak-1 laø caùc heä soá
thöïc
•
{fn} laø moät daõy soá thöïc cho
3
tröôùc
- Định nghĩa
Tröôøng hôïp daõy fn= 0 vôùi moïi
n thì (1) trôû
thaønh:
xn = a1xn-1 +… +akxn-k (2)
Ta noùi (2) laø moät heä thöùc ñeä
qui tuyeán tính
thuaàn nhaát caáp k
4
- Nghiệm tổng quát
Ø
Moãi daõy {xn} thoûa (1) ñöôïc
goïi laø moät nghieäm cuûa (1).
• Nhaän xeùt raèng moãi nghieäm
{xn} cuûa (1) ñöôïc hoaøn toaøn
xaùc ñònh bôûi k giaù trò ban ñaàu
x0, x1,…, xk-1.
Ø
Hoï daõy soá { xn = xn(C1, C2,
…,Ck)} phuï thuoäc vaøo k hoï
tham soá C1, C2,…,Ck ñöôïc goïi
laø nghieäm toång quaùt cuûa (1)
neáu moïi daõy cuûa hoï 5
naøy
ñeàu laø nghieäm cuûa (1)
- Nghiệm riêng
Cho {xn} là nghiệm tổng quát của (1) và vôùi
moïi k
giaù trò ban ñaàu y0, y1,…, yk-1, toàn taïi
duy nhaát caùc
giaù trò cuûa k tham soá C1, C2,…,Ck
sao cho nghieäm
{xn} töông öùng thoûa:
x0 = y0, x1 = y1,…, xk-1 = yk-1
(*)
Khi ñoù, nghieäm {xn} töông öùng ñöôïc
6
goïi nghieäm
- Mục đích giải hệ thức đệ qui
•
Giaûi moät heä thöùc ñeä qui laø ñi
tìm nghieäm toång quaùt cuûa
noù.
•
Neáu heä thöùc ñeä qui coù
keøm theo ñieàu kieän ban ñaàu,
ta phaûi tìm nghieäm rieâng thoûa
ñieàu kieän ban ñaàu ñoù.
7
- Fibonacci (11701250)
8
- Một số ví dụ
Ví dụ 1(Dãy Fibonacci)
Bài toán:Một đôi thỏ(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 diễn.Tính Fn là số đôi thỏ có
ở tháng n?
9
- Một số ví dụ
Giải:
Tháng đầu tiên và tháng thứ 2 chỉ có
mộtđôithỏ.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 = Fn1+Số đôi thỏ được sinh ra ở tháng thứ n.
Do các đôi thỏ được sinh ra ở tháng thứ n1 chưa
đẻ con ở tháng thứ n , và ở tháng này mỗi đôi thỏ
có ở tháng n2 sẽ đẻ ra được một đôi thỏ con nên
số 10
- Một số ví dụ
Như vậy việc giải bài toán Fobonacci 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 = Fn1+Fn2 với n >2.
11
- Một số ví dụ
Ví dụ2: Moät caàu thang coù n baäc.
Moãi böôùc ñi goàm 1 hoaëc 2 baäc.
Goïi xn laø soá caùch ñi heát caàu
thang. Tìm moät heä thöùc ñeä qui
cho xn
12
- Một số ví dụ
Vôùi n = 1, ta coù x1 = 1.
Vôùi n = 2, ta coù x2 = 2
Vôùi n > 2, ñeå khaûo saùt xn ta chia thaønh
hai tröôøng hôïp loaïi tröø laãn nhau:
Tröôøng hôïp 1: Böôùc ñaàu tieân goàm 1 baäc.
Khi ñoù, caàu thang coøn n-1 baäc neân soá
caùch ñi heát caàu thang trong tröôøng hôïp
naøy laø xn-1.
13
- Ví dụ
Tröôøng hôïp 2: Böôùc ñaàu tieân goàm 2
baäc.
Khi ñoù, caàu thang coøn n-2 baäc neân
soá caùch ñi heát caàu thang trong
tröôøng hôïp naøy laø xn-2.
Theo nguyeân lyù coäng, soá caùch ñi
heát caàu thang laø xn-1 + xn-2 . Do
ñoù ta coù:
xn = xn-1 + xn-2
14
- Một số ví dụ
Vaäy ta coù heä thöùc ñeä qui
tuyeán tính thuaàn nhaát caáp 2:
xn = xn−1 + xn−2
x1 = 1, x2 = 2.
15
- Example3: The tower of Hanoi puzzle consists of three
pegs mounted on a board and disks with different sizes.
How can we move the disks to the 2nd peg, following the
rule: larger disks are never placed on top of smaller ones?
16
- How can we move the disks to the 2nd peg, one in a
time,following the rule: larger disks are never placed
on top of smaller ones?
17
- n Let Hn be the minimum number of moves to complete the
puzzle. First we must move the top (n – 1) disks to the 3rd
peg, using at least Hn – 1 moves
18
- § We need one more move to take the largest disk to peg 2
§ Then carry (n – 1) smaller disks from 3rd peg to the 2nd
peg, using at least Hn – 1 moves .
19
- Modeling with Recurrence
Relations
n First, move the top (n – 1) disks to the 3rd peg, using at
least Hn – 1 moves
n one more move to take the largest disk to peg 2
n carry (n – 1) smaller disks from 3rd peg to the 2nd
peg, using at least Hn – 1 moves .
Thus Hn = 2Hn – 1 + 1
n In fact we can prove by induction that
Hn = 2 Hn – 1 + 1
20
nguon tai.lieu . vn
