Tìm hiểu thuật toán tổng quát trong lập trình phần 1
lượt xem 6
download
— 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 hồ sơ.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Tìm hiểu thuật toán tổng quát trong lập trình phần 1
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD er er ! ! W W O O N N Nội dung chương 10 y y bu bu TỔNG QUÁT HÓA CÁC KIỂU DỮ LIỆU VÀ PHÉP TOÁN TRONG LẬP TRÌNH to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k NỘI DUNG BÀI HỌC: 10.1 Tổng quát hóa kiểu dữ liệu phần tử 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ặp phần tử 2 Chương 10: Thuật toán tổng quát
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD er er ! ! W W O O 10.1 Tổng quát hóa kiểu dữ liệu phần tử N N y y bu bu to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k 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 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ử 3 Chương 10: Thuật toán tổng quát
- h a n g e Vi h a n g e Vi Ví dụ: Thuật toán tìm ₫ịa chỉ phần tử ₫ầu tiên trong một mảng có giá XC XC ew ew F- F- PD PD er er ! ! W W O O N N y y bu bu trị lớn hơn một số cho trước: to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o template c u -tr a c k c u -tr a c k 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
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD er er ! ! W W O O N N Ví dụ: Thuật toán cộng hai vector, kết quả lưu vào vector thứ ba y y bu bu to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k #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 < a.size(); ++i) c[i] = a[i] + b[i]; } template Vector operator+(const Vector&a, const Vector& b) { Vector c(a.size()); addVector(a,b,c); return c; } 5 Chương 10: Thuật toán tổng quát
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD er er ! ! W W O O 10.2 Tổng quát hóa phép toán cơ sở N N y y bu bu to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k 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, ...) 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! 6 Chương 10: Thuật toán tổng quát
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD template er er ! ! W W O O N N y y bu bu to to int* find_elem(int* first, int* last, int k, COMP comp) { k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k 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 < b; } bool is_equal(int a, int b) { return a == b;} void main() { int a[] = { 1, 3, 5, 2, 7, 9, 6 }; int* alast = a+7; int* p1 = find_elem(a,alast,4,is_greater); int* p2 = find_elem(a,alast,4,is_less); int* p3 = find_elem(a,alast,4,is_equal); if (p1 != alast) cout
- h a n g e Vi h a n g e Vi XC XC ew ew F- F- PD PD er er ! ! W W O O N N Tham số khuôn mẫu cho phép toán y y bu bu to to k k lic lic C C w w m m w w w w o o .c .c .d o .d o c u -tr a c k c u -tr a c k Có thể là một hàm, ví dụ bool is_greater(int a, int b){ return a > b; } bool is_less(int a, int b) { return a < b; } int add(int a, int b) { return a + b; } int sub(int a, int b) { return a - b; } ... Hoặc tốt hơn hết là một ₫ối tượng thuộc một lớp có hỗ trợ (nạp chồng) toán tử gọi hàm => ₫ối tượ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; } }; struct Add { int operator()(int a, int b) { return a + b; } }; ... 8 Chương 10: Thuật toán tổng quát
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình trí tuệ nhân tạo
61 p | 873 | 262
-
Giáo trình mạng máy tính - Chương 3
15 p | 221 | 74
-
Bài giảng Thuật toán: Chương 3 - GV. Nguyễn Thanh Cẩm
67 p | 161 | 30
-
Bài giảng Thuật toán: Chương 2 - GV. Nguyễn Thanh Cẩm
65 p | 128 | 19
-
Tài liệu Kỹ thuật lập trình - Chương 4: Phân tích số nguyên thành nhân tử
14 p | 150 | 10
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)
55 p | 117 | 8
-
Tìm hiểu thuật toán tổng quát trong lập trình phần 3
8 p | 47 | 4
-
Tìm hiểu thuật toán tổng quát trong lập trình phần 2
8 p | 60 | 4
-
Sự phát triển của Malware trong 10 năm trở lại đây
14 p | 10 | 4
-
Giáo trình Cấu trúc dữ liệu và giải thuật - Nghề: Công nghệ thông tin (Cao đẳng) - CĐ Kỹ Thuật Công Nghệ Bà Rịa-Vũng Tàu
86 p | 64 | 3
-
Một phương pháp mô hình hóa nhiễu để tăng cường chất lượng nhận dạng tiếng nói
4 p | 30 | 3
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