Vấn đề đặt ra ở đây là tiêu diệt goons trong các phòng của một tòa nhà với số vụ đánh bom tối thiểu. Các phòng được dán nhãn từ 1 đến n. Những con goons bị thương bởi cuộc tấn công ném bom đầu tiên và chết trong cuộc tấn công thứ hai. Khi các căn phòng bị đánh bom, lũ goons lao đến căn phòng gần nhất trong tòa nhà, đặc biệt là căn phòng bên cạnh. Chúng ta phải tính toán số lần ném bom cần thiết để ném bom vào các phòng để tiêu diệt hết lũ goon trong tòa nhà.
Hãy cho chúng tôi hiểu với ví dụ
Đầu vào - int number of room =3
Đầu ra −Yêu cầu ném bom tổng cộng
4
2 1 3 2
Giải thích - Ở đây số lượng bom tối thiểu cần thiết là 4, chúng ta hãy xem xét trước tiên chúng ta đánh bom phòng thứ 2, lũ goons sẽ lao đến phòng thứ nhất hoặc thứ 3 để tự cứu mình. Sau đó, chúng tôi đánh bom phòng đầu tiên, ở đây một số goons bị thương do các cuộc tấn công của phòng thứ 2 sẽ chết và những người trốn trong phòng thứ nhất bị thương và chạy đến phòng thứ 2 vì nó gần chúng nhất. Bây giờ chúng ta đánh bom căn phòng thứ 3 ở đây bọn goons từ cuộc đánh bom ở căn phòng thứ 2 đang ẩn nấp nên chúng sẽ chết trong vụ đánh bom của căn phòng thứ 3, và những con goon đang trốn trong căn phòng thứ 3 sẽ lao đến căn phòng gần nhất tức là căn phòng thứ 2 cuối cùng chúng ta đánh bom phòng thứ 2 ở đây goons bị thương từ phòng thứ 3 và thứ nhất bị giết và điều này hoàn thành nhiệm vụ của chúng ta.
Đầu vào - int number of room =2
Đầu ra −Yêu cầu ném bom tổng cộng
3
2 1 2
Giải thích - Ở đây số lượng bom tối thiểu yêu cầu là 3, chúng ta hãy xem chúng ta đánh bom phòng thứ 2 trước tiên, bọn goons sẽ lao đến phòng thứ nhất để tự cứu mình. Sau đó, chúng tôi đánh bom phòng đầu tiên, ở đây một số goons bị thương do các cuộc tấn công của phòng thứ 2 sẽ chết và những con goons đang trốn trong phòng thứ nhất bị thương và chạy đến phòng thứ 2 vì nó gần chúng nhất. Bây giờ chúng ta đánh bom căn phòng thứ 2 ở đây. Những con goons từ vụ đánh bom phòng thứ nhất đang ẩn náu bị giết và điều này hoàn thành nhiệm vụ của chúng tôi.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
-
Đầu tiên, số lượng phòng được lấy làm đầu vào từ người dùng.
-
Số lượng bom yêu cầu được tính là (n + n / 2) và được in sau đó.
-
Sau đó, chúng tôi đánh bom tất cả các phòng chẵn của tòa nhà và nó được in.
-
Sau đó, chúng tôi đánh bom các phòng lẻ của tòa nhà và in chúng sau đó.
-
Cuối cùng, chúng tôi đánh bom các phòng chẵn của tòa nhà một lần nữa để kết thúc quá trình ném bom và kết quả được in cho người dùng.
Ví dụ
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
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Total Bombings required 12 2 4 6 8 1 3 5 7 2 4 6 8