Bài giảng Thuật toán ứng dụng: Bài thực hành số 1.2 - TS. Bùi Quốc Trung, TA. Đặng Xuân Vương

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

Thêm vào BST

Báo xấu

2
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài thực hành "Thuật toán ứng dụng - Bài thực hành số 1.2: Cấu trúc dữ liệu" tập trung vào việc ứng dụng các cấu trúc dữ liệu để giải quyết các bài toán cụ thể. Bài thực hành sử dụng các ví dụ minh họa như HIST, REROAD và SIGNAL để giúp sinh viên hiểu rõ hơn về cách lựa chọn và sử dụng cấu trúc dữ liệu phù hợp. Mục tiêu là giúp sinh viên nắm vững cách thiết kế và triển khai các cấu trúc dữ liệu hiệu quả.

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 Thuật toán ứng dụng: Bài thực hành số 1.2 - TS. Bùi Quốc Trung, TA. Đặng Xuân Vương

Thuật toán ứng dụng Bài thực hành số 1.2: Cấu trúc dữ liệu TS. Bùi Quốc Trung, TA. Đặng Xuân Vương Trường Đại học Bách khoa Hà Nội Viện Công nghệ thông tin và Truyền thông Ngày 16 tháng 3 năm 2021 TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 1 / 21
Mục lục 1 HIST 2 REROAD 3 SIGNAL TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 2 / 21
Mục lục 1 HIST 2 REROAD 3 SIGNAL TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 3 / 21
02. HIST Có N cột với độ cao l1 , l2 , ... xếp liên tiếp. Tìm diện tích hình chữ nhật lớn nhất nằm gọn trong N cột. TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 4 / 21
Thuật toán Nhận xét: Hình chữ nhật có 2 cột biên i, j sao cho i < j có diện tích là (j − i + 1) × min(li , ..., lj ). Thuật toán: Thử hết các cặp (i, j), duyệt từ i đến j để tìm cột thấp nhất (tương tự bài SUBSEQMAX). Độ phức tạp: O(n3 ). TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 5 / 21
Thuật toán Nhận xét: min(li , ..., lj ) = min(min(li , ...lj−1 ), lj ). Cải tiến: O(n2 ). TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 6 / 21
Hướng tiếp cận khác Chọn cột i làm cột thấp nhất trong hình chữ nhật. Tìm lefti là cột gần nhất bên trái i thấp hơn cột i. Tìm righti là cột gần nhất bên phải i thấp hơn cột i. Số cột trong hình chữ nhật là righti − lefti − 1. Độ phức tạp: O(n2 ). TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 7 / 21
Tăng tốc bằng ngăn xếp Với left, duyệt các cột từ trái sang phải, khi duyệt đến cột i: Loại cột ở đầu stack trong khi nó còn cao hơn cột i. lefti là cột ở đầu stack hiện tại. Độ phức tạp O(N). Tương tự với right, chỉ khác là duyệt từ phải sang trái. Độ phức tạp tổng: O(N). TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 8 / 21
Code 1 template < class RandomIt > 2 vector < int > calc_extend ( RandomIt first , RandomIt last ) 3 vector < int > result ; 4 stack < RandomIt > s ; 5 for ( RandomIt it = first ; it != last ; it ++) { 6 while (! s . empty () && * s . top () >= * it ) s . pop (); 7 result . push_back ( it - ( s . empty () 8 ? ( first -1) : s . top ())); 9 s . push ( it ); 0 } 1 return result ; 2 } TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 9 / 21
Code 3 int main () { 4 int n ; 5 while (( cin >> n ) && n ) { 6 vector < long long > l ( n ); 7 for ( int i = 0; i < n ; i ++) cin >> l [ i ]; 8 vector < int > L = calc_extend ( l . begin () , l . end ()); 9 vector < int > R = calc_extend ( l . rbegin () , l . rend ()); 0 long long result = 0; 1 for ( int i = 0; i < n ; ++ i ) { 2 result = max ( result ,( L [ i ]+ R [n -i -1] -1)* l [ i ]); 3 } 4 cout
Mục lục 1 HIST 2 REROAD 3 SIGNAL TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 11 / 21
02. REROAD Cho N đoạn đường, đoạn đường i dùng phủ nhựa đường loại ti . Một phần đường là: Dãy liên tục các đoạn đường dùng chung loại nhựa đường tk . Đoạn đường phía trước đoạn đường đầu dãy (nếu có) không dùng nhựa đường loại tk . Tương tự với đoạn đường phía sau đoạn đường cuối dãy. Độ gập ghềnh là số phần đường. Yêu cầu: Tính lại độ gập ghềnh sau khi một đoạn đường bị sửa. TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 12 / 21
Ví dụ TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 13 / 21
Thuật toán Nhận xét: t[i] = t[i − 1] thì i chính là điểm bắt đầu phần đường. Số phần đường bằng số điểm bắt đầu phần đường. TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 14 / 21
Thuật toán Khi thay đổi t[i], sự thay đổi chỉ xảy ra ở i và i + 1. TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 15 / 21
Code 1 int isStart ( int u ) { 2 return u == 1 ? 1 : t [ u ] != t [u -1]; 3 } 4 int main () { 5 cin >> N ; 6 for ( int i = 1; i > t [ i ]; 7 int res = 0; 8 for ( int i = 1; i > Q ; 0 while (Q - -) { 1 cin >> p >> c ; 2 res -= isStart ( p ); 3 if ( p < N ) res -= isStart ( p +1); 4 t[p] = c; 5 res += isStart ( p ); 6 if ( p < N ) res += isStart ( p +1); 7 cout
Mục lục 1 HIST 2 REROAD 3 SIGNAL TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 17 / 21
02. SIGNAL Cho tín hiệu độ dài n có độ lớn a1 , a2 , ..., an và giá trị phân tách b. Tín hiệu phân tách được tại i nếu: max{a1 , ..., ai−1 } − ai ≥ b max{ai+1 , ..., an } − ai ≥ b Tìm vị trí i để tín hiệu phân tách được và max{a1 , ..., ai−1 } − ai + max{ai+1 , ..., an } − ai lớn nhất. TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 18 / 21
Thuật toán Xây dựng mảng maxPreﬁx[i] = max{a1 , ..., ai } Xây dựng mảng maxSuﬃx[i] = max{ai , ..., an } Duyệt từng vị trí i, kiểm tra điều kiện phân tách và cập nhật giá trị. Độ phức tạp: O(n). TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 19 / 21
Code 0 long long solve () { 1 maxPrefix [0] = - INF ; maxSuffix [ n +1] = - INF ; 2 for ( int i = 1; i = 1; i - -) 5 maxSuffix [ i ] = max ( maxSuffix [ i +1] , a [ i ]); 6 long long res = -1; 7 for ( int i = 2; i < n ; i ++) 8 res = check ( i ) ? max ( res , val ( i )) : res ; 9 return res ; 0 } TrungBQ, VuongDX (HUST) Cấu trúc dữ liệu Ngày 16 tháng 3 năm 2021 20 / 21