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

Cấu trúc dữ liệu - Phần 7

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:0

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

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 7 Phương pháp quy hoạch động

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu - Phần 7

  1. Phương pháp quy hoạch động (dynamic programming) GVGD: Trương Phước Hải
  2. Nội dung 1. Nguyên lý quy hoạch động 2. Công thức truy hồi 3. Phương pháp quy hoạch động 4. Một số bài toán ứng dụng Trương Phước Hải 2
  3. Nguyên lý quy hoạch động  Chia để trị là phương pháp chủ đạo trong việc thiết kế các thuật toán có tính chất đệ quy  Chia để trị phân nhỏ bài toán và giải quyết độc lập từng phần một cách đệ quy  Tư tưởng đệ quy dễ hiểu và dễ cài đặt nhưng tiêu tốn nhiều bộ nhớ (stack lưu trữ các lời gọi) Trương Phước Hải 3
  4. Nguyên lý quy hoạch động  Xét bài toán Tìm phần tử thứ N của dãy Fibonacci  Dãy được định nghĩa FN = FN-1 + FN-2 với F0 = F1 = 1   Giải bằng phương pháp chia để trị Chia: Fn được chia thành FN-1 và FN-2  Trị: tính FN-1 và FN-2 một cách đệ quy  Gộp: tính tổng FN-1 + FN-2 để được FN  Trương Phước Hải 4
  5. Nguyên lý quy hoạch động  Giải thuật chia để trị cho bài toán F(N) If (N = 0) Or (N = 1) Then Return 1 End If Return F(N - 1) + F(N - 2) End F Trương Phước Hải 5
  6. Nguyên lý quy hoạch động  Minh họa sơ đồ giải bài toán tính F(5) 8 F(5) 5 3 F(4) F(3) 3 2 2 1 F(3) F(2) F(2) F(1) 2 1 1 1 1 1 F(2) F(1) F(1) F(0) F(1) F(0) 1 1 F(1) F(0) Trương Phước Hải 6
  8. Nguyên lý quy hoạch động  Xây dựng lời giải của một bài toán thông qua lời giải của các bài toán con  Các bài con tiếp tục được chia nhỏ để giải quyết nhưng không sử dụng kỹ thuật đệ quy  Sử dụng bảng tra cứu để lưu lại kết quả đã tính được và tính dần đến nghiệm của bài toán bằng một công thức xác định Trương Phước Hải 8
  9. Nội dung 1. Nguyên lý quy hoạch động 2. Công thức truy hồi 3. Phương pháp quy hoạch động 4. Một số bài toán ứng dụng Trương Phước Hải 9
  10. Công thức truy hồi  Trong quá trình quay lui, đệ quy sẽ gọi lại nhiều lần các bài toán con đã được gọi ở các bước trước Gây tiêu tốn thời gian thực hiện lặp lại và tài nguyên bộ  nhớ Lưu trữ nghiệm của tất cả bài toán con và kết hợp chúng  theo một công thức xác định để tìm nghiệm cho bài toán ban đầu  Công thức kết hợp nghiệm của các bài toán con để tìm nghiệm của bài toán lớn hơn gọi là công thức truy hồi Trương Phước Hải 10
  11. Công thức truy hồi  Ví dụ 1 Xét lại bài toán tìm phần tử thứ N của dãy Fibonacci   Giải bài toán ở một cách nhìn khác Sử dụng bảng tra lưu lại giá trị các số Fibonacci nhằm tính  dần cho các số Fibonacci tiếp theo Trương Phước Hải 11
  12. Công thức truy hồi  Tạo mảng lưu kết quả để tra cứu Gọi F[i] là giá trị của phần tử Fibonacci thứ i, vậy phần tử  thứ N của dãy Fibonacci là F[N]. Ta có F[0] = F[1] = 1  Công thức truy hồi  F[i] = F[i-1] + F[i-2], với 2 ≤ i ≤ N  ? ? 1 1 ? ? ... ? ? 0 1 2 3 … N Trương Phước Hải 12
  13. Công thức truy hồi  Giải thuật sử dụng công thức truy hồi với độ phức tạp O(N) Fibonacci(N) F[0] = 1 F[1] = 1 For (i = 2; i
  14. Công thức truy hồi  Cài đặt ngôn ngữ int Fibonacci(int N) { int F[MAX]; F[0] = F[1] = 1; for (int i = 2; i
  17. Công thức truy hồi  Minh họa quá trình xây dựng bảng để tính C[N][k] 0 1 2 3 4 5 0 1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 2 1 3 3 1 0 0 3 1 4 6 4 1 0 4 1 5 10 10 5 1 5 1 Trương Phước Hải 17
  18. Công thức truy hồi  Giải thuật sử dụng bảng tra cứu độ phức tạp O(n2) ToHop(N, k) For (j = 0; j
  19. Công thức truy hồi  Cài đặt ngôn ngữ int ToHop(int N, int k) { for (int i = 0; i
  20. Nội dung 1. Nguyên lý quy hoạch động 2. Công thức truy hồi 3. Phương pháp quy hoạch động 4. Một số bài toán ứng dụng Trương Phước Hải 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