จำนวนระเบิดขั้นต่ำเพื่อกำจัดโจรในห้องต่างๆ ใน Java

ภาพรวมปัญหา

ตึกมีห้อง 1 ถึง n โจรอยู่ในแต่ละห้อง การระเบิดครั้งแรกทำให้โจรบาดเจ็บ ครั้งที่สองตาย เมื่อระเบิด โจรจะหนีไปห้องข้างเคียง ต้องหาลำดับการระเบิดน้อยที่สุดเพื่อกำจัดโจรทั้งหมด

ตัวอย่าง

n = 3

Output: 4 ครั้ง
ลำดับ: 2 1 3 2

คำอธิบาย: ระเบิดห้อง 2 → โจรหนีไป 1,3 → ระเบิดห้อง 1 → โจรบาดเจ็บจากห้อง 2 ตาย โจรห้อง 1 บาดเจ็บหนีไป 2 → ระเบิดห้อง 3 → โจรจากห้อง 1 ตาย โจรห้อง 3 หนีไป 2 → ระเบิดห้อง 2 → โจรที่เหลือตายทั้งหมด

n = 2

Output: 3 ครั้ง
ลำดับ: 2 1 2

แนวทางแก้ปัญหา

• จำนวนระเบิดขั้นต่ำ = n + n/2
• ลำดับการระเบิด:
  1. ระเบิดห้องเลขคู่ทั้งหมด (2, 4, 6, ...)
  2. ระเบิดห้องเลขคี่ทั้งหมด (1, 3, 5, ...)
  3. ระเบิดห้องเลขคู่อีกครั้ง (2, 4, 6, ...)

ตัวอย่างโค้ด 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 + " ");
    }
}

ผลลัพธ์ (n=8)

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