Dado un polinomio de la forma c n x n + c n-1 x n-1 + c n-2 x n-2 + … + c 1 x + c 0 y un valor de x, encuentre el valor del polinomio para a valor dado de x. Aquí c n , c n-1 , .. son números enteros (pueden ser negativos) y n es un número entero positivo.
La entrada tiene la forma de una array, digamos poly[], donde poly[0] representa el coeficiente para x n y poly[1] representa el coeficiente para x n-1 y así sucesivamente.
Ejemplos:
// Evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
Input: poly[] = {2, -6, 2, -1}, x = 3
Output: 5
// Evaluate value of 2x3 + 3x + 1 for x = 2
Input: poly[] = {2, 0, 3, 1}, x = 2
Output: 23
Una forma ingenua de evaluar un polinomio es evaluar uno por uno todos los términos. Primero calcule x n , multiplique el valor por c n , repita los mismos pasos para otros términos y devuelva la suma. La complejidad temporal de este enfoque es O(n 2 ) si usamos un ciclo simple para la evaluación de x n . La complejidad del tiempo se puede mejorar a O(nLogn) si usamos el enfoque O(Logn) para la evaluación de x n .
El método de Horner se puede utilizar para evaluar polinomios en tiempo O(n). Para comprender el método, consideremos el ejemplo de 2x 3 – 6x 2 + 2x – 1. El polinomio se puede evaluar como ((2x – 6)x + 2)x – 1. La idea es inicializar el resultado como coeficiente de x norteque es 2 en este caso, multiplique repetidamente el resultado con x y agregue el siguiente coeficiente al resultado. Finalmente devuelve resultado.
A continuación se muestra la implementación del método de Horner.
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>
Producción:
Value of polynomial is 5
Complejidad de tiempo : O(n)
Espacio auxiliar: O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA