Chuyển đến nội dung chính

Vét cạn hay duyệt trâu (Brute Force)


Thuật toán vét cạn: 

  • Thuật toán vét cạn hay duyệt trâu (Brute Force) được  hiểu đúng như tên gọi của nó, chúng ta sẽ dùng những phương pháp đơn giản để duyệt qua toàn bộ các trường hợp của bài toán và bằng sức mạnh của máy  tính để tìm ra được đáp án chính xác thay vì dùng các thuật toán hiệu quả hơn . 

  • VD: bài toán sống sót qua cuối tháng khi hết tiền tiêu: 
    • Giải pháp của bài này là chúng ta sẽ dùng vòng for vét can toàn bộ lương thực quanh nhà như mì tôm, hủ gạo... Để có thể tìm ra bữa ăn sống sót qua ngày và vì phải chạy đi tìm kiếm khắp nơi nên cách làm này sẽ có hơi tốn sức (dẫn đến chết đói).

  • Có nhiều cách duyệt khác nhau như:
    • Dùng nhiều vòng for
    • If, else
    • Đệ Quy, quay lui (Backtracking)
    • Bitmask
    • ....
  • Giải thuật này thường rất hiệu quả với những bài toán có dữ liệu đầu vào nhỏ nhưng đối với các dữ liệu lớn hơn hay các bài toán phức tạp hơn sẽ tốn rất nhiều thời gian và đòi hỏi một lực code trâu bò để có thể vét cạn hết toàn bộ.



Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Thuật toán lùa bò vào chuồng(Đếm phân phối)

Làm cách nào từ một coder chân chính  trở thành một người chăn bò 😃😃 Chắc hẳn trong lập trình chúng ta không khó để gặp gỡ các bài toán đếm.Tuy nhiên việc thực hiện các bài toán đếm thường được diễn ra trên dữ liệu lớn, nếu các bạn không biết cách tổ chức dữ liệu và thực hiện  thuật toán hiệu quả thường sẽ dẫn đến kết quả sai lầm. Vì vậy trong bài viết hôm nay chúng ta sẽ cùng tìm hiểu qua một trong những cách tiếp cận bài toán đếm đó là thuật toán lùa bò vào chuồng hay còn gọi là đếm phân phối. 1. Đặt vấn đề: Ban đầu bạn có một mảng số gồm N phần tử ( N <10^5) mỗi giá trị trong mảng đều bé hơn hoặc bằng 100. Bạn được giao nhiệm vụ đếm xem trong mảng số đó có bao nhiêu phần tử riêng biệt.      VD: N=10      arr []  =   1 6 9 1  7 9 9 9 2 3 => 6 phần tử riêng biệt. 2.Thuật toán lùa bò vào chuồng:   Tư tưởng của thuật toán: giả sử bạn là một người nông dân sở hữu một nông trại bò và bạn cần phải đếm chính xác s...
Đăng nhận xét
Đọc thêm

Tính a*b theo lũy thừa nhị phân

Như ta đã biết với a và b là 2 số nguyên           a*b = a*(b-1)+a  khi b>0 cách làm này cũng vẫn sẽ mất  b bước thực hiện. Tượng tự ta có tính chất sau trong phép nhân           a*b=a*(b/2)+a*(b/2) Từ đó: ta có thể phân tích a*b như sau: a*b = a*(b/2)+a*(b/2)               khi b chẵn a*b= a*(b/2) + a*(b/2)+a          khi b lẻ Với tính chất này tương tự như lũy thừa ta có thể tính a*b bằng cách tính a*(b/2) mà khong cần tính  a*(b-1)+a... từ đó ta có tính a*b với độ phức tạp là O(log(n)) int bin_multiplication ( int a , int b ) {     int res = 0 ;     while ( b > 0 ) {         if ( b % 2 == 1 )             res = res + a ;         a = a + a ;         b = b >> 1 ; // b=b/2     }   ...
Đăng nhận xét
Đọc thêm