[Dev] Tính căn bậc 2 theo cách khác

Tính căn bậc 2 của một số theo một cách khác

Vấn đề

Trong một buổi phỏng vấn, có một câu hỏi như sau:

“Hãy viết chương trình C tính căn bậc 2 của số nguyên x”

Trong chớp mắt, bạn có thể đưa ra ngay lời giải với đoạn code ngắn gọn sau:

Chương trình compiled không có một lỗi và ra kết quả đúng.

Đến đây, bạn đã chứng tỏ bạn là người có căn bản. :) Nhưng đời lại không như đồn. <3

Ban phỏng vấn lại đặt ra một câu hỏi rất liên quan:

“Cậu hãy trả lời lại câu hỏi trên, lần này không dùng hàm sqrt của thư viện C”

Câu hỏi bắt đầu khó hơn rồi đấy, bạn đã thấy khoai chưa? Đến đây, nếu bạn không có câu trả lời, tức là bạn còn phải cố gắng rất nhiều nữa.

Vậy làm thế nào mà người ta lại có thể tính ra căn bậc 2 của một số mà không dùng hàm SQRT? Phải chăng là chúng ta sẽ phải viết một thuật toán phức tạp với rất nhiều dòng mã?

Và đây, là câu trả lời cho vấn đề khá hóc búa kia:

Máy tính làm phép tính rất nhanh, thay vì có câu trả lời tuyệt đối, ta có thể bắt nó đoán câu trả lời cho ta!

Căn bậc hai của y được định nghĩa là số x sao cho: x^2 == y hay x = y / x. Nếu x là kết quả thì x = y / x, còn nếu không kết quả sẽ phải là 1 số x’ nằm trong khoảng x và y/x. Ta không biết số này là bao nhiêu, nhưng ta có 1 cách để đoán lấy 1 số trong khoảng này đó là trung bình cộng!

Ví dụ:

Cần tính căn bậc 2 của 3. Ta đoán kết quả là 1.0. Kết quả này không đúng rồi, nên đáp số sẽ nằm trong khoảng 1.0 và 3/1.0 = 2.0. Lấy trung bình cộng lần 1 ta có kết quả là 1.5. Lại thử với 1.5 và 3/1.5 = 2.0 ta có kết quả là 1.75! Sau nhiều lần lặp ta sẽ có kết quả tiệm cận với đáp số!

Vì ta không có kết quả chính xác, nên số lần lặp sẽ là vô hạn. Tuy vậy tại mỗi bước lặp, ta sẽ thử xem kết quả đủ chính xác theo yêu cầu chưa. Ví dụ nếu đáp số hiện tại là x = 1.73, x^2 = 2.99 và ta chỉ cần độ chính xác đến 2 số sau dấu phẩy, thì 1.73 là đáp án phù hợp. Do vậy ta sẽ có chương trình tính căn bậc 2 như sau:

Tham khảo

  • Structure and Interpretation of Computer Programs
  • Newton method
  • http://www.cnblogs.com/luochuanghero/articles/4281491.html

Từ kipalog.com

Leave a Reply

2 Comments on "[Dev] Tính căn bậc 2 theo cách khác"

Notify of
avatar
Sort by:   newest | oldest | most voted
cuong
Guest

mình nghĩ while(fabs(guess*guess – x)/x >= PRECISE) nên bỏ /x đi vì cái đó không ảnh hưởng đến điều kiện dừng.

wpDiscuz