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

Bài giảng môn Thuật toán ứng dụng: Chia để trị

Chia sẻ: Dương Hoàng Lạc Nhi | Ngày: | Loại File: PDF | Số trang:31

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

Bài giảng Thuật toán ứng dụng: Chia để trị. Chương này cung cấp cho học viên những nội dung về: tổng quan chia để trị; ví dụ minh họa; độ phức tạp chia để trị; sắp xếp trộn; giảm để trị;... Mời các bạn cùng tham khảo chi tiết nội dung bài giả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 môn Thuật toán ứng dụng: Chia để trị

  1. THUẬT TOÁN ỨNG DỤNG CHIA ĐỂ TRỊ Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1
  2. NộI dung  Tổng quan chia để trị  Ví dụ minh họa  Độ phức tạp chia để trị  Giảm để trị 2
  3. Tổng quan chia để trị  Chia bài toán cần giải ban đầu thành các bài toán con độc lập nhau  Giải (trị) các bài toán con  Tổng hợp lời giải của các bài toán con để dẫn ra lời giải của bài toán xuất phát 3
  4. Ví dụ minh họa  Bài toán dãy con dài nhất: cho dãy số nguyên a = a1, a2, …, an. Tìm dãy con gồm một số liên tiếp các phần tử có tổng lớn nhất  Phân chia: ký hiệu P(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj có tổng cực đại  Tổng hợp lời giải  Ký hiệu PL(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj sao cho phần tử cuối cùng là aj có tổng cực đại  Ký hiệu PR(i, j) là lời giải của bài toán tìm dãy con liên tiếp của dãy ai, ai+1,…, aj sao cho phần tử đầu tiên là ai có tổng cực đại 4
  5. Ví dụ minh họa  Xét đoạn [l,l+1,...,r]. Ký hiệu m = (l+r)/2  P(l,r) = MAX{P(l, m), P(m+1,r), PL(l,m) + PR(m+1,r)} l P(l,m) P(m+1,r) r m m+1 PL(l,m) PR(m+1,r) 5
  6. Ví dụ minh họa #include using namespace std; #define INF 1e9 #define MAX 1000000 int a[MAX]; int n; void input(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; } 6
  7. Ví dụ minh họa int PL(int l, int r){ int rs = -INF; int s = 0; for(int i = r; i >= l; i--){ s += a[i]; rs = max(rs,s); } return rs; } int PR(int l, int r){ int rs = -INF; int s = 0; for(int i = l; i
  8. Ví dụ minh họa int P(int l, int r){ if(l == r) return a[r]; int m = (l+r)/2; return max(max(P(l,m),P(m+1,r)), PL(l,m)+PR(m+1,r)); } void solve(){ cout
  9. Độ phức tạp tính toán  Chia bài toán xuất phát thành a bài procedure D-and-C(n) { toán con, mỗi bài toán con kích 1. if(n  n0) thước n/b 2. xử lý trực tiếp  T(n): thời gian của bài toán kích 3. else{ thước n 4. chia bài toán xuất phát  Thời gian phân chia (dòng 4): D(n) thành a bài toán con kích thước  Thời gian tổng hợp lời giải (dòng 6): n/b C(n) 5. gọi đệ quy a bài toán con  Công thức truy hồi: 6. tổng hợp lời giải 7. } Q 1 , ≤ 0 T = } + + , > 0 9
  10. Độ phức tạp tính toán  Độ phức tạp của thuật toán chia để trị (định lí thợ)  Công thức truy hồi: T(n) = aT(n/b) + cnk, với các hằng số a  1, b > 1, c > 0  Nếu a > bk thì T(n) = Q( )  Nếu a = bk thì T(n) = Q( ) với logn =  Nếu a < bk thì T(n) = Q( ) 10
  11. Độ phức tạp tính toán  Độ phức tạp của thuật toán chia để trị (định lí thợ)  Công thức truy hồi: T(n) = aT(n/b) + cnk, với các hằng số a  1, b > 1, c > 0  Nếu a > bk thì T(n) = Q( )  Nếu a = bk thì T(n) = Q( ) với logn =  Nếu a < bk thì T(n) = Q( )  Thuật toán chia để trị giải bài toán tổng con cực đại có độ phức tạp là O(nlogn) 11
  12. Sắp xếp trộn  Phân chia: Chia dãy a1, …, an thành 2 dãy con có độ dài bằng nhau  Trị đệ quy: Sắp xếp 2 dãy con bằng thuật toán sắp xếp trộn  Tổng hợp: Trộn 2 dãy con đã được sắp với nhau để thu được dãy ban đầu được sắp thứ tự 12
  13. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 13
  14. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 14
  15. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 15
  16. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 4 16
  17. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 4 5 17
  18. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 4 5 8 18
  19. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 4 5 8 9 19
  20. Sắp xếp trộn  Trộn hai dãy đã được sắp xếp thành dãy mới được sắp xếp i j a 1 3 8 9 20 4 5 10 11 23 k ta 1 3 4 5 8 9 10 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