Cần số nguyên q thỏa hai bất đẳng thức
Với số nguyên n≥0, căn bậc hai nguyên là số nguyên q≥0 lớn nhất không vượt $\sqrt n$. Có thể kiểm bằng điều kiện:
$$q^2\le n<(q+1)^2.$$
Ví dụ n=50 cho q=7 vì $7^2=49\le50<64=8^2$. Với n=49 cũng có q=7; với n=0 có q=0. Dùng so sánh bình phương nguyên để tránh phải làm tròn từ số thực.
Mỗi lần chỉ giữ một phía của khoảng
Hàm dưới dùng lời gọi đầu floorSqrt(n,0,n), với n nguyên không âm:
```python
def floorSqrt(n, start, end):
if start == end:
return start
mid = (start + end) // 2
if mid * mid == n:
return mid
if mid * mid < n:
if (mid + 1) * (mid + 1) > n:
return mid
return floorSqrt(n, mid + 1, end)
return floorSqrt(n, start, mid - 1)
```
Nếu mid²>n thì các số từ mid trở lên đều quá lớn, chỉ giữ phía trái. Nếu mid²<n nhưng (mid+1)²>n, mid chính là kết quả; nếu chưa thỏa, tìm tiếp phía phải. Khoảng ban đầu chứa kết quả và các nhánh giữ kết quả trong khoảng; khi chỉ còn một số thì trả số ấy.
Với n=50: [0,50] chọn mid=25 và thu trái về [0,24]; tiếp mid=12 về [0,11]; mid=5 về [6,11]; mid=8 về [6,7]; mid=6 về [7,7]; trả 7.
Kiểm quanh số chính phương
Chạy với tệp thực hành:
```text
python3 g11-cs-chia-de-tri.py can 50
```
Cần nhận căn bậc hai nguyên 7. Thử tiếp 0,1,2,48,49,63,64,65; kết quả lần lượt là 0,1,1,6,7,7,8,8. Với mỗi q, kiểm cả q²≤n và (q+1)²>n, không chỉ nhìn thấy chương trình trả một số.
Mẫu nhận n nguyên từ 0 đến 10^30 để giữ bộ thử trong phạm vi đang kiểm; số âm, chữ hoặc giá trị ngoài mẫu phải báo lỗi. Đây là giới hạn thử của tệp, không phải giới hạn của định nghĩa căn bậc hai nguyên.
Bài luyện
Căn bậc hai nguyên của 50 là bao nhiêu?
49 là một bình phương gần n, không phải căn nguyên.
7² vẫn chưa vượt 50 nên 6 chưa lớn nhất.
49≤50<64.
8²=64 vượt 50.
Lời giải
7²=49≤50, còn 8²=64>50. Vì vậy số nguyên lớn nhất có bình phương không vượt 50 là 7.
Bài luyện
Nếu mid²>n trong khoảng đang xét, vì sao chỉ tìm tiếp tới mid−1?
Phía trái vẫn có thể chứa số có bình phương không vượt n.
Tăng số không âm không làm bình phương giảm.
Điều kiện kết quả yêu cầu q²≤n.
Bình phương tăng theo số nguyên không âm.
Lời giải
Trong miền số nguyên không âm, số càng lớn thì bình phương càng lớn. mid đã quá lớn nên loại mid và toàn bộ phía phải; phần còn lại kết thúc tại mid−1.
Bài luyện
Điều kiện nào đủ xác nhận q là căn bậc hai nguyên của n≥0, với q nguyên không âm?
q hợp lệ và số nguyên kế tiếp đã vượt n.
q có thể chưa lớn nhất.
Chỉ đúng với một số n nhỏ, không phải điều kiện chung.
Có thể chọn số quá lớn hoặc bỏ số chính phương.
Lời giải
q²≤n cho biết q không vượt căn bậc hai; (q+1)²>n cho biết không thể tăng lên số nguyên tiếp theo. Hai điều kiện cùng xác nhận q là số nguyên lớn nhất cần tìm.
Đang học