TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

10.1. Đảo mảng (1/3)  Cho một mảng gồm một dãy các giá trị.  Để đảo thứ tự các phần tử trong mảng, sử dụng nguyên lý Last-In-First-Out của Stack.  Ví dụ về hoạt động của đảo mảng: 10.1. Đảo mảng (2/3) Ý tưởng thực hiện giải thuật: 1. Khởi tạo một Stack rỗng, có kiểu số. 2. Với n phần tử của mảng, lần lượt đưa vào Stack thông qua hàm Pus...

24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 704 | Lượt tải: 1

9.1. Khái niệm về stacks (1/7)  Có thể hình dung stack như một chồng đĩa. Với chồng đĩa này, có thể nhìn thấy chiếc đĩa ở trên cùng, các đĩa còn lại chưa nhìn thấy được.  Khi thêm một đĩa vào chồng đĩa (pushed), chiếc đĩa này ở đỉnh của stack, có thể nhìn thấy.  Khi lấy di một đĩa từ stack (popped), có thể sử dụng đĩa này, chiếc đĩa kế ti...

24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 574 | Lượt tải: 1

8.1. Khái niệm về tìm kiếm (1/3)  Trong thực tế, việc xác định vị trí của một phần tử nào đó trong một danh sách ( đã sắp xếp hoặc chưa sắp xếp) có ý nghĩa quan trọng và được dùng trong nhiều ứng dụng.  Ví dụ 1: một chương trình tra cứu từ điển, chương trình cần trả lời ngay nghĩa của một từ nào đó.  Ví dụ 2: trong một danh sách thí sinh, ...

24 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 615 | Lượt tải: 1

7.1. ShellSort (1/8)  Phương pháp này được Donald Shell giới thiệu năm 1959.  Với phương pháp sắp xếp chèn: thực hiện ít phép toán so sánh, nhưng sử dụng nhiều phép di chuyển thừa.  Với phương pháp sắp xếp chọn: thực hiện ít phép toán di chuyển, nhưng sử dụng nhiều phép so sánh.  Có thể có phương pháp hiệu quả hơn không? 7.1. ShellSor...

31 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 561 | Lượt tải: 1

6.1. Thuật toán QuickSort (1/6)  Giải thuật Quick-sort là phương pháp sắp xếp dựa trên chiến lược chia để trị.  Giải thuật gồm các bước:  Phép chia: chọn ngẫu nhiên một phần tử x làm khóa, chia tập dữ liệu S ban đầu thành 3 phần:  L chứa các phần tử nhỏ hơn x  E chứa các phần tử bằng x  G chứa các phần tử lớn hơn x  Bước lặp: sắp...

27 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 794 | Lượt tải: 1

5.1.1. Các thuật toán sắp xếp (1/2) Thế nào là sắp xếp?  Đưa một dãy các đối tượng về dạng thứ bậc nào đó. Giải thuật sắp xếp dựa trên sự so sánh nào đó.  Việc sắp xếp chỉ dựa trên phép toán so sánh. Các phép toán cơ bản của sắp xếp.  So sánh.  Tráo đổi giữa các phần tử. 5.1.1. Các thuật toán sắp xếp (1/2) Quy ước.  Phương pháp s...

31 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 604 | Lượt tải: 1

4.1. Khái niệm kỹ thuật quay lui (1/6)  Kỹ thuật quay lui là quá trình phân tích từ trên xuống trong không gian tìm kiếm.  Trong trường hợp tổng quát, giả sử lời giải là một vector: a = (a[1], a[2], , a[n]) trong đó, mỗi phần tử a[i] chọn từ tập hữu hạn S[i] (các khả năng của a[i]). 4.1. Khái niệm kỹ thuật quay lui (2/6)  Ta sẽ giải quy...

29 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 628 | Lượt tải: 1

3.1. Khái niệm về đệ quy (1/6)  Với phần lập trình viên, để giải quyết bài toán lớn, có thể sử dụng 1 quá trình dạng đệ quy.  Ta nói một đối tượng là đệ qui nếu đối tượng này bao gồm chính nó như một bộ phận hoặc đối tượng được định nghĩa dưới dạng của chính nó. 3.1. Khái niệm về đệ quy (2/6)  Nguyên lý đệ quy cho phép hình thành bài toán...

39 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 656 | Lượt tải: 1

2.1. Khái niệm về mảng (1/2)  Mảng là cấu trúc dữ liệu do người dùng định nghĩa, có kích thước cố định và đồng nhất.  Theo tính chất đồng nhất, các thành phần có cùng kiểu, được gọi là element type hoặc base type.  Theo tính chất có kích thước cố định, ta không thể thay đổi kích thước của mảng khi đang sử dụng.  Mảng có thể coi là cấu tr...

26 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 534 | Lượt tải: 1

1.0. Đôi nét về khái niệm  Để giải một bài toán, bắt đầu từ câu hỏi “phải làm gì?”, sau đó trả lời câu hỏi “làm như thế nào?” → đó là cách tiếp cận đến giải thuật và cấu trúc dữ liệu.  Các bài toán trong thực tế không dễ giải bằng cách hiểu thông thường và để giảm độ phức tạp, trong nhiều trường hợp có thể mô hình hóa bài toán.  Từ việc m...

40 trang | Chia sẻ: thanhle95 | Ngày: 28/06/2021 | Lượt xem: 574 | Lượt tải: 1