Để 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
Để 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:
Giải Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị - Kết nối tri thức
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.
Lời giải bài tập Chuyên đề Tin 11 Bài 6: Ý tưởng và kĩ thuật chia để trị hay, chi tiết khác:
Khởi động trang 28 Chuyên đề Tin học 11: Trò chơi tìm bi giả ....
Câu hỏi 2 trang 30 Chuyên đề Tin học 11: Mô tả bước "kết hợp" của bài toán 9 viên bi trên ....