Bài giảng Toán rời rạc - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông)

Chia sẻ: Bạch Nhược Đông | Ngày: | Loại File: PPTX | Số trang:92

Thêm vào BST

Báo xấu

25
lượt xem 2
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 - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông) cung cấp cho học viên những kiến thức về định nghĩa hệ thức đệ quy, 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, hệ thức đề qui tuyến tính không thuần nhất,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

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 - Phần 4: Hệ thức đệ quy (TS. Nguyễn Viết Đông)

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