Вычисление значения полинома

Популярные задачи:

#Шифрование произвольных данных. (329119 hits)

#Обновление нескольких записей таблицы. (32715 hits)

#Заливка замкнутой области. (62702 hits)

#Масштабирование, пропорциональное изменение размеров картинки. (101361 hits)

#Создание нестандартного (custom-ного) окна браузера. (36125 hits)

#Загрузчик классов. (43675 hits)

#Переворот символов строки (или элементов одномерного массива). (112608 hits)

#Вычисление медианы заданной выборки. (49446 hits)

#Сглаживание кривой В-сплайном. (39017 hits)

#Преобразование RGB в HEX и обратно HEX в RGB. (56996 hits)

#Доступ ко всем полям и методам. (58225 hits)

#Шейкер-сортировка. (71537 hits)

#Перестановка фрагментов строки(или одномерного массива). (60973 hits)

#Овал, вписанный в прямоугольник. (38132 hits)

#Замена символа строки. (443573 hits)

#Добавление истории операций(undo&redo) в компонент. (40182 hits)

#Сортировка выбором, общий подход. (73131 hits)

#Выборка конкретной записи из таблицы. (33019 hits)

#Арктангенс. (45736 hits)

#Вращение 3D объекта. (36294 hits)

показать все >>

Главная >> Каталог задач >> Математика >> Вычисление значения полинома

Вычисление значения полинома

Aвтор:this
Дата: 12.08.2004
Просмотров: 62339
реализации(C#: 2шт...) +добавить

Рассмотрим программу для расчета значения полинома в общем виде:
y = a_nxⁿ + a_n-1x^n-1 + ... + a₁x¹ + a₀

Решение "в лоб" даст нам:

псевдокод: Первоначальный вариант ссылка

y = a[0]
xi = 1
for i = 1 to n
  xi = x * xi
  y = y + a[i] * xi

y = a[0]
xi = 1
for i = 1 to n
  xi = x * xi
  y = y + a[i] * xi

Код делает 2*n умножений(n - размерность полинома). Многовато, с учетом того, что умножение не самая элементарная операция. К счастью существует более быстрая программа.

По схеме Горнера значение полинома может быть вычислено, следующим образом:

псевдокод: Схема Горнера, вдвое быстрый вариант ссылка

y = a[n]
for i = n-1 downto 0
  y = x * y + a[i]

y = a[n]
for i = n-1 downto 0
  y = x * y + a[i]

В программе используется n умножений и она обычно работает вдвое быстрее.

Реализации:

C#(2) +добавить

1) Расчет полинома, решение "в лоб" на C#, code #88[автор:this]
2) Расчет полинома по схеме Горнера на C#, code #89[автор:this]

<< назад наверх

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей