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: Phần V & VI - GVC ThS.Võ Minh Đức

Chia sẻ: Vo Minh Duc | Ngày: | Loại File: PPTX | Số trang:26

Thêm vào BST
Báo xấu
588
lượt xem 63
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 trình bày về hệ thức truy hồi và quan hệ chia để trị trong Toán rời rạc. Tài liệu giúp các bạn củng cố thêm kiến thức về Toán rời rạc là nền tảng cho việc học nhiều môn khoa học tự nhiên sau này.

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 V & VI - GVC ThS.Võ Minh Đức

  1. TOÁN RỜI RẠC CH1: Hãy cho một ví dụ về định nghĩa đệ  quy? 1. Định nghĩa giai thừa của n: n! = n * (n­1)! 2. Lũy thừa nguyên của một số: an = a * an­1 CH2: Có thể ĐN hai khái niệm trên không  dùng đệ quy được không? 25/08/2014 GVC, ThS.Võ Minh Đức 1
  2. TOÁN RỜI RẠC CH1: Đọc giá trị của dãy số gồm các giai  thừa của một số, bắt đầu từ 0: 0, 1, 2, 6, 12, 20,..,n!  a1, a2, a3, a4…an 25/08/2014 GVC, ThS.Võ Minh Đức 2
  3. TOÁN RỜI RẠC 1. Định nghĩa 1:  V. Hệ  thức  truy  hồi  đối  với  dãy  số  Hệ {an}  là  công  thức  biểu  diễn  an  qua  thức một hay nhiều số hạng đi trước của  dãy. Dãy số được gọi là lời giải hay  truy nghiệm  của  hệ  thức  truy  hồi  nếu  hồi các  số  hạng  của  nó  thỏa  mãn  hệ  thức truy hồi này. 25/08/2014 GVC, ThS.Võ Minh Đức 3
  4. TOÁN RỜI RẠC CÁC VÍ DỤ Ví  dụ  1(Lãi  kép):  Giả  sử  một  người  gửi 10.000 đô la vào tài khoản của mình  V. tại  một  ngân  hàng  với  lãi  suất  kép  11%  Hệ mỗi  năm.  Sau  30  năm  anh  ta  có  bao  thức nhiêu tiền trong tài khoản của mình? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 4
  5. TOÁN RỜI RẠC GIẢI Gọi  Pn  là  tổng  số  tiền  có  trong  tài  khoản  sau  n  năm.  Vì  số  tiền  có  trong  tài khoản sau n năm bằng số có sau n  V. ­  1 năm cộng lãi suất của năm thứ n,  Hệ nên ta thấy dãy {Pn} thoả mãn hệ thức  thức truy hồi sau:    truy Pn = Pn­1 + 0,11Pn­1 = (1,11)Pn­1 với  điều  kiện  đầu  P0  =  10.000  đô  la.  hồi Từ đó suy ra Pn = (1,11)n.10.000.  Thay  n  =  30  cho  ta  P30  =  228922,97  đô la. 25/08/2014 GVC, ThS.Võ Minh Đức 5
  6. TOÁN RỜI RẠC VÍ DỤ 2 Tìm  hệ  thức  truy  hồi  và  cho  điều  kiện  đầu để tính số các xâu nhị phân độ dài  V. n và không có hai số 0 liên tiếp.  Hệ Có bao nhiêu xâu nhị phân như thế có  thức độ dài bằng 5? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 6
  7. TOÁN RỜI RẠC GIẢI Gọi  an  là  số  các  xâu  nhị  phân  (np)  độ dài n và không có hai số 0 liên tiếp.  V. Ta có: Hệ Số các xâu np độ dài n và không có hai  số 0 liên tiếp (an) = số các xâu np như  thức thế  kết  thúc  bằng  số  1  (bn)  +  số  các  truy xâu np như thế kết thúc bằng số 0 (cn). hồi Vậy an = bn + cn  (1) 25/08/2014 GVC, ThS.Võ Minh Đức 7
  8. TOÁN RỜI RẠC GIẢI Giả sử n ‡  3. *  bn  chính  là  số  xâu  np  như  thế,  độ  dài  n  ­   1  và  thêm  số  1  vào  cuối  của  V. chúng. Hỏi có tất cả là bao nhiêu xâu? Hệ có tất cả là an­1xâu. thức Vậy bn = ? * cn  là số các xâu np có bit thứ n ­  1  truy bằng 1, nếu không thì chúng có hai số 0  hồi ở  hai  bit  cuối  cùng.  Hỏi  có  tất  cả  là  bao  nhiêu xâu như thế ? có tất cả là an­2 xâu. Vậy cn = ? 25/08/2014 GVC, ThS.Võ Minh Đức 8
  9. TOÁN RỜI RẠC GIẢI Vậy: an = an­1 + an­2   với n ‡  3. V. Hệ •  n = 1 ta có 2 xâu: 0, 1.  Vậy: a1 = 2  thức •  n = 2, ta có 3 xâu: ???.  truy Vậy a2 = 3 hồi Khi đó a5 = a4 + a3 = a3 + a2 + a3         = 2(a2 + a1) + a2 = 13. 25/08/2014 GVC, ThS.Võ Minh Đức 9
  10. TOÁN RỜI RẠC 2. Giải các hệ thức truy hồi. Định nghĩa 2: Một hệ thức truy hồi V. tuyến tính thuần nhất bậc k là hệ Hệ thức truy hồi có dạng: thức an = c1an-1 + c2an-2 + ... + ckan-k truy trong đó c1, c2, ..., ck là các số thực và ck  0. hồi 25/08/2014 GVC, ThS.Võ Minh Đức 10
  11. Hệ thức truy hồi 2. Là tuyến tính vì vế phải của nó là Giải tổng các tích của các số hạng trước các nhân với một hệ số hệ Là thuần nhất vì các số hạng đều là thức ai và hệ số đều là hằng số. truy Có bậc k vì an được biểu diễn qua k hồi. số hạng đứng trước nó. 25/08/2014 GVC, ThS.Võ Minh Đức 11
  12. Hệ thức truy hồi Pn = (1,11)Pn-1 là tuyến tính bậc 2. nhất Giải an = an-1+ an-2 là tuyến tính thuần nhất bậc 2. các an = an-5 là tuyến tính thuần nhất hệ bậc 5. thức Cho ví dụ một hệ thức không phải là truy hệ thức truy hồi? a0 = 3; a1 = 10 hồi. an = an-1 + (an-4)2 25/08/2014 GVC, ThS.Võ Minh Đức 12
  13. an = rn, (r là hằng số) là nghiệm của 2. hệ thức truy hồi Giải an = c1an-1 + c2an-2 + ... + ckan-k các  rn = c1rn-1 + c2rn-2 + ... + ckrn-k hệ Hay rk  c1rk-1  c2rk-2 … ck-1r – ck thức truy = 0. hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 13
  14. Phương trình: 2. rk - c1rk-1 - c2rk-2 - ... Ck-1r - ck = 0 Giải được gọi là phương trình đặc trưng các hệ của hệ thức truy hồi an  =  c1an­1  +  thức c2an­2 +  ... + ckan­k, nghiệm của nó truy gọi là nghiệm đặc trưng của hệ thức hồi. truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 14
  15. Mệnh đề  Cho c1, c2, ..., ck là các số thực. Giả sử rằng 2. phương trình đặc trưng: Giải rk - c1rk-1 - c2rk-2 - ... ck-1r - ck = 0 có k nghiệm phân biệt r1, r2, ..., rk. các Khi đó dãy {an} là nghiệm của hệ thức truy hệ hồi an = c1an-1 + c2an-2 + ... + ckan-k thức khi và chỉ khi truy an = 1r1n + 2r2n + ... + krkn, với n = 1, 2, ... trong đó 1, 2, ..., k là các hằng số. hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 15
  16. Ví dụ Tìm công thức hiển của các số Fibonacci. Dãy số Fibonacci thỏa mãn hệ thức: 2. an = an-1 + an-2 (với đk đầu a0 = 0, a1 = 1). Giải k = 2, c1 = 1, c2 = 1 các Phương trình đặc trưng là: r2 – r – 1 = 0 hệ Có các nghiệm là = 1 + 5 và r2 = 1 − 5 r1 : thức 2 2 truy Do đó các số Fibonacci được cho bởi công hồi. thức: 1+ 5 n 1− 5 n an = α1 ( ) +α2 ( ) 2 2 25/08/2014 GVC, ThS.Võ Minh Đức 16
  17. Ví dụ Tìm công thức hiển của các số Fibonacci. 2. 1+ 5 n 1− 5 n an = α 1 ( ) + α2 ( ) (1) 2 2 Giải các Với các điều kiện đầu: a0 = 0 và a1 = 1. hệ Từ (1). Ta có: α1+ α2 = 0 = a0 1+ 5 1− 5 thức a1 = 1 = α1 ( ) +α2 ( ) 2 2 truy Từ 2 phương trình trên, ta được: hồi. 5 − 5 α1 = ,α 2 = 5 5 25/08/2014 GVC, ThS.Võ Minh Đức 17
  18. Ví dụ Tìm công thức hiển của các số Fibonacci. 2. Do đó các số Fibonacci được cho bởi công Giải thức hiển sau: các 5 1+ 5 n 5 1− 5 n an = ( ) − ( ) 5 2 5 2 hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 18
  19. Hãy tìm nghiệm của hệ thức truy hồi an = 6an-1 - 11an-2 + 6an-3 với điều kiện ban đầu a0 = 2, a1 = 5 và a2 = 15. 2. Giải các hệ thức truy hồi. 25/08/2014 GVC, ThS.Võ Minh Đức 19
  20. VI. QUAN HỆ CHIA ĐỂ TRỊ Chơi trò chơi đoán số: 1. Em  hãy  nghĩ  trong  đầu  một  số  lớn  hơn  100  và  nhỏ hơn 200 (gọi SV). 2. Số em nghĩ là 150 (nhỏ hơn hoặc lớn hơn) … Đây chính là bài toán chia để trị 25/08/2014 GVC, ThS.Võ Minh Đức 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