Tìm giá trị của đa thức bằng quy tắc Horner trong C++

Quy tắc của Horner là một thuật toán hiệu quả để tính giá trị của một đa thức.

Xét đa thức p(x) = 6x^3 - 2x^2 + 7x + 5 tại x = 4 . Để tính toán nó bằng quy tắc Horner trong C++, hệ số đầu tiên, 6, được nhân với giá trị tại x, là 4, và tích của hai là 24, được cộng vào hệ số tiếp theo -2.

Kết quả được nhân với 4 và thêm vào hệ số tiếp theo.

Quá trình này được lặp lại đối với số hệ số trong phương trình. Sản phẩm cuối cùng còn lại là giá trị của đa thức.

Bài viết này giải thích cách tìm giá trị của đa thức bằng quy tắc Horner trong C++ bằng cách chuyển đổi các quy tắc trên thành mã máy tính.

Hãy xem xét một đa thức:

Nếu x = 4 thì giá trị của đa thức là 385.

Tìm giá trị của đa thức bằng quy tắc Horner trong C++ bằng cách lặp lại vòng lặp

Hãy xem chương trình tìm giá trị của một đa thức sử dụng quy tắc Horner trong C++ bằng cách lặp ngược.

1. Dòng mã đầu tiên nhập gói thư viện iostream ; trong dòng thứ hai, không gian tên được định nghĩa là std .

2. Một phương thức int Horner() được tạo với ba tham số – một mảng con trỏ a sẽ truyền danh sách các hệ số, biến số nguyên n lưu trữ bậc của đa thức và một biến số nguyên khác x lưu trữ giá trị của đa thức tại x .

    int Horner( int * a, int n, int x)

3. Điều này giải thích cách cộng tích của các đa thức với nhau. Một biến số nguyên result được tạo, được khởi tạo với phần tử cuối cùng của mảng a[n] .

    int result = a[n];

   Lưu ý: Đừng nhầm nó là kích thước của mảng; nó khởi tạo biến result với phần tử trong mảng a ở vị trí thứ n.

4. Vòng lặp for được tạo, đảo ngược vòng lặp từ phần tử cuối cùng của mảng a sang chỉ số thứ 0. Giá trị của biến result được cập nhật cho mỗi lần lặp lại vòng lặp.

    for ( int i = n - 1 ; i >= 0 ; -- i)

   Trong lần lặp đầu tiên, giá trị của a[n] được nhân với x và sau đó được thêm vào phần tử trước đó trong mảng – a[n-1] . Đối với một mảng – {2,3,4} , vòng lặp sẽ lấy phần tử cuối cùng a[n] , là 4, nhân nó với x , rồi cộng vào phần tử n-1 của mảng, là 3.

   Vì lý do này, các hệ số cần được đảo ngược trong khi khởi tạo trong hàm main . Giá trị của result được trả về ở cuối phương thức.

5. Bên trong hàm main , một mảng được tạo để chuyển nó đến tham số đầu tiên của phương thức Horner . Lưu ý rằng giá trị của các hệ số bên trong mảng bị đảo ngược do vòng lặp lặp ngược.

6. Một biến số nguyên sol được tạo để lưu trữ kết quả trả về từ phương thức có tên Horner .

   Trong tham số đầu tiên, mảng đang được tạo được truyền vào. Tham số thứ hai chuyển bậc của đa thức trong phương trình, 3 và giá trị tham số thứ ba tại x được chuyển.

    int sol = Horner(arr, 3 , 4 );

Mã số:

#include <iostream>
using namespace std;
int Horner(int* a, int n, int x)
{
    int result = a[n];
    for (int i = n - 1; i >= 0; --i)
        result = result * x + a[i];
    return result;
}

int main() {
    int arr[4] = {5,7,-2,6};
    int sol = Horner(arr, 3, 4);
    cout << sol;
}

Đầu ra (Quy tắc lặp ngược của Horner trong C++):

385

Tìm Giá trị của Đa thức Sử dụng Quy tắc Horner trong C++ bằng cách Lặp lại Vòng lặp Chuyển tiếp

Nếu chúng ta cần chạy vòng lặp về phía trước, không giống như ví dụ trước, chúng ta có thể hủy đăng ký con trỏ của mảng để lấy phần tử đầu tiên của nó và chạy vòng lặp về phía trước thay vì đảo ngược nó. Đó là một cách khác để sử dụng các vòng lặp để thực hiện quy tắc Horner trong C++.

Hãy hiểu những gì mã làm:

1. Dòng mã đầu tiên nhập gói thư viện iostream .

2. Tương tự như ví dụ trước, một phương thức Horner được tạo với ba tham số.

    int Horner( int a[], int n, int x)

3. Một biến result được tạo và khởi tạo với phần tử đầu tiên của mảng bằng cách hủy tham chiếu con trỏ. Con trỏ *a giống như cách viết arr[0] .

    int result = * a;

   Trong ví dụ trước, phương thức Horner cần một thành phần kích thước được gắn vào mảng của nó: int result = a[n]; để trỏ đến phần tử cuối cùng. Ở đây, nó chỉ được hủy đăng ký.

4. Một vòng lặp for được tạo lặp đi lặp lại từ 1 đến n . Trong mỗi lần lặp, giá trị của biến result được cập nhật với giá trị của đa thức.

   Giá trị của result được trả về ở cuối phương thức.

    for ( int i = 1 ; i < n; i ++ ) result = result * x + a[i]; return result;

5. Bên trong hàm main , một mảng được tạo với giá trị của các hệ số. Đa thức được sử dụng ở đây là:

   $$
   p(x) = 5x^4 + 3x^3 – 2x^2 + 4x – 6; x=-2
   $$

   Mảng được tạo bằng cách lấy các hệ số của đa thức – int arr[] = {5,3,-2,4,-6}; .

6. Biến n chứa bậc của đa thức. Giá trị của n được tính bằng: n = size of array -1 .

    int n = ( * ( & arr + 1 ) - arr) - 1 ; // n = size of the array - 1;

7. Phương thức Horner được gọi bằng cách chuyển mảng, giá trị của n và giá trị tại x . Kết quả trả về được lưu trữ trong một biến số nguyên mới và được in ra.

    int sol = Horner(arr, n, - 2 ); std :: cout << "Value of polynomial = " << sol;

Mã số:

#include <iostream>
int Horner(int a[], int n, int x)
{
    int result = *a;
    for (int i = 1; i < n; i++)
        result = result * x + a[i];
    return result;
}

int main() {
    int arr[] = {5,3,-2,4,-6};
    int n = (*(&arr + 1) - arr)-1;
    int sol = Horner(arr, n, -2);
    std::cout << "Value of polynomial = " << sol;
}

Đầu ra (Chuyển tiếp quy tắc Horner trong C++):

Value of polynomial = -20

Sử dụng đệ quy để tìm giá trị của đa thức bằng quy tắc Horner trong C++

Cho đến giờ, chúng ta đã học cách tìm giá trị của đa thức bằng cách sử dụng quy tắc Horner trong C++. Nó được thực hiện bằng cách lặp lại các vòng lặp và cập nhật số đếm bằng biến tích lũy.

Trong ví dụ này, giá trị của đa thức được tính bằng đệ quy. Hãy nhìn vào mã.

1. Dòng mã đầu tiên nhập gói iostream và xác định không gian tên là std .

    #include <iostream>
   using namespace std;

2. Một phương thức Horner được tạo có ba tham số – một số nguyên con trỏ *pi , một biến số nguyên khác degree , là bậc của đa thức (được sử dụng như n trong ví dụ trước) và x để truyền giá trị tại x .

    int Horner( int * pi, int degree, int x)

3. Đặc điểm của hàm đệ quy là tiếp tục gọi chính nó như một vòng lặp cho đến khi thỏa mãn điều kiện, giúp giảm độ phức tạp về thời gian. Đối với điều kiện, câu lệnh if trả về giá trị của pi ở chỉ số thứ 0 chỉ khi giá trị của độ đã giảm xuống 0.

    if (degree == 0 ) { return pi[ 0 ]; }

4. Để áp dụng đệ quy, phương thức Horner được gọi lại thay vì trả về một giá trị.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   Cú pháp trên giữ cho phương thức Horner gọi chính nó nhiều lần cho bậc của đa thức hiện tại. Trong một phương trình, bậc của đa thức là số mũ cao nhất của nó.

   Nếu phương trình được sử dụng trong ví dụ trước được xem xét:

   $$ p(x) = 5x^4 + 3x^3 – 2x^2 + 4x – 6; x=-2 $$

   Bậc của đa thức là 4.

   Điều này có nghĩa là đệ quy sẽ tự lặp lại n+1 = 5 lần (kích thước của mảng). Tại mỗi lần lặp, phương thức sẽ tự gọi cho đến khi giá trị của độ giảm xuống 0 .

   Khi nó đạt đến 0 , đệ quy sẽ lấy phần tử *p[0] và chuyển nó vào lời gọi phương thức trước đó của nó.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   Nó cũng giống như việc mở một phong bì bên trong phong bì cho đến khi mở đến phong bì cuối cùng rồi gấp lại. Giá trị ở lần gọi phương thức cuối cùng được chuyển đến lần gọi phương thức trước đó và các phép tính được thực thi.

5. Bên trong hàm main , một mảng số nguyên được tạo để truyền các hệ số của phương trình cho phương thức Horner . Sau đó, giá trị của các tham số được truyền cho phương thức.

    int sol = Horner(arr, 4 , - 2 );

   Mảng là arr , độ – 4 và giá trị tại x , là -2 .

6. Cuối cùng, kết quả trả về được lưu trữ trong một biến số nguyên sol và được in ra.

Mã số:

#include <iostream>
using namespace std;

int Horner(int* pi, int degree, int x)
{
    if (degree == 0)
    {
        return pi[0];
    }
    return Horner(pi, degree - 1, x) * x + pi[degree];
}
int main() {
    int arr[] = { 5,3,-2,4,-6 };
    int sol = Horner(arr, 4, -2);
    cout << "Value of Polynomial using recursion = " << sol;
}

Đầu ra:

Value of Polynomial using recursion = 34

Sự kết luận

Bài viết này giải thích cách tìm giá trị của đa thức bằng quy tắc Horner trong C++. Ba phương pháp có độ phức tạp về thời gian khác nhau có thể là một công cụ học tập tuyệt vời cho người đọc.

Bạn nên thử tự viết mã và sau đó quay lại để nhận gợi ý. Bạn đọc sẽ dễ dàng hiểu được khái niệm tìm giá trị của đa thức bằng quy tắc Horner trong C++.

Viết bởi Duy Mạnh. Đã đăng ký bản quyền tác giả tại Creativecommons và DMCA