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ị.
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.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy
Bài 6: Ý tưởng và kĩ thuật chia để trị
Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị