Kĩ thuật lập trình - Chương 10: Thuật toán tổng quát

Nội dung text: Kĩ thuật lập trình - Chương 10: Thuật toán tổng quát

1. Kỹ thuật lập trình ng 1 ươ 010101010101010110000101010101010101011000010101010101010101100001 Chương 10: ThuStateControllerậttoánt010101010010101010010101010101001010101001010101010100101010100101ổng quát start() 101001100011001001001010100110001100100100101010011000110010010010 Ch stop() 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 N Ơ 101001100011001001001010100110001100100100101010011000110010010010y = A*x + B*u; 110010110010001000001011001011001000100000101100101100100010000010x = C*x + d*u; LQGController010101010101010110000101010101010101011000010101010101010101100001 start() 010101010010101010010101010101001010101001010101010100101010100101 stop() 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 11/2/2005 2004, HOÀNG MINH S ©
2. Nộidung chương 10 10.1 Tổng quát hóa kiểudữ liệuphầntử 10.2 Tổng quát hóa phép toán cơ sở 10.3 Tổng quát hóa phương pháp truy lặpphầntử N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 2 © 2005 - HMS ©
3. 10.1 Tổng quát hóa kiểudữ liệuphầntử ƒ Thực tế: —Khoảng 80% thời gian làm việc của một người thư ký văn phòng trước ₫ây (và hiện nay ở nhiều nơi) sử dụng cho công việc tìm kiếm, sắp xếp, ₫ối chiếu, so sánh, tài liệu và hồ sơ — Trung bình, khoảng 80% mã chương trình và thời gian thực hiện chương trình dành cho thực hiện các thuật toán ít liên quan trực tiếp tới bài toán ứng dụng cụ thể, mà liên quan tới tìm kiếm, sắp xếp, lựa chọn, so sánh dữ liệu ƒ Dữ liệu ₫ược quản lý tốt nhất trong các cấu trúc dạng "container" (vector, list, map, tree, queue, ) ƒ Vấn ₫ề xây dựng hàm áp dụng cho các "container": Nhiều hàm N Ơ chỉ khác nhau về kiểu dữ liệu tham số áp dụng, không khác nhau về thuật toán ƒ Giải pháp: Xây dựng khuôn mẫu hàm, tổng quát hóa kiểu dữ liệu phần tử Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 3 © 2005 - HMS ©
4. ƒ Ví dụ: Thuật toán tìm ₫ịa chỉ phần tử ₫ầu tiên trong một mảng có giá trị lớn hơn một số cho trước: template T* find_elem(T *first, T* last, T k) { while (first != last && !(*first > k)) ++first; return first; } void main() { int a[] = { 1, 3, 5, 2, 7, 9, 6 }; int *p = find_elem(a,a+7,4); if (p != a+7) { cout 4 :" 4:" << *p; N Ơ } double b[] = { 1.5, 3.2, 5.1, 2.4, 7.6, 9.7, 6.5 }; double *q = find_elem(b+2,b+6,7.0); *q = 7.0; Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát © 2005 - HMS 4 }©
5. ƒ Ví dụ: Thuậttoáncộng hai vector, kếtquả lưuvàovector thứ ba #include #include "myvector.h" template void addVector(const Vector & a, const Vector & b, Vector & c) { assert(a.size() == b.size() && a.size() == c.size()); for (int i= 0; i Vector N operator+(const Vector &a, const Vector & b) { Ơ Vector c(a.size()); addVector(a,b,c); return c; } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 5 © 2005 - HMS ©
6. 10.2 Tổng quát hóa phép toán cơ sở ƒ Vấn ₫ề: Nhiều thuật toán chỉ khác nhau ở một vài phép toán (cơ sở) trong khi thực hiện hàm ƒ Ví dụ: —Các thuật toán tìm ₫ịa chỉ phần tử ₫ầu tiên trong một mảng số nguyên có giá trị lớn hơn, nhỏ hơn, lớn hơn hoặc bằng, nhỏ hơn hoặc bằng, một số cho trước —Các thuật toán cộng, trừ, nhân, chia, từng phần tử của hai mảng số thực, kết quả lưu vào một mảng mới —Các thuật toán cộng, trừ, nhân, chia, từng phần tử của hai vector (hoặc của hai danh sách, hai ma trận, ) N ƒ Giải pháp: Tổng quát hóa thuật toán cho các phép toán cơ sở Ơ khác nhau! Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 6 © 2005 - HMS ©
7. template int* find_elem(int* first, int* last, int k, COMP comp) { while (first != last && !comp(*first, k)) ++first; return first; } bool is_greater(int a, int b) { return a > b; } bool is_less(int a, int b) { return a 4 is " > c; Ch}2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 7 © 2005 - HMS ©
8. Tham số khuôn mẫu cho phép toán ƒ Có thể là mộthàm, vídụ bool is_greater(int a, int b){ return a > b; } bool is_less(int a, int b) { return a ₫ốitượng hàm, ví dụ struct Greater { bool operator()(int a, int b) { return a > b; } }; struct Less { bool operator()(int a, int b) { return a < b; } N Ơ }; struct Add { int operator()(int a, int b) { return a + b; } }; Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 8 © 2005 - HMS ©
9. ƒ Ví dụ sử dụng ₫ốitượng hàm void main() { int a[] = { 1, 3, 5, 2, 7, 9, 6 }; int* alast = a+7; Greater greater; Less less; int* p1 = find_elem(a,alast,4,greater); int* p2 = find_elem(a,alast,4,less); if (p1 != alast) cout 4 is " > c; } N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 9 © 2005 - HMS ©
10. Ưu ₫iểmcủa ₫ốitượng hàm ƒ Đốitượng hàm có thể chứatrạng thái ƒ Hàm toán tử () có thể₫ịnh nghĩa inline => tăng hiệusuất template void apply(int* first, int* last, OP& op) { while (first != last) { op(*first); ++first; } } class Sum { int val; N public: Ơ Sum(int init = 0) : val(init) {} void operator()(int k) { val += k; } int value() const { return val; } }; Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 10 © 2005 - HMS ©
11. class Prod { int val; public: Prod(int init=1): val(init) {} void operator()(int k) { val *= k; } int value() const { return val; } }; struct Negate {void operator()(int& k) { k = -k;} }; struct Print { void operator()(int& k) { cout > c; } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 11 © 2005 - HMS ©
12. Kếthợp2 bướctổng quát hóa template T* find_elem(T* first, T* last, T k, COMP comp) { while (first != last && !comp(*first, k)) ++first; return first; } template void apply(T* first, T* last, OP& op) { while (first != last) { op(*first); ++first; N } Ơ } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 12 © 2005 - HMS ©
13. Khuôn mẫulớpchocác₫ốitượng hàm template struct Greater{ bool operator()(const T& a, const T& b) { return a > b; } }; template struct Less{ bool operator()(const T& a, const T& b) { return a > b; } }; template class Sum { T val; public: Sum(const T& init = T(0)) : val(init) {} N Ơ void operator()(const T& k) { val += k; } T value() const { return val; } }; Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 13 © 2005 - HMS ©
14. template struct Negate { void operator()(T& k) { k = -k;} }; template struct Print { void operator()(const T& k) { cout ()); int* p2 = find_elem(a,alast,4,Less ()); if (p1 != alast) cout 4 is " sum_op; apply(a,a+7,sum_op); Ơ cout ()); apply(a,a+7,Print ()); char c; cin >> c; }Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 14 © 2005 - HMS ©
15. 10.3 Tổng quát hóa truy lặpphầntử ƒ Vấn ₫ề 1: Một thuật toán (tìm kiếm, lựa chọn, phân loại, tính tổng, ) áp dụng cho một mảng, một vector, một danh sách họăc một cấu trúc khác thực chất chỉ khác nhau ở cách truy lặp phần tử ƒ Vấn ₫ề 2: Theo phương pháp truyền thống, ₫ể truy lặp phần tử của một cấu trúc "container", nói chung ta cần biết cấu trúc ₫ó ₫ược xây dựng như thế nào —Mảng: Truy lặp qua chỉ số hoặc qua con trỏ — Vector: Truy lặp qua chỉ số —List: Truy lặp qua quan hệ móc nối (sử dụng con trỏ) N Ơ — Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 15 © 2005 - HMS ©
16. Ví dụ thuậttoáncopy ƒ Áp dụng cho kiểumảng thô template void copy(const T* s, T* d, int n) { while (n ) { *d = *s; ++s; ++d; } } ƒ Áp dụng cho kiểuVector template void copy(const Vector & s, Vector & d) { for (int i=0; i void copy(const List & s, List & d) { N ListItem *sItem=s.getHead(), *dItem=d.getHead(); Ơ while (sItem != 0) { dItem->data = sItem->data; dIem = dItem->getNext(); sItem=sItem->getNext(); } } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 16 © 2005 - HMS ©
17. Ví dụ thuậttoánfind_max ƒ Áp dụng cho kiểu mảng thô template T* find_max(T* first, T* last) { T* pMax = first; while (first != last) { if (*first > *pMax) pMax = first; ++first; } return pMax; } ƒ Áp dụng cho kiểuVector template T* find_max(const Vector & v) { N int iMax = 0; Ơ for (int i=0; i v[iMax]) iMax = i; return &v[iMax]; } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 17 © 2005 - HMS ©
18. ƒ Áp dụng cho kiểu List (₫ã làm quen): template ListItem * find_max(List & l) { ListItem *pItem = l.getHead(); ListItem *pMaxItem = pItem; while (pItem != 0) { if (pItem->data > pMaxItem->data) pMaxItem = pItem; pItem = pItem->getNext(); } return pMaxItem; }  Cần tổng quát hóa phương pháp truy lặp phần tử! N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 18 © 2005 - HMS ©
19. Bộ truy lặp (iterator) ƒ Mục ₫ích: Tạomộtcơ chế thống nhấtchoviệctruylặpphầntử cho các cấutrúcdữ liệumàkhôngcầnbiếtchi tiếtthựcthibên trong từng cấutrúc ƒ Ý tưởng: Mỗicấutrúcdữ liệucungcấpmộtkiểubộ truy lặp riêng, có ₫ặctínhtương tự như mộtcon trỏ (trong trường hợp ₫ặcbiệtcóthể là mộtcon trỏ thực) ƒ Tổng quát hóa thuậttoáncopy: template void copy(Iterator1 s, Iterator2 d, int n) { while (n ) { *d = *s; N ++s; Ơ ++d; } Cácphéptoánápdụng } ₫ượctương tự con trỏ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 19 © 2005 - HMS ©
20. ƒ Tổng quát hóa thuậttoánfind_max: template ITERATOR find_max(ITERATOR first, ITERATOR last) { ITERATOR pMax = first; while (first != last) { if (*first > *pMax) pMax = first; ++first; } return pMax; Cácphéptoánápdụng ₫ượctương tự con trỏ } N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 20 © 2005 - HMS ©
21. Bổ sung bộ truy lặpchokiểu Vector ƒ KiểuVector lưutrữ dữ liệudướidạng mộtmảng => có thể sử dụng bộ truy lặpdướidạng con trỏ! template class Vector { int nelem; T* data; public: typedef T* Iterator; Iteratator begin() { return data; } Iteratator end() { return data + nElem; } }; N void main() { Ơ Vector a(5,1.0),b(6); copy(a.begin(),b.begin(),a.size()); } Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 21 © 2005 - HMS ©
22. Bổ sung bộ truy lặpchokiểuList template class ListIterator { ListItem *pItem; ListIterator(ListItem * p = 0) : pItem(p) {} friend class List ; public: T& operator*() { return pItem->data; } ListIterator & operator++() { if (pItem != 0) pItem = pItem->getNext(); return *this; } friend bool operator!=(ListIterator a, N Ơ ListIterator b) { return a.pItem != b.pItem; } }; Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 22 © 2005 - HMS ©
23. Khuôn mẫuList cảitiến template class List { ListItem *pHead; public: ListIterator begin() { return ListIterator (pHead); } ListIterator end() { return ListIterator (0); } }; N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 23 © 2005 - HMS ©
24. Bài tậpvề nhà ƒ Xây dựng thuậttoánsắpxếptổng quát ₫ể có thể áp dụng cho nhiềucấutrúcdữ liệutậphợp khác nhau cũng như nhiềutiêu chuẩnsắpxếp khác nhau. Viếtchương trình minh họa. ƒ Xây dựng thuậttoáncộng/trừ/nhân/chia từng phầntử củahai cấutrúcdữ liệutậphợpbấtkỳ. Viếtchương trình minh họa. N Ơ Ch2004, HOÀNG MINH S ương 10: Thuật toán tổng quát 24 © 2005 - HMS ©