Chương trình kiểm tra số chính phương không dùng hàm sqrt trong Python

Cho số n. Kiểm tra n có phải số chính phương () hay không, không dùng hàm căn bậc hai có sẵn.

Ví dụ: → (121 = 11×11).

Thuật toán giải quyết (Tìm kiếm nhị phân O(log n))

1. Nếu : trả về
2. Khởi tạo ,
3. Khi :
   • Tạo range
   • Lấy phần tử giữa:
   • Nếu : trả về
   • Nếu n:
   • Ngược lại:
4. Trả về

Ví dụ minh họa

def solve(n):
    if n == 0 or n == 1:
        return True
    start = 2
    stop = n // 2
    while start <= stop:
        temp = range(start, stop + 1)
        k = temp[len(temp) // 2]
        k_squared = k * k
        if k_squared == n:
            return True
        if k_squared > n:
            start = temp[0]
            stop = k - 1
        else:
            start = k + 1
            stop = temp[-1]
    return False

n = 121
print(solve(n))

Đầu vào

121

Đầu ra

True