D18CN

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ủ...

Thuật toán quay lui (Backtracking) Tư tưởng Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng. Các bước trong việc liệt kê cấu hình dạng X[1...n]: Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ: Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước: ... .... Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó. Thông báo cấu hình tìm được. Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search). Mô hình thuật toán Mã giả cho thuật toán quay lui. Backtracking(k) { for ([Mỗi phương án chọ n i ( thuộc tập D )]) { if ([Chấp nhận i]) { [ Chọ...