Bài viết đăng tại: https://programming.laptrinh.site
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.
Nội dung
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.
-
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
. -
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ênn
lưu trữ bậc của đa thức và một biến số nguyên khácx
lưu trữ giá trị của đa thức tạix
.int Horner(
int
* a,
int n,
int x)
-
Đ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ảnga[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ảnga
ở vị trí thứ n. -
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ảnga
sang chỉ số thứ 0. Giá trị của biếnresult
đượ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ớix
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ùnga[n]
, là 4, nhân nó vớix
, 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ủaresult
được trả về ở cuối phương thức. -
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ứcHorner
. 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. -
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ênHorner
.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:
-
Dòng mã đầu tiên nhập gói thư viện
iostream
. -
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)
-
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ếtarr[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ý. -
Một vòng lặp
for
được tạo lặp đi lặp lại từ 1 đếnn
. Trong mỗi lần lặp, giá trị của biếnresult
đượ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;
-
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};
. -
Biến
n
chứa bậc của đa thức. Giá trị củan
được tính bằng:n = size of array -1
.int n
= (
* (
& arr
+
1 )
- arr)
-
1 ;
// n = size of the array - 1;
-
Phương thức
Horner
được gọi bằng cách chuyển mảng, giá trị củan
và giá trị tạix
. 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ã.
-
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;
-
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ácdegree
, 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ạix
.int Horner(
int
* pi,
int degree,
int x)
-
Đặ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ủapi
ở chỉ số thứ 0 chỉ khi giá trị của độ đã giảm xuống 0.if (degree
==
0 )
{
return pi[
0 ];
}
-
Để á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ống0
.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.
-
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ứcHorner
. 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ạix
, là-2
. -
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++.
URL Link
https://laptrinh.site/tim-gia-tri-cua-da-thuc-bang-quy-tac-horner-trong-c/
Viết bởi Duy Mạnh. Đã đăng ký bản quyền tác giả tại Creativecommons và DMCA