เดารากที่สองประมาณการใน Python

สมมติว่าเรามีตัวเลขไม่ติดลบ n เราต้องหาตัวเลข r ที่ทำให้ r * r = n และปัดเศษลงเป็นจำนวนเต็มที่ใกล้ที่สุด ต้องแก้ปัญหานี้โดยไม่ใช้ฟังก์ชันรากที่สองในตัว

ตัวอย่าง

หากอินพุตคือ 1025 ผลลัพธ์จะเป็น 32

ขั้นตอนการแก้ปัญหา

1. ถ้า n <= 1 ให้คืนค่า n
2. start := 1, end := n
3. ในขณะที่ start < end:
   • mid := start + end >> 1 (หาร 2 ด้วยการขยับบิต)
   • ถ้า mid * mid <= n ให้ start := mid + 1
   • อื่นๆ ให้ end := mid
4. คืนค่า start - 1

การใช้งาน

class Solution:
    def solve(self, n):
        if n <= 1:
            return n
        start, end = 1, n
        while start < end:
            mid = start + end >> 1
            if mid * mid <= n:
                start = mid + 1
            else:
                end = mid
        return start - 1

ob = Solution()
print(ob.solve(1025))

อินพุต

1025

เอาต์พุต

32