多项式求值的霍纳方法-yiteyi-C++库

给定一个c形式的多项式 _N 十、 ^N +c _n-1 十、 ^n-1 +c _n-2 十、 ^n-2 +…+c _1. x+c ₀ 对于给定的x值，求多项式的值 _N C _n-1 , .. 是整数（可能是负数），n是正整数。输入是数组的形式 聚[] 其中poly[0]表示x的系数 ^N poly[1]表示x的系数 ^n-1 等等 例如：

null

// Evaluate value of 2x³ - 6x² + 2x - 1 for x = 3Input: poly[] = {2, -6, 2, -1}, x = 3Output: 5// Evaluate value of 2x³ + 3x + 1 for x = 2Input: poly[] = {2, 0, 3, 1}, x = 2Output: 23

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

计算多项式的一种简单方法是逐个计算所有项。首先计算x ^N ，将该值乘以c _N ，对其他条件重复相同的步骤，并返回总和。该方法的时间复杂度为O（n） ^2. )如果我们用一个简单的循环来计算x ^N .如果我们使用 O（Logn）评估x的方法 ^N . 霍纳法 可以用来计算O（n）时间内的多项式。为了理解这个方法，让我们考虑2X的例子。 ^3. –6倍 ^2. +2x–1。多项式可以计算为（（2x–6）x+2）x–1。其思想是将结果初始化为x的系数 ^N 在这种情况下，重复将结果乘以x，然后将下一个系数加到结果上。最后返回结果。下面是霍纳方法的实现。

C++

                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // returns value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]                       
                         int                                     horner(                                     int                                     poly[],                                     int                                     n,                                     int                                     x)                       
                         {                       
                                                 int                                     result = poly[0];                                     // Initialize result                       
           
                                                 // Evaluate value of polynomial using Horner's method                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 result = result*x + poly[i];                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver program to test above function.                       
                         int                                     main()                       
                         {                       
                                                 // Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3                       
                                                 int                                     poly[] = {2, -6, 2, -1};                       
                                                 int                                     x = 3;                       
                                                 int                                     n =                                     sizeof                                     (poly)/                                     sizeof                                     (poly[0]);                       
                                                 cout <<                                     "Value of polynomial is "                                     << horner(poly, n, x);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for implementation of Horner Method                       
                         // for Polynomial Evaluation                       
                         import                                     java.io.*;                       
           
                         class                                     HornerPolynomial                       
                         {                       
                                                 // Function that returns value of poly[0]x(n-1) +                       
                                                 // poly[1]x(n-2) + .. + poly[n-1]                       
                                                 static                                     int                                     horner(                                     int                                     poly[],                                     int                                     n,                                     int                                     x)                       
                                                 {                       
                                                 // Initialize result                       
                                                 int                                     result = poly[                                     0                                     ];                       
                                   
                                                 // Evaluate value of polynomial using Horner's method                       
                                                 for                                     (                                     int                                     i=                                     1                                     ; i<n; i++)                       
                                                 result = result*x + poly[i];                       
                                   
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 // Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3                       
                                                 int                                     [] poly = {                                     2                                     , -                                     6                                     ,                                     2                                     , -                                     1                                     };                       
                                                 int                                     x =                                     3                                     ;                       
                                                 int                                     n = poly.length;                       
                                                 System.out.println("Value of polynomial is "                       
                                                 + horner(poly,n,x));                       
                                                 }                       
                         }                       
           
                         // Contributed by Pramod Kumar                       

Python3

                         # Python program for                       
                         # implementation of Horner Method                       
                         # for Polynomial Evaluation                       
           
                         # returns value of poly[0]x(n-1)                       
                         # + poly[1]x(n-2) + .. + poly[n-1]                       
                         def                                     horner(poly, n, x):                       
           
                                                 # Initialize result                       
                                                 result                                     =                                     poly[                                     0                                     ]                       
                                   
                                                 # Evaluate value of polynomial                       
                                                 # using Horner's method                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
           
                                                 result                                     =                                     result                                     *                                     x                                     +                                     poly[i]                       
                                   
                                                 return                                     result                       
                                   
                         # Driver program to                       
                         # test above function.                       
           
                         # Let us evaluate value of                       
                         # 2x3 - 6x2 + 2x - 1 for x = 3                       
                         poly                                     =                                     [                                     2                                     ,                                     -                                     6                                     ,                                     2                                     ,                                     -                                     1                                     ]                       
                         x                                     =                                     3                       
                         n                                     =                                     len                                     (poly)                       
           
                         print                                     ("Value of polynomial                                     is                                     " , horner(poly, n, x))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program for implementation of                       
                         // Horner Method  for Polynomial Evaluation.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function that returns value of poly[0]x(n-1) +                       
                                                 // poly[1]x(n-2) + .. + poly[n-1]                       
                                                 static                                     int                                     horner(                                     int                                     []poly,                                     int                                     n,                                     int                                     x)                       
                                                 {                       
                                                 // Initialize result                       
                                                 int                                     result = poly[0];                       
           
                                                 // Evaluate value of polynomial                       
                                                 // using Horner's method                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 result = result * x + poly[i];                       
           
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 // Let us evaluate value of                       
                                                 // 2x3 - 6x2 + 2x - 1 for x = 3                       
                                                 int                                     []poly = {2, -6, 2, -1};                       
                                                 int                                     x = 3;                       
                                                 int                                     n = poly.Length;                       
                                                 Console.Write("Value of polynomial                                     is                                     "                       
                                                 + horner(poly,n,x));                       
                                                 }                       
                         }                       
           
                         // This code Contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program for implementation                       
                         // of Horner Method for Polynomial                       
                         // Evaluation.                       
           
                         // returns value of poly[0]x(n-1) +                       
                         // poly[1]x(n-2) + .. + poly[n-1]                       
                         function                                     horner(                                     $poly                                     ,                                     $n                                     ,                                     $x                                     )                       
                         {                       
                                                 // Initialize result                       
                                                 $result                                     =                                     $poly                                     [0];                       
           
                                                 // Evaluate value of polynomial                       
                                                 // using Horner's method                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $result                                     =                                     $result                                     *                       
                                                 $x                                     +                                     $poly                                     [                                     $i                                     ];                       
           
                                                 return                                     $result                                     ;                       
                         }                       
           
                         // Driver Code                       
           
                         // Let us evaluate value of                       
                         // 2x3 - 6x2 + 2x - 1 for x = 3                       
                         $poly                                     =                                     array                                     (2, -6, 2, -1);                       
                         $x                                     = 3;                       
                         $n                                     = sizeof(                                     $poly                                     ) / sizeof(                                     $poly                                     [0]);                       
           
                         echo                                     "Value of polynomial is "                                     .                       
                                                 horner(                                     $poly                                     ,                                     $n                                     ,                                     $x                                     );                       
           
                         // This code is contributed by mits.                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program for implementation                       
                         // of Horner Method for Polynomial                       
                         // Evaluation.                       
           
                         // returns value of poly[0]x(n-1) +                       
                         // poly[1]x(n-2) + .. + poly[n-1]                       
                         function                                     horner(poly, n, x)                       
                         {                       
           
                                                 // Initialize result                       
                                                 let result = poly[0];                       
           
                                                 // Evaluate value of polynomial                       
                                                 // using Horner's method                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 result = result *                       
                                                 x + poly[i];                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver Code                       
           
                         // Let us evaluate value of                       
                         // 2x3 - 6x2 + 2x - 1 for x = 3                       
                         let poly =                                     new                                     Array(2, -6, 2, -1);                       
                         let x = 3;                       
                         let n = poly.length                       
           
                         document.write(                                     "Value of polynomial is "                                     +                       
                                                 horner(poly, n, x));                       
           
                         // This code is contributed by _saurabh_jaiswal.                       
                         </script>                       

输出：

Value of polynomial is 5

时间复杂性 ：O（n）

辅助空间： O（1）如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章