โปรแกรมตรวจสอบว่าสถานีตรวจจับ k ตัวเพียงพอหรือไม่ใน Python

มีโมดูลเซ็นเซอร์ตรวจจับรัศมี r มีจุดบนเส้นรูปวงกลมที่ต้องตรวจจับ วางโมดูลต่ำพลัง k ตัว ตรวจสอบว่าตรวจจับจุดทั้งหมดได้หรือไม่

ตัวอย่าง: j=4 (r^2), k=3 ผลลัพธ์ False (มี 4 จุดบนเส้นรูปวงกลม ต้องการอย่างน้อย 4 ตัว)

วิธีแก้ปัญหา

1. นับจุดจำนวนเต็ม (lattice points) บนเส้นรูปวงกลม x^2 + y^2 = j
2. วน i นับคู่ (i, sqrt(j-i^2)) ที่เป็นจำนวนเต็ม
3. คูณ 4 (4 ควอดรันต์)
4. ถ้า k >= จุดทั้งหมด คืน True มิฉะนั้น False

ตัวอย่างโค้ด

square_set = set([z**2 for z in range(44722)])

def solve(j, k):
    i = 0
    res = 0
    while i < (j**0.5):
        if j - i**2 in square_set:
            res += 1
        i += 1
    res *= 4
    return k >= res

print(solve(4, 3))

อินพุต

4, 3

เอาต์พุต

False