Tìm căn bậc hai không sử dụng hàm sqrt? Bạn nghĩ sao?
Hôm nay Nguyễn Văn Hiếu quay lại cùng với một bài toán đơn giản mà phức tạp. Chắc hẳn khi học lập trình bạn nào cũng đã từng tính căn bậc hai của một số. Chắc không ai quên được tên hàm nó chính là hàm sqrt(). Nhưng các bạn đã bao giờ tự hỏi làm sao để có thể tự viết hàm sqrt() này chưa? Hãy cũng mình đi tìm giải pháp trong bài viết này nhé.
Tính căn bậc hai sử dụng hàm trong C/C++.
// Code from https://nguyenvanhieu.vn #include <stdio.h> #include <math.h> int main() { int x; printf("Input x: "); scanf("%d", &x); printf("Sqrt of %d = %fn", x, sqrt(x)); }
Chạy demo:
Input x: 5 Sqrt of 5 = 2.236068
Tìm căn bậc hai của một số không dùng hàm thì sao?
Ý tưởng tìm căn bậc hai:
- Khai báo 1 epsilon đặt sai số chấp nhận, vì căn bậc hai của một số có thể là số thập phân vô hạn.
- Khởi tạo kết quả bằng 1.0
Nếu kết quả có sai số cao hơn epsilon, cập nhật lại kết quả theo công thức
result = (number/result - result) / 2 + result;
- Mình sẽ thu hẹp dần giới hạn trên và giới hạn dưới của kết quả, lấy trung bình hiệu khoảng cách giới hạn đó để cập nhật kết quả. Điều này luôn đảm bảo rằng giới hạn trên dưới sẽ bị thu hẹp nhưng sẽ luôn bao bọc đáp án.
- Nếu kết quả có sai số nhỏ hơn EPSILON thì dừng lại và lấy kết quả đó làm đáp án.
Ví dụ: Bạn cần tính căn bậc 2 của 5.
- Ta khởi tạo kết quả là 1.0. Kết quả này dĩ nhiên không đúng rồi, nên đáp số sẽ nằm trong khoảng 1.0 và 5/1.0 = 5.0.
- Lấy một nửa hiệu khoảng 1.0 đến 5.0 là 1.0 + (5.0 – 1.0)/2 được 3.0. Nhưng 3.0 lớn hơn kết quả thực(bình phương là biết, trong code thì sai số để check),
- Lại lấy nửa hiệu khoảng từ 5/3.0 đến 3.0 cộng vào kết quả hiện tại(3.0) = 3.0 + (5/3.0 – 3.0) = 2.33…
- Cứ làm tiếp tục như vậy cho tới khi sai số nhỏ hơn EPSILON
Code đầy đủ cho ý tưởng này là
// Code from https://nguyenvanhieu.vn #include <stdio.h> #include <math.h> #define EPSILON 0.0001f double mySqrt(int number) { double result = 1.0f; while (fabs(result * result - number) / number >= EPSILON) result = (number / result - result) / 2 + result; return result; } int main() { int x; printf("Input x: "); scanf("%d", &x); printf("Sqrt of %d = %1.9fn", x, mySqrt(x)); return 0; }
Và chạy thử xem sao
Input x: 5 Sqrt of 5 = 2.236069
Ok, hi vọng rằng bài viết chia sẻ được cho bạn những kiến thức bổ ích về lập trình.
Nếu bạn quan tâm đến kiến thức lập trình C/C++, hãy đọc các bài viết ở đây nhé
Để lại một bình luận