Thuật Toán Brute Force – Thuật Toán “Trâu Bò” - Undefined Developer

Chào các bạn, hẳn là ai cũng đã từng nghe đến thuật toán Brute Force hay còn gọi là thuật toán trâu bò, vậy Brute Force là gì? Hôm nay mình sẽ giới thiệu cho các bạn về thuật toán trâu bò này – một thuật toán mà thực tế mọi người rất hay sử dụng nhưng có thể không biết nó chính là Brute Force.

Brute Force là một thuật toán vét cạn, thuật toán này sẽ chạy tất cả các trường hợp có thể có để giải quyết một vấn đề nào đó (Bao gồm cả trường hợp đúng và các trường hợp sai hay còn gọi là trường hợp dư thừa).

Để các bạn có thể hình dung rõ hơn về nó mình sẽ lấy một ví dụ đơn giản dễ hiểu như sau:

Ví dụ 1: Cho 2 chuỗi T và chuỗi P (20 < t, P < 100000). Tìm tất cả các vị trí mà chuỗi T xuất hiện trong chuỗi P. Ví dụ minh họa: + Chuỗi T = “abc” + Chuỗi P = “abcdefghijkabbcabchgjak” => Chuỗi T sẽ xuất hiện trong P tại 2 vị trí là 1 và 16.

Nếu dùng thuật toán Brute Force thì bạn sẽ chạy từ kí tự đầu tiên đến kí tự cuối cùng của chuỗi P, nếu vị trí thứ i có kí tự trùng với kí tự đầu tiên trong chuỗi T thì bạn thực hiện chạy 1 vòng lặp nữa để so sánh xem chuỗi T có xuất hiện trong P ở vị trí thứ i hay không. Cách chạy như vậy được gọi là Brute Force hay thuật toán trâu bò.

#include <bits/stdc++.h> #include <stdio.h> #include <algorithm> #include <iostream> #include <iterator> #include <numeric> #include <sstream> #include <fstream> #include <cassert> #include <climits> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <functional> using namespace std; #define sync ios::sync_with_stdio(false) #define ll long long int #define pii pair<int, int> #define MAX 100011 int main() { string T, P; int n, m; cin >> T >> P; n = P.length(); m = T.length(); for(int i = 0; i < n - m; i++) { if(P[i] == T[0]) for(int j = 1; j < m; j++) { if(P[i + j] != T[j]) break; if(j == m -1) cout << "T xuat hien tai vi tri " << i + 1 << " trong P" << endl; } } return 0; }

Ví dụ 2: Cho 2 mảng số nguyên a, b có tối đa 1000000 phần tử. Tìm tất cả các cặp phần tử (i, j) sao cho ai = bj = 1. Nếu không có cặp nào thì xuất (-1, -1). => Nếu bài này các bạn giải theo Brute Force thì sẽ chạy 1 vòng lặp tất cả phần tử của a, với mỗi phần tử của a có giá trị là 1 thì cần chạy duyệt tất cả phần tử của b xem b có phần tử nào có giá trị là 1 thì xuất ra cặp (i, j).

Nếu dùng thuật toán trâu bò như vậy thì với lượng dữ liệu đầu vào rất lớn thì tốc độ chạy thuật toán là rất chậm, đối với các bài toán có dữ liệu đầu vào nhỏ, số lượng trường hợp ít thì thuật toán Brute Force chạy cũng không mất quá nhiều thời gian.

Vì vậy trong các trường hợp cần chạy nhanh, chính xác thì nên cải tiến Brute Force (nếu có thể) hoặc sử dụng các thuật toán khác để đảm bảo tốc độ chạy chương trình như: Two Pointer, Hash, KMP/MP…

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan