Encuentre el valor del polinomio usando la regla de Horner en C++

1. Encuentre el valor del polinomio usando la regla de Horner en C++ iterando el bucle hacia atrás
2. Encuentre el valor del polinomio usando la regla de Horner en C++ iterando el bucle hacia adelante
3. Use la recursividad para encontrar el valor del polinomio usando la regla de Horner en C++
4. Conclusión

La regla de Horner es un algoritmo eficiente para calcular el valor de un polinomio.

Considere el polinomio p(x) = 6x^3 - 2x^2 + 7x + 5 en x = 4. Para calcularlo usando la regla de Horner en C++, el primer coeficiente, 6, se multiplica por el valor en x, que es 4, y el producto de los dos, que es 24, se suma al siguiente coeficiente -2.

La resultante se multiplica por 4 y se suma al siguiente coeficiente.

Este proceso se repite para el número de coeficientes en la ecuación. El producto final que queda es el valor del polinomio.

Este artículo explica cómo encontrar el valor de un polinomio usando la regla de Horner en C++ al convertir las reglas anteriores en código de computadora.

Consideremos un polinomio:

Si x = 4, el valor del polinomio es 385.

Encuentre el valor del polinomio usando la regla de Horner en C++ iterando el bucle hacia atrás

Veamos el programa que encuentra el valor de un polinomio usando la regla de Horner en C++ mediante bucle inverso.

1. La primera línea de código importa el paquete de biblioteca iostream; en la segunda línea, el espacio de nombres se define como std.

2. Se crea un método int Horner() con tres parámetros: una matriz de punteros a que pasará la lista de coeficientes, una variable entera n que almacena el grado del polinomio y otra variable entera x que almacena el valor del polinomio en x.

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

3. Esto explica cómo sumar el producto de polinomios entre sí. Se crea una variable entera resultado, inicializada con el último elemento del arreglo a[n].

   int result = a[n];
   

   Nota: No lo confunda con el tamaño de la matriz; inicializa la variable resultado con el elemento del arreglo a en la n-ésima posición.

4. Se crea un bucle for, invirtiendo el bucle desde el último elemento de la matriz a hasta el índice 0. El valor de la variable resultado se actualiza para cada iteración del bucle.

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

   En la primera iteración, el valor de a[n] se multiplica por x y luego se suma al elemento anterior de la matriz: a[n-1]. Para una matriz - {2,3,4}, el bucle tomará el último elemento a[n], que es 4, lo multiplicará por x, y luego lo sumará al elemento n-1 de la matriz, que es 3.

   Por esta razón, los coeficientes deben invertirse al inicializar en la función main. El valor de resultado se devuelve al final del método.

5. Dentro de la función main, se crea un array para pasarlo al primer parámetro del método Horner. Tenga en cuenta que el valor de los coeficientes dentro de la matriz se invierte porque el ciclo itera hacia atrás.

6. Se crea una variable entera sol para almacenar el resultado devuelto por el método denominado Horner.

   En el primer parámetro se pasa el array que se está creando. El segundo parámetro pasa el grado de los polinomios en la ecuación, 3, y el tercer parámetro pasa el valor en x.

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

Código:

#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;
}

Salida (regla de Horner de bucle inverso en C++):

385

Encuentre el valor del polinomio usando la regla de Horner en C++ iterando el bucle hacia adelante

Si necesitamos ejecutar el bucle hacia adelante, a diferencia del último ejemplo, podemos eliminar la referencia del puntero de la matriz para obtener su primer elemento y ejecutar el bucle hacia adelante en lugar de invertirlo. Es otra forma de usar bucles para implementar la regla de Horner en C++.

Entendamos lo que hace el código:

1. La primera línea de código importa el paquete de biblioteca iostream.

2. Similar al ejemplo anterior, se crea un método Horner con tres parámetros.

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

3. Se crea una variable resultado y se inicializa con el primer elemento de la matriz desreferenciando el puntero. El puntero *a es lo mismo que escribir arr[0].

   int result = *a;
   

   En el ejemplo anterior, el método Horner necesitaba un componente de tamaño adjunto a su matriz: int result = a[n]; para señalar el último elemento. Aquí, simplemente está desreferenciado.

4. Se crea un bucle for que itera de 1 a n. En cada iteración, el valor de la variable resultado se actualiza con el valor del polinomio.

   El valor de resultado se devuelve al final del método.

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

5. Dentro de la función main, se crea una matriz con el valor de los coeficientes. El polinomio utilizado aquí es:

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

   La matriz se crea tomando los coeficientes de los polinomios - int arr[] = {5,3,-2,4,-6};.

6. La variable n contiene el grado del polinomio. El valor de n se calcula mediante: n = tamaño del arreglo -1.

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

7. El método Horner se llama pasando la matriz, el valor de n y el valor en x. El resultado devuelto se almacena en una nueva variable entera y se imprime.

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

Código:

#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;
}

Salida (regla de Horner de bucle hacia adelante en C++):

Value of polynomial = -20

Use la recursividad para encontrar el valor del polinomio usando la regla de Horner en C++

Hasta ahora, hemos aprendido a encontrar el valor de un polinomio usando la regla de Horner en C++. Se hizo iterando bucles y actualizando el conteo usando una variable acumuladora.

En este ejemplo, el valor del polinomio se calcula por recursión. Veamos el código.

1. La primera línea de código importa el paquete iostream y define el espacio de nombres como std.

   #include <iostream>
   using namespace std;
   

2. Se crea un método Horner que tiene tres parámetros: un puntero entero *pi, otra variable entera grado, que es el grado del polinomio (usado como n en el ejemplo anterior), y x para pasar el valor en x.

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

3. La característica de la función recursiva es seguir llamándose a sí misma como un bucle hasta que se cumpla una condición, lo que reduce la complejidad del tiempo. Para la condición, una instrucción if devuelve el valor de pi en el índice 0 solo si el valor del grado se ha reducido a 0.

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

4. Para aplicar la recursividad, se vuelve a llamar al método Horner en lugar de devolver un valor.

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

   La sintaxis anterior mantiene el método Horner para llamarse a sí mismo repetidamente por el grado del polinomio presente. En una ecuación, el grado del polinomio es su máximo exponente.

   Si se considera la ecuación utilizada en el último ejemplo:

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

   El grado del polinomio es 4.

   Esto significa que la recursividad se repetirá a sí misma para n+1 = 5 veces (tamaño de la matriz). En cada iteración, el método se llamará a sí mismo hasta que el valor del grado se reduzca a 0.

   Una vez que llegue a 0, la recursividad tomará el elemento *p[0] y lo pasará a su llamada de método anterior.

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

   Es lo mismo que abrir un sobre dentro de un sobre hasta llegar al último y luego volver a doblarlo. El valor de la última llamada al método se pasa a la llamada al método anterior y se ejecutan los cálculos.

5. Dentro de la función main, se crea una matriz de enteros para pasar los coeficientes de la ecuación al método Horner. Luego, el valor de los parámetros se pasa al método.

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

   La matriz es arr, grado - 4, y valor en x, que es -2.

6. Por último, el resultado devuelto se almacena en una variable entera sol y se imprime.

Código:

#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;
}

Producción :

Value of Polynomial using recursion = 34

Conclusión

Este artículo explica cómo encontrar el valor de polinomios usando la regla de Horner en C++. Los tres métodos tienen diferentes complejidades de tiempo que pueden ser una gran herramienta de aprendizaje para el lector.

Se recomienda intentar escribir los códigos usted mismo y luego regresar para obtener sugerencias. El lector entenderá fácilmente los conceptos de encontrar el valor de polinomios usando la regla de Horner en C++.