Рубрики

Метод Хорнера для полиномиальной оценки

Дан многочлен вида c n x n + c n-1 x n-1 + c n-2 x n-2 +… + c 1 x + c 0 и значения x, найти значение полинома для данного значения х. Здесь c n , c n-1 , .. являются целыми числами (могут быть отрицательными), а n является положительным целым числом.

Входные данные представлены в виде массива, скажем, poly [], где poly [0] представляет коэффициент для x n, а poly [1] представляет коэффициент для x n-1 и так далее.

Примеры:

// 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

Наивный способ оценить многочлен состоит в том, чтобы один за другим оценить все члены. Сначала вычислите x n , умножьте значение на c n , повторите те же шаги для других членов и верните сумму. Временная сложность этого подхода составляет O (n 2 ), если мы используем простой цикл для оценки x n . Временная сложность может быть улучшена до O (nLogn), если мы используем подход O (Logn) для оценки x n .

Метод Хорнера может быть использован для оценки полинома за O (n) времени. Чтобы понять метод, давайте рассмотрим пример 2x 3 — 6x 2 + 2x — 1. Полином можно оценить как ((2x — 6) x + 2) x — 1. Идея состоит в том, чтобы инициализировать результат как коэффициент x n, который в этом случае равен 2, многократно умножает результат на x и добавляет следующий коэффициент к результату. Наконец, верните результат.

Ниже приводится реализация метода Хорнера.

C / C ++

#include <iostream>

using namespace std;

  
// возвращает значение 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];  // Инициализировать результат

  

    // Оцениваем значение полинома по методу Хорнера

    for (int i=1; i<n; i++)

        result = result*x + poly[i];

  

    return result;

}

  
// Программа драйвера для проверки вышеуказанной функции.

int main()

{

    // Давайте оценим значение 2x3 - 6x2 + 2x - 1 для 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-программа для реализации метода Хорнера
// для полиномиальной оценки

import java.io.*;

  

class HornerPolynomial

{

    // Функция, которая возвращает значение poly [0] x (n-1) +

    // poly [1] x (n-2) + .. + poly [n-1]

    static int horner(int poly[], int n, int x)

    {

        // Инициализировать результат

        int result = poly[0];  

   

        // Оцениваем значение полинома по методу Хорнера

        for (int i=1; i<n; i++)

            result = result*x + poly[i];

   

        return result;

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        // Давайте оценим значение 2x3 - 6x2 + 2x - 1 для 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));

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python программа для
# реализация метода Хорнера
# для полиномиальной оценки

  
# возвращает значение poly [0] x (n-1)
# + poly [1] x (n-2) + .. + poly [n-1]

def horner(poly, n, x):

  

    # Инициализировать результат

    result = poly[0]  

   

    # Оценить значение полинома

    # используя метод Хорнера

    for i in range(1, n):

  

        result = result*x + poly[i]

   

    return result

   
# Драйвер программы для
# проверка над функцией.

  
# Давайте оценим ценность
# 2x3 - 6x2 + 2x - 1 для x = 3

poly = [2, -6, 2, -1]

x = 3

n = len(poly)

  

print("Value of polynomial is " , horner(poly, n, x))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для реализации
// Метод Горнера для полиномиальной оценки.

using System;

  

class GFG

{

    // Функция, которая возвращает значение poly [0] x (n-1) +

    // poly [1] x (n-2) + .. + poly [n-1]

    static int horner(int []poly, int n, int x)

    {

        // Инициализировать результат

        int result = poly[0]; 

  

        // Оцениваем значение полинома

        // используя метод Хорнера

        for (int i = 1; i < n; i++)

            result = result * x + poly[i];

  

        return result;

    }

      

    // Код драйвера

    public static void Main() 

    {

        // Давайте оценим ценность

        // 2x3 - 6x2 + 2x - 1 для 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));

    }

}

  
// Этот код предоставлен nitin mittal.

PHP

<?php
// PHP программа для реализации
// метода Хорнера для полинома
// Оценка.

  
// возвращает значение poly [0] x (n-1) +
// poly [1] x (n-2) + .. + poly [n-1]

function horner($poly, $n, $x)

{

    // Инициализировать результат

    $result = $poly[0]; 

  

    // Оцениваем значение полинома

    // используя метод Хорнера

    for ($i = 1; $i < $n; $i++)

        $result = $result

                  $x + $poly[$i];

  

    return $result;

}

  
// Код драйвера

  
// Давайте оценим ценность
// 2x3 - 6x2 + 2x - 1 для 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);

  
// Этот код предоставлен mits.
?>


Выход:

Value of polynomial is 5

Сложность времени : O (n)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Метод Хорнера для полиномиальной оценки

0.00 (0%) 0 votes