Bài giảng Toán rời rạc - Bài 3: Kỹ thuật đếm nâng cao

Nội dung text: Bài giảng Toán rời rạc - Bài 3: Kỹ thuật đếm nâng cao

1. BÀI 3 KỶ THUẬT ĐẾM NÂNG CAO Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
2. Nhắc lại! Quy tắc nhân Quy tắc cộng HV, CH, TH Chỉnh hợp lặp Tổ hợp lặp Nguyên lý bù trừ 2
3. Nội dung 3.1. Giới thiệu 3.2. Một số khái niệm 3.3. Mô hình hóa 3.4.Định nghĩa 3.5. Phương pháp . Phương pháp thế . Phương trình đặc trưng 3.6. Bài tập Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
4. 3.1. Giới thiệu . Khó định nghĩa đối tượng một cách tường minh . Có thể định nghĩa đối tượng qua chính nó . Kỷ thuật = đệ quy. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
5. 3.1. Giới thiệu • Ví dụ 3.1 • Ví dụ 3.2 10 000$ Một ông 11 % tính gộp già 30 năm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
6. 3.2. Các khái niệm Xác định một hay nhiều số hạng đầu tiên a0 = 5 Đệ quy dãy số {a n} a = 2 a Xác định số hạng n n-1 tiếp theo từ số hạng đi trước Hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
7. 3.2. Các khái niệm Có thể Có thể Có thể Đưa ra phiên bản phiên bản vấn đề đơn giản có đơn giản có phức tạp giải nếu thể được giải nếu giải nếu thể được giải giải an = 2an-1 an-1 = 2an-2, a1 = 2a0, a0=5
8. 3.2. Các khái niệm • Hệ thức truy hồi của {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. • Nghiệm htth là dãy {bn} nếu các số hạng thỏa mản hệ thức truy hồi. • Giải htth là đi tìm công thức biểu diễn các số hạng của dãy mà không thông qua các số hạng phía trước Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
9. 3.2. Các khái niệm . an = 3n với mọi n nguyên không âm, có là lời giải của hệ thức truy hồi an = 2 an-1 – an-2 với n = 2, 3, 4, hay không? . HD: Giả sử an = 3n với mọi n, n ≥ 2; 2an-1 – an-2 = ___ . an = 5 với mọi n nguyên không âm, có là lời giải của hệ thức truy hồi an = 2an-1 – an-2 với n = 2, 3, 4, hay không? . HD 2an-1 – an-2 = ___
10. 3.3. Mô hình hóa hệ thức truy hồi 3.3.1. tổ hợp C(n,k), k ≤ n, 3.3.2. Bài toán tháp Hà nội, 3.3.3. Bài toán họ nhà thỏ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
11. 3.3. Mô hình hóa hệ thức truy hồi 3.3.1. Tính C(n,k) • C(n,k) = ? • Xây dưng Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
12. 3.3. Mô hình hóa hệ thức truy hồi 3.3.1. Tính C(n,k) . Cố định a trong n phần tử . Chia số cách chọn tập con k pt của tập n pt thành 2 lớp: – Lớp chứa a: C(n-1,k-1) – Lớp không chứa a: C(n-1,k) . Nguyên lý cộng C(n,k) = C(n-1,k-1) + C(n-1,k) C(n,0) = C(n,n) =1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
13. 3.3. Mô hình hóa hệ thức truy hồi 3.3.1. Tính C(n,k) . int c(int m,int n) { if(m==0) return 1; else if(m==n) return 1; else return (c(m-1,n-1)+c(m,n-1)); } . Nhược điểm đệ quy Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
14. 3.3. Mô hình hóa hệ thức truy hồi 3.3.2. Bài toán tháp Hà nội • Mô tả bài toán toán: • Cho 3 cái cọc A, B, C và tập n đĩa có kích cỡ khác nhau; • Đĩa được bố trí theo thứ tự đường kính giảm dần từ dưới lên trên • Số đĩa ban đầu được đặt trên cọc A; • Mục đích: xếp được tất cả đĩa lên cọc C Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
15. 3.3. Mô hình hóa hệ thức truy hồi 3.3.2. Bài toán tháp Hà nội • Quy tắc chơi − Mỗi lần chuyển chỉ được chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ lên trên đĩa có đường kính lớn hơn. − Mỗi đĩa có thể chuyển từ cọc này sang cọc khác; − Trong quá trình chuyển được phép sử dụng cọc B làm trung gian. • Bài toán đặt là: Tìm số lần dịch chuyển đĩa ít nhất cần thực hiện để thực hiện xong nhiệm vụ đặt ra trong trò chơi tháp Hà Nôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
16. 3.3. Mô hình hóa hệ thức truy hồi MINH HỌA NGHIỆM Gọi Hn : n đĩa Số lần chuyển n đĩa A B C Vị trí bắt đầu trên tháp Hà Nội n-1 đĩa Chuyển n-1 đĩa ở phần trên sang cọc B A B C Vị trí trung gian trên tháp Hà Nội Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
17. 3.3. Mô hình hóa hệ thức truy hồi MINH HỌA NGHIỆM Chuyễn đĩa lớn nhất sang cọc C 1 đĩa 1 lần chuyển A B C Vị trí trung gian trên Tháp Hà Nội n đĩa Chuyển phần trên n-1 đĩa sang cọc C A B C Hn-1 lần chuyển Vị trí cuối cùng trên Tháp Hà Nội Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
18. 3.3. Mô hình hóa hệ thức truy hồi HHHnn 2 11 1, n 2; 1 Chuyển n-1 đĩa phần Chuyển đĩa lớn nhất Chuyển n-1 đĩa phần trên sang cọc B sang cọc C trên sang cọc C Hn-1 1 Hn-1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
19. void THN(int n,char a, char b, char c){ • Nhập n đưa ra if(n==1) Move(a,b); số lần chuyển else { . Quan tâm số THN(n-1,a,c,b); lần chuyển Move(a,b); . Cách chuyển THN(n-1,c,b,a);} không quan } trọng void Move(char a, char b){ printf("\t%c > %c\n",a,b); }
20. 3.3. Mô hình hóa hệ thức truy hồi 3.3.3. Bài toán họ nhà thỏ (population of rabbits) Đôi Đôi tái tạo Đôi thỏ con Th Đôi Tổ án thỏ (từ hai tháng tuổi) (dưới hai tháng tuổi) tái tạo ng g con Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
21. 3.3. Mô hình hóa hệ thức truy hồi 3.3.3. Bài toán họ nhà thỏ f n = f n-1 + fn-2 , n≥ 3 Số đôi thỏ sau n-1 tháng Số đôi thỏ trên đảo sau n tháng số đôi thỏ mới sinh số đôi thỏ sau n-2 tháng Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
22. 3.4. Định nghĩa • Hệ thức truy hồi tuyến tính thuần nhất bậc k hệ số hằng có dạng: an = c1 an-1 + c2 an-2 + + ck an-k c1, c2, ,ck - hằng số, ck ≠ 0 . • Hệ thức truy hồi bậc k với k giá đầu: a0=I0, a1,= I1 , ,ak-1 = I k-1 sẽ xác định duy nhất một dãy {an} Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
23. 3.4. Định nghĩa • Hệ thức truy hồi tuyến tính thuần nhất có hệ số hằng Pn = (1.11) Pn-1 bậc một 1. Thường xuyên tồn tại trong các mô hình hóa các bài toán fn = fn-1 + fn-2 bậc hai 2. Có thể giải một cách có hệ thống an = an-5 bậc năm • Hệ thưc truy hồi không tuyến tính, không thuần nhất, không hệ số hằng Hn = 2Hn-1 + 1 Không thuần nhất Bn = nBn-1 Không có hệ sô hằng an = an-1 + a²n-2 Không tuyến tính 23
24. 3.5. Phương pháp giải hệ thức truy hồi • Giải hệ thức truy hồi – Tìm công thức tổng quát cho số hạng an – Số hạng an không phải tính qua k phần tử trước nó. • Phương pháp giải: – Phương pháp thế – Phương pháp phương trình đặc trưng Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
25. 3.5. Phương pháp giải hệ thức truy hồi 3. 5.1 Phương pháp thế: • Dùng để giải hệ thức truy hồi bậc 1 • Các bược giải: Thay an bởi an-1 Thay an-1 bởi an-2  Thay a0 bởi I0 • Thu được công thức trực tiếp cho an • Chứng minh tính đúng đắn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25
26. 3.5. Phương pháp giải hệ thức truy hồi 3.5.1. Phương pháp thế: – Gọi Hn là số lần chuyển đĩa ít nhất của bài toán tháp Hà nội. – Hn = 2Hn-1 + 1, n ≥1,với H1 = 1 – HHnn 21 1 2 2 2HHnn 22 1 1 2 2 1 2 3 2 2 2HHnn 33 1 2 1 2 2 2 1 n 1 n 2 n 3 2H1 2 2 2 1 2n 1 2 n 2 2 n 3 2 1 21n Chứng minh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26
27. 3.5. Phương pháp giải hệ thức truy hồi 3.5.2. Phương pháp phương trình đặc trưng – Dùng giải hệ thức truy hồi bậc 2 tuyến tính thuần nhất hệ số hằng. an = c1 an-1 + c2 an-2 , n ≥2 (1) c1, c2- hằng số, c2 ≠ 0 . – Có phương trình đặc trưng: 2 r = c1 r + c2 (2) r - hằng số. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27
28. 3.5. Phương pháp giải hệ thức truy hồi 3.5.2. Phương pháp phương trình đặc trưng  Nếu (2) có hai nghiệm thực phân biệt r1, r2 và có a0 = I0 ,a1 = I1, thì tồn tại duy nhất hằng số d1 , d2: n n an = d1 r 1 + d2 r 2 là nghiệm của (1)  Nếu (2) có nghiệm thực kép r1, có a1 = I0 ,a1 = I1 thì tồn tại duy nhất hằng số d1 , d2: n an = (d1 + d2 n )r 1 là nghiệm của (1) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28
29. 3.5. Phương pháp giải hệ thức truy hồi 3.5.2. Phương pháp phương trình đặc trưng • Cần chứng minh: n n • an = d1 r 1 + d2 r 2 là nghiệm của (1) • tồn tại d1 d2 duy nhất không ? • chứng minh: n n • c1 an-1 + c2 an-2 = d1 r 1 + d2 r 2 với mọi n≥2 • I0 = d1 + d2 • I1 = d1 r1 + d2 r2 Suy ra d1 d2 duy nhất • Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29
30. 3.5. Phương pháp giải hệ thức truy hồi • Bài toán họ nhà thỏ có hệ thức truy hồi an = an-1 + an-2 , n≥2; a0 = 1, a1 = 1 Giải: Bước 1: Tìm nghiệm tổng quát Bước 2: Tìm hệ số hằng Bước 3: Nghiệm của hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30
31. 3.5. Phương pháp giải hệ thức truy hồi Bước 1: Tìm nghiệm tổng quát 2 – Phương trình đặc trưng: r = r +1 – Nghiệm của pt đặc trưng: r1 = (1+√5)/2 , r2 = (1-√5)/2 n n – Nghiệm tổng quát: an = d1((1+√5)/2) + d2 ((1+√5)/2) Bước 2: Tìm hằng số d1 và d2 : – Sử dụng điều kiện đầu: 1 = d1 + d2 1 = d1 (1+√5)/2 + d2 (1+√5)/2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 31
32. 3.5. Phương pháp giải hệ thức truy hồi Bước 2 (t.): d1 = (1+√5) / 2√5 d2 = -(1-√5) / 2√5 Bước 3: Nghiệm của hệ thức truy hồi nn 11 1 1 5 1 1 5 an  ,0 n 55 22 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 32
33. 3.5. Phương pháp giải hệ thức truy hồi Vi dụ 5.1 Giải hệ thức truy hồi sau: an = 6an-1 - 9an-2 , a0= 1, a1= 6. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 33
34. 3.5. Phương pháp giải hệ thức truy hồi • Vi dụ 5.1 – Bước 1: Tìm nghiệm tổng quát 2 • Phương trình đặc trưng: r = 6r -9 • pt đặc trưng có nghiệm kép: r1 = r2 = 3 n • Nghiệm tổng quát: an = (d1 + d2 n ) 3 – Bước 2: Tìm hằng số d1 và d2 • Sử dụng điều kiện đầu: 1 = d1 d1 = 1 6= (d1 + d2) 3 d2 = 1 – Bước 3: Nghiệm của hệ thức truy hồi n an = (1 + n ) 3 , n≥0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 34
35. 3.5. Giải hệ thức truy hồi bậc k ≥ 3  Hệ thức truy hồi tuyến tính thuần nhất bậc k: an = c1 an-1 + c2 an-2 + + ck an-k (*) trong đó, c1, c2, ,ck - hằng số, ck ≠ 0 .  Phương trình đặc trưng: k k-1 k-2 r = c1 r + c2 r + + ck ( ) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35
36. 3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3  Người ta chứng minh đươc kết quả sau:  Nếu (*) có nghiệm thực phân biệt r1 ,r2 , ,rk , thì ( ) có nghiệm tổng quát sau: n n n an d1  r 1 d 2  r 2 d k  r k  Nếu (*) có t nghiệm thực phân biệt r1 ,r2 , ,rt tương ứng với các tính bội m1, m2 , , mt , thì ( ) có nghiệm tổng quát: a ( d d n d nm1 1 )  r n nm10 11 11 1 1 (d d n d nmt 1 )  r n t0 t 1 tmt 1 t Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36
37. 3.5. Giải hệ thức truy hồi bậc k ≥ 3 • Ví dụ 5.2 Giải hệ thức truy hồi sau: an = -3an-1- 3an-2 - an-3, a0 = 1, a1 = -2, a2 = -1. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 37
38. 3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3 • Ví dụ 5.2 Bước 1: Tìm nghiệm tổng quát • Phương trình đặc trưng: r3 = - 3r2 - 3r - 1 • Nghiệm của pt đặc trưng: r1 = r2 = r3 = - 1 2 n • Nghiệm tổng quát: an = (d10 + d11 n + d12 n )(-1) Bước 2: Tìm hằng số d10, d11 và d12 • Sử dụng điều kiện đầu: 1 = d10 , -2 = (d10 + d11 + d12)(-1) , -1 = d10 + d112 + d12 4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 38
39. 3.5. Phương pháp giải hệ thức truy hồi bậc ≥ 3 Ví dụ 5.2 Bước 2 (t.): d10 = 1 d11 = 3 d12 = -2 Bước 3: Nghiệm của hệ thức truy hồi 2 n an = (1 + 3 n - 2 n ) (-1) , n ≥ 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 39
40. 3. 6. Bài tập 1. an = 6an-1 - 11an-2 + 6an-3 , a0 =2, a1 = 5 , a2 = 15. n n • ĐS: an = 1 2 + 2.3 . Nguyễn Văn Hiệu, 2012, Discrete Mathematics 40
41. THAT’S ALL; THANK YOU • WHAT NEXT? BÀI TOÁN TỒN TẠI