Thuật toán vét cạn (Brute Force) và 2 ví dụ mô tả qua Java

Thuật toán vét cạn (Brute Force) và 2 ví dụ mô tả qua Java

Nếu Binh Pháp Tôn Tử có 36 kế, trong đó hạ kế cuối cùng là vứt hết của cải, bỏ chạy để giữ lấy mạng sống. Thì trong lĩnh vực khoa học máy tính cũng có một giải pháp tương tự để giải quyết mọi vấn đề khi bế tắc, bó tay: Thuật toán Vét cạn (Brute Force).

Thuật toán vét cạn (Brute Force) là gì?

Ý tưởng lý thuyết của thuật toán Vét cạn đơn giản là: duyệt qua tất cả các khả năng và lựa chọn kết quả gần đúng nhất. Thuật toán này chỉ được sử dụng trong những tình huống khi không có cách nào khác để tối ưu hóa hoặc giảm thiểu thời gian tính toán. Do phải duyệt qua tất cả các khả năng nên độ phức tạp của thuật toán Vét Cạn là O(n^2). Hiệu suất thời gian của Brute Force chắc chắn là kém, không thể sử dụng cho các vấn đề phức tạp. Nhưng khá hữu ích cho các vấn đề đơn giản khi chúng ta không tìm được giải pháp nào hay hơn.

Thuật toán bruteforcemath là loại giải pháp đơn giản và dễ hiểu, thường được sử dụng để giải quyết các bài toán toán học đơn giản, trong đó số lượng trường hợp cần duyệt không quá lớn. Ví dụ như:

Tìm hai số nguyên dương có tích bằng k.
Tìm ba số nguyên dương có tổng bằng k.
Tìm số nguyên dương nhỏ nhất chia hết cho tất cả các số từ 1 đến n.
Tìm số nguyên dương lớn nhất chia hết cho tất cả các số từ 1 đến n.

Ví dụ mô tả thuật toán vét cạn bằng Java

Để giúp bạn hiểu rõ hơn về thuật toán Brute Force, dưới đây là ví dụ bằng Java dùng thuật toán Vét Cạn để tìm 2 số nguyên dương có tổng là 10.

public class BruteForceMath {

    public static void main(String[] args) {
        int n = 10;

        // Duyệt qua tất cả các số nguyên dương từ 1 đến n
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                // Kiểm tra xem i và j có phải là hai số cần tìm hay không
                if (i + j == n) {
                    System.out.println("Hai số cần tìm là " + i + " và " + j);
                    return;
                }
            }
        }

        // Không tìm thấy hai số cần tìm
        System.out.println("Không tìm thấy hai số cần tìm");
    }
}