Số lượng bom tối thiểu để tiêu diệt kẻ thù trong Java

Bài toán: Tiêu diệt kẻ thù trong các phòng của tòa nhà với số lần ném bom tối thiểu. Các phòng được đánh số 1 đến n. Kẻ thù bị thương khi ném bom lần 1 và chết ở lần 2. Khi ném bom, kẻ thù chạy đến phòng lân cận gần nhất. Cần tính số lần ném bom để tiêu diệt hết kẻ thù.

Ví dụ minh họa

Đầu vào: Số phòng = 3

Đầu ra: Tổng số lần ném bom: 4, Thứ tự: 2 1 3 2

Giải thích: Ném phòng 2 → kẻ thù chạy đến 1 hoặc 3. Ném phòng 1 → kẻ thù bị thương ở 2 chết, kẻ thù ở 1 bị thương chạy đến 2. Ném phòng 3 → kẻ thù từ 2 chết, kẻ thù ở 3 chạy đến 2. Ném phòng 2 lần cuối → tiêu diệt hết.

Đầu vào: Số phòng = 2

Đầu ra: Tổng số lần ném bom: 3, Thứ tự: 2 1 2

Giải thích: Ném 2 → kẻ thù chạy đến 1. Ném 1 → kẻ thù bị thương từ 2 chết, kẻ thù ở 1 bị thương chạy đến 2. Ném 2 → tiêu diệt hết.

Phương pháp tiếp cận

• Nhập số phòng n
• Số bom cần thiết = n + n/2
• Ném bom tất cả phòng chẵn (2, 4, 6...)
• Ném bom tất cả phòng lẻ (1, 3, 5...)
• Ném bom lại các phòng chẵn một lần nữa

Ví dụ mã Java

public class TP {
    public static void main(String[] args) {
        int n = 8;
        System.out.println("Total Bombings required");
        System.out.println(n + n / 2);
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
        for (int i = 1; i <= n; i += 2)
            System.out.print(i + " ");
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
    }
}

Đầu ra

Total Bombings required 12 2 4 6 8 1 3 5 7 2 4 6 8