Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước

Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 6: Ý tưởng và kĩ thuật chia để trị

Vận dụng 3 trang 32 Chuyên đề Tin học 11: Để tính giá trị (số nguyên) gần đúng căn bậc hai của số tự nhiên n cho trước:, người ta đã thiết lập hàm sau với ý tưởng gần tương tự thuật toán tìm kiếm tuần tự như sau:

Hãy thiết kế lại thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n bằng kĩ thuật chia để trị.

Lời giải:

Thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n có thể được thiết kế bằng kĩ thuật chia để trị theo các bước sau:

1. Nếu n bằng 0 hoặc 1, trả về n.

2. Đặt a bằng căn bậc hai của n.

3. Nếu a bằng n, trả về a.

4. Ngược lại, tìm số nguyên lớn nhất không vượt quá căn bậc hai của n/2 và số nguyên lớn nhất không vượt quá căn bậc hai của n - 1. So sánh hai số này và trả về số lớn hơn.