Toán học - Bài 3: Kỷ thuật đếm nâng cao

BÀI 3 KỶ THUẬT ĐẾM NÂNG CAO Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn 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 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 3.1. Giới thiệu Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4  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. 3.1. Giới thiệu • Ví dụ 3.1 • Ví dụ 3.2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5 Một ông già 10 000$ 11 % tính gộp 30 năm 3.2. Các khái niệm Xác định một hay nhiều số hạng đầu tiên Xác định số hạng tiếp theo từ số hạng đi trước Đệ quy dãy số {a n} Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6 an = 2 an-1 a0 = 5 Hệ thức truy hồi 3.2. Các khái niệm phiên bản đơn giản có thể được giải phiên bản đơn giản có thể được giải Có thể giải nếu Có thể giải nếu Có thể giải nếu an = 2an-1 an-1 = 2an-2, a1 = 2a0, a0=5 Đưa ra vấn đề phức tạp 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 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 = ___________________ 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 3.3. Mô hình hóa hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11 • C(n,k) = ? • Xây dưng 3.3.1. Tính C(n,k) 3.3. Mô hình hóa hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12 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 3.3. Mô hình hóa hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13 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 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 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 3.3. Mô hình hóa hệ thức truy hồi MINH HỌA NGHIỆM Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16 A B C A B C Vị trí bắt đầu trên tháp Hà Nội Vị trí trung gian trên tháp Hà Nội n đĩa n-1 đĩa Gọi Hn : Số lần chuyển n đĩa Chuyển n-1 đĩa ở phần trên sang cọc B MINH HỌA NGHIỆM Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17 A B C A B C Vị trí trung gian trên Tháp Hà Nội Vị trí cuối cùng trên Tháp Hà Nội 1 đĩa n đĩa Hn-1 lần chuyển Chuyễn đĩa lớn nhất sang cọc C Chuyển phần trên n-1 đĩa sang cọc C 1 lần chuyển 3.3. Mô hình hóa hệ thức truy hồi Chuyển n-1 đĩa phần trên sang cọc B Chuyển đĩa lớn nhất sang cọc C Chuyển n-1 đĩa phần trên sang cọc C Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18 3.3. Mô hình hóa hệ thức truy hồi 1 12 1, n 2; 1n nH H H    Hn-1 1 Hn-1 • Nhập n đưa ra số lần chuyển  Quan tâm số lần chuyển  Cách chuyển không quan trọng void THN(int n,char a, char b, char c){ if(n==1) Move(a,b); else { THN(n-1,a,c,b); Move(a,b); THN(n-1,c,b,a);} } void Move(char a, char b){ printf("\t%c ---> %c\n",a,b); } 3.3.3. Bài toán họ nhà thỏ (population of rabbits) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20 Đôi tái tạo (từ hai tháng tuổi) Đôi thỏ con (dưới hai tháng tuổi) Th án g Đôi tái tạo Đôi thỏ con Tổ ng 3.3. Mô hình hóa hệ thức truy hồi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 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ỏ mới sinh Số đôi thỏ trên đảo sau n tháng số đôi thỏ sau n-2 tháng 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 • 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 fn = fn-1 + fn-2 bậc hai 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 Bn = nBn-1 an = an-1 + a²n-2 23 1. Thường xuyên tồn tại trong các mô hình hóa các bài toán 2. Có thể giải một cách có hệ thống Không thuần nhất Không có hệ sô hằng Không tuyến tính 3.4. Định nghĩa 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 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 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 – Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26     1 2 2 2 2 3 2 3 3 1 2 3 1 1 2 3 2 1 2 2 1 1 2 2 1 2 2 1 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 1 2 1 n n n n n n n n n n n n n H H H H H H H                                          Chứng minh 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: r2 = c1 r + c2 (2) r - hằng số. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 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  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: an = d1 r n 1 + d2 r n 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: an = (d1 + d2 n )r n 1 là nghiệm của (1) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 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 • Cần chứng minh: • an = d1 r n 1 + d2 r n 2 là nghiệm của (1) • tồn tại d1 d2 duy nhất không ? • chứng minh: • c1 an-1 + c2 an-2 = d1 r n 1 + d2 r n 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 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 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 – Phương trình đặc trưng: r2 = r +1 – Nghiệm của pt đặc trưng: r1 = (1+√5)/2 , r2 = (1-√5)/2 – Nghiệm tổng quát: an = d1((1+√5)/2) n + d2 ((1+√5)/2) n 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 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 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 32 1 1 1 1 5 1 1 5 , 0 2 25 5 n n na n                       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 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 • Phương trình đặc trưng: r2 = 6r -9 • pt đặc trưng có nghiệm kép: r1 = r2 = 3 • Nghiệm tổng quát: an = (d1 + d2 n ) 3 n – 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 an = (1 + n ) 3 n , n≥0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 34 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: rk = c1 r k-1 + c2 r k-2 ++ ck (**) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35 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ế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: Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36 1 1 2 2 ... n n n n k ka d r d r d r       1 1 1 10 11 1 1 1 1 0 1 1 ( ... ) ... ( ... )t t m n n m m n t t tm t a d d n d n r d d n d n r                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 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 • Nghiệm tổng quát: an = (d10 + d11 n + d12 n 2 )(-1)n 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 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 an = (1 + 3 n - 2 n 2 ) (-1)n , n ≥ 0 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 39 3. 6. Bài tập 1. an = 6an-1 - 11an-2 + 6an-3 , a0 =2, a1 = 5 , a2 = 15. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 40 • ĐS: an = 1  2 n + 2.3n. • WHAT NEXT? BÀI TOÁN TỒN TẠI THAT’S ALL; THANK YOU