intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Bài 3 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST
Báo xấu
138
lượt xem 16
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 3 "Kỹ thuật đếm nâng cao" thuộc bài giảng Toán rời rạc giới thiệu đến các bạn những nội dung: Một số khái niệm, mô hình hóa, định nghĩa, phương pháp đếm nâng cao, phương pháp thế, phương trình đặc trư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: Bài 3 - TS. Nguyễn Văn Hiệu

  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} an = 2 an-1 Xác định số hạng 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 = ___________________  a = 5 với mọi n nguyên không âm, có là lời giải của hệ n thức truy hồi a = 2a – a với n = 2, 3, 4, …hay không? n n-1 n-2  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 H n  2H n1  1, n  2; H1  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) Th Đôi Đôi tái tạo Đôi thỏ con Đôi Tổ án thỏ (từ hai tháng tuổi) (dưới hai tháng tuổi) g tái tạo ng con Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2