[変分法則]ホーナー法則C ++コードの実装、与えられた点での多項式の値を見つける
Horners Rule C Code Implementation
1.ホルネルの法則アルゴリズムの原理
n + 1個の実数a0、a1、...、an、およびxのシーケンスがあり、多項式Pn(x)= anx ^ n + a(n-1)x ^(n-1)+であるとします。 .. + a1x + a0が評価されます。次の変換、つまりPn(x)= anx ^ n + a(n-1)x ^(n-1)+…+ a1x + a0 =((…(((anx + an-1)x + an-2)x + an-3)...)x + a1)x + a0。この評価の取り決めは、ホルネルの法則と呼ばれます。
たとえば、x = 3の場合、p(x)= 2x ^ 4-x ^ 3 + 3x ^ 2 + x-5の値を計算します。多項式p(x)= 2x ^ 4-x ^ 3 + 3x ^ 2 + x-5の場合、ホルネルの法則に従って変換を実行します。
p(x)= 2x ^ 4-x ^ 3 + 3x ^ 2 + x-5
=x(2x^3-x^2+3x+1)-5
=x(x(2x^2-x+3)+1)-5
=x(x(x(2x-1)+3)+1)-5
2.ホルネルの法則の2次元テーブル計算
①実際の運用プロセスでは、多項式係数の元のリストのみが必要です。
②表の最初の行には、a0の最高値から最低値までの多項式の係数が含まれています(0に等しい係数がある場合は、すべて含まれています)。
③xとanを格納するために使用される2行目の1番目と2番目のセルを除いて、他のセルは中間結果を格納するために使用されます。
④このような初期化の後、2行目のセルの値を計算するときは、xの値にセルの前のセルを掛けて、セルの最初の行の係数を加算します。できる。この方法で計算された最後のセルの値は、多項式の値です。
最大数はnで、テーブル列の数はn +1です。
三、ホルネルの法典の実装
①疑似コード:
Horner(P[0..n],x) //Use Horner's law to find the value of a polynomial at a given point //Input: a coefficient array P[0..n] of n-degree polynomial (stored from low to high), and a number x //Output: the value of the polynomial at point x p<-P[n] for i<-n-1 downto 0 do p<-x*p+p[i] return p
②ホーナー法のC ++実装:
#include using namespace std int LEN = 3 int hornor(int list[],int n,int x) //Use recursion to implement Horner's rule { if(n == LEN-1) { return list[LEN-1]//Recursive export } else { return hornor(list,n+1,x)*x+list[n]//Recursive process } } int main() { int a[3]={1,2,3}//The array represents the coefficients of the polynomial int x=3//The value of the independent variable of the polynomial int result=0//Store results result = hornor(a,0,3) cout<' ' cout<exit(0) return 0 }