TAILIEUCHUNG - Bài giảng môn Toán rời rạc - Chương 4: Hệ thức đệ quy

Bài giảng môn Toán rời rạc - Chương 4: Hệ thức đệ quy, cung cấp những kiến thức như Giới thiệu; Hệ thức đệ quy tuyến tính với hệ số hằng; nghiệm của hệ thức đệ quy tuyến tính thuần nhất; nghiệm của hệ thức đệ quy tuyến tính không thuần nhất. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC Chương 4 HỆ THỨC ĐỆ QUY Toán Rời Rạc Chương 4. Hệ thức đệ quy O c 2020 LVL 1 33 Nội dung Chương 4. HỆ THỨC ĐỆ QUY 1. Giới thiệu 2. Hệ thức đệ quy tuyến tính với hệ số hằng 3. Nghiệm của hệ thức đệ quy tuyến tính thuần nhất 4. Nghiệm của hệ thức đệ quy tuyến tính không thuần nhất Toán Rời Rạc Chương 4. Hệ thức đệ quy O c 2020 LVL 2 33 . Giới thiệu Ví dụ. Tháp Hà Nội Có 3 cọc A B C và n đĩa với đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu cả n đĩa được đặt chồng lên nhau ở cọc A hai cọc B và C để trống. Vấn đề đặt ra là chuyển cả n đĩa ở cọc A sang cọc C có thể qua trung gian cọc B mỗi lần chỉ chuyển được một đĩa. Ta gọi xn là số lần chuyển đĩa tìm xn Toán Rời Rạc Chương 4. Hệ thức đệ quy Oc 2020 LVL 3 33 Giải. Với n 1 ta có x1 1. Với n gt 1 trước hết ta chuyển n 1 đĩa bên trên sang cọc B qua trung gian cọc C giữ nguyên đĩa thứ n dưới cùng ở cọc A . Số lần chuyển n 1 đĩa đó là xn 1 . Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng ta chuyển n 1 đĩa từ cọc B sang cọc C cọc A làm trung gian . Số lần chuyển n 1 đĩa đó lại là xn 1 . Như vậy số lần chuyển toàn bộ n đĩa từ A sang C là xn 1 1 xn 1 2xn 1 1. Nghĩa là x1 1 xn 2xn 1 1 với n gt 1 Toán Rời Rạc Chương 4. Hệ thức đệ quy O c 2020 LVL 4 33 Ví dụ. Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm xn Giải. Với n 1 ta có x1 1. Với n 2 ta có x2 2. Với n gt 2 để khảo sát xn ta chia thành hai trường hợp loại trừ lẫn nhau Trường hợp 1. Bước đầu tiên gồm 1 bậc. Khi đó cầu thang còn n 1 bậc nên số cách đi hết cầu thang là xn 1 . Trường hợp 2. Bước đầu tiên gồm 2 bậc. Khi đó cầu thang còn n 2 bậc nên số cách đi hết cầu thang trong là xn 2 . Theo nguyên lý cộng số cách đi hết cầu thang là xn 1 xn 2 . Do đó ta có xn xn 1 xn 2 Như vậy x1 1 x2 2 xn xn 1 xn 2 với n gt 2. Toán Rời Rạc Chương 4. Hệ thức đệ quy O c 2020 LVL 5 33 . Hệ thức đệ quy tuyến tính với hệ số hằng Định nghĩa. Một hệ thức đệ

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Hệ thức đệ quy
• Hệ thức đệ quy tuyến tính thuần nhất
• Giải hệ thức đệ quy
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc