D18CN

Mục lục [QUEUE] [Priority_QUEUE] Giới thiệu QUEUE Chắc hẳn các bạn đã từng xếp hàng rồi chứ nhỉ? Khi mua đồ, khi mua vé xem phim, hay xếp hàng ra về. Mọi lần xếp hàng sẽ bắt đầu từ người đứng đầu tiên rồi tới các bạn phía sau, và tất nhiên người nào đến sớm hơn thì sẽ được ra về sớm hơn. Đó cũng chính là minh họa cho Cấu trúc QUEUE mà mình muốn hướng tới ngày hôm nay. QUEUE-tạm dịch là hàng đợi, là cấu trúc song hành với STACK nhưng hoạt động theo chuẩn LILO(Last In Last Out) hoặc FIFO(Fist In First Out). Hiểu một cách đơn giản là Vào Trước Ra Trước. Trong QUEUE, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào Code Việc thêm phần tử vào cuối queue gọi là enqueue. Việc xóa phần tử đầu gọi là dequeue Khai báo # include <queue> //Ví dụ khai báo queue kiểu int queue < int > s ; s . size ( ) : trả về kích thước hiện tại của queue . s . empty ( ) : ...

--- --- Mục lục Giới thiệu Định nghĩa Code Ứng dụng Áp dụng Giới thiệu Tưởng tượng bạn có một giá sách thì khi cất sách thì cuốn đó được đặt lên trên cùng, và khi lấy ra thì phải lấy cuốn trên cùng, chứ không thể lấy ra hoặc cất lên từ vị trí khác. Đó chính là cách hoạt động của cấu trúc Stack (Ngăn xếp) theo kiểu LIFO (Last In First Out - Vào sau ra trước) Định nghĩa Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node) ) và có hai phép toán cơ bản: push : Bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. pop : Giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack. Code Cấu trúc Stack được chứa trong thư viện stack vậy nên chúng ta cần include< stack > Cách khai báo: stack < int > nganXep1 ; /...

Mục lục Giới thiệu Giới thiệu thuật toán Thuật toán khác Giới thiệu Một hoán vị trong toán học là một dãy gồm n n n kí tự với các kí tự từ 1…9 xuất hiện duy nhất và chỉ một lần: 123, 321, 1234, … Giới thiệu thuật toán Thuật toán sinh hoán vị kế tiếp là một thuật toán được dùng trong tin học máy tính rất nhiều, và thường được thấy ở một số bài toán giải thuật áp dụng. Giống với “Sinh Nhị Phân”, sinh hoán vị cũng là thuật toán được áp dụng với các bài toán mang tính “Lựa chọn” có thứ tự. Ví dụ: Các cách sắp xếp các số từ 1 đến 3 có thể là: 123, 321, 132, 231, 213, 312 Thuật toán được phát biểu như sau: Từ phải qua trái tìm chỉ số đầu tiên xuất hiện trước dãy giảm dần: Ví dụ: 6543 721 thì vị trí cần tìm là i = 4 với A[i] = 3 Trong đoạn giảm dần ở vị trí có phần tử nhỏ nhất vẫn lớn hơn A[i]: Như trên thì chỉ só cần tìm là j = 5 A[j] = 7 Đổi chỗ A[i] và A[j] Sau đó đảo ngược đoạn từ i + 1 -> cuối dãy Code: # include <iostream> using namespace ...

--- --- Mục lục Giới thiệu Giới thiệu thuật toán Quay lui nhị phân Áp dụng giải thuật Giới thiệu Nhị phân là một chuỗi kí tự gồm [0,1] thường được dùng để biểu diễn các tín hiệu số trong môn Điện tử số(Kỹ thuật số PTIT), và được sử dụng bởi chính chiếc máy tính của chúng ta, những thao tác cực kì phức tạp cũng được biểu diễn bởi những dãy nhị phân. Vd: 001, 111, 111100110,… Tất nhiên dãy nhị phân có quy luật cả đấy. Bây giờ chúng ta sẽ đi tìm cách để xây dựng bộ mã nhị phân nhé! Giới thiệu thuật toán Ví dụ: Một dãy nhị phân cấp 3: 000, 001, 010, 011, 100, 101, 110, 111 Dãy nhị phân cấp 2: 00, 01, 10, 11 Dãy nhị phân cấp n: sẽ có 2 n 2^n 2 n dãy Thuật toán chúng ta dùng ở đây mình sẽ không chứng minh lại mà áp dụng kết quả luôn, các bạn có thể tự suy nghĩ từ các dãy, quy luật rất đơn giản Thuật toán được phát biểu như sau: Bước khởi tạo: Khởi tạo tất cả các giá trị bằng 0 Bước một: Duyệt từ cuối về đầu gặp số 0 đầu tiên thì đánh đấu là 1 Bước hai: Đặt tất cả cá...

--- --- Mục lục Giới thiệu bài toán Thuật toán truyền thống Tối ưu Giới thiệu bài toán Trong thực tế nhiều trường hợp, chúng ta luôn phải sắp xếp, tìm kiếm theo một chuẩn nào đó. Ví dụ như: Trong lớp có duy nhất một bạn được 9 điểm, hãy tìm bạn đó? Hay là một dãy sinh viên trong lớp tìm một sinh viên bất kì? Với những bài toán như vậy chúng ta sẽ phải đi tìm kiếm trên một tập nào đó, ví dụ như tìm kiếm tên sinh viên trên tập sinh viên trong lớp… Truyền thống Linear Search Tất cả chúng ta đều biết rằng, muốn tìm kiếm một sinh viên nào đó trên bảng danh sách thì cách đơn giản nhất đó là : “Đi từng sinh viên từ đầu, kiểm tra xem đó có phải sinh viên cần tìm không, không thì next”. Ví dụ chúng ta có mảng A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9} với Key = 7 Theo đúng cách trên thì ta có cách duyệt từ đầu đến cuối. Nếu giá trị mình cần tìm là Key thì sẽ in ra vị trí xuất hiện đó # include <iostream> using namespace std ; int timKiem ( int Arr [ ] , int n , i...

1. Nguyên lý cơ bản của Interpolation Search + Cũng yêu cầu dãy số đầu vào là một dãy đã được xắp xếp cho sẵn. + Tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search. + Nếu như tìm kiếm nhị phân luôn nhắm vào vị trí giữa của các khoảng tìm kiếm thì tìm kiếm nội suy lại có xu hướng tiến gần đến vị trí gần với giá trị tìm kiếm. + Do đó Tìm kiếm nội suy đạt được sự tối ưu rất cao, và tốc độ nhanh hơn nhiều Binary. Độ phức tạp thời gian mà nó đạt được là:  Log2(log2(n)) .    (log cơ số 2) Giả sử nếu số phần từ n = 1 tỷ =>  Linear O = 1 tỷ. =>  Binary O = log2(1 tỷ) xấp xỉ =  30 =>  Nội suy O =  log2(log2(1 tỷ)) < 5 Các bạn sẽ thấy chỉ với số lượt nhỏ hơn 5, Tìm kiếm nội suy có thể tìm cho bạn được vị trí cần tìm trong 1 tỉ phần tử =>  RẤT KHỦNG. Do đó nó được coi như hàng độc, và khi nào cần thiết thì mới sử dụng. Vậy thì cơ chế nào để tìm kiếm nội suy có thể đạt được tốc độ kinh khủ...