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

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

#Часики на js. (93802 hits)

#Косинус. (40045 hits)

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

#Как работать с zip архивами стандартными средствами windows. (42391 hits)

#Программное создание ссылок. (100113 hits)

#Вычисление минимального / максимального значения. (74736 hits)

#Сапер. (53678 hits)

#Преобразование целых чисел в битовый массив. (37890 hits)

#Предварительная загрузка изображений. (47449 hits)

#Преобразование сумм из цифрового представления в строковое. (176235 hits)

#Просмотр изображения во всплывающем окне. (89539 hits)

#Вращение фигуры в плоскости. (40244 hits)

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

#Работа с камерой. (36044 hits)

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

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

#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (390326 hits)

#Наибольший общий делитель. (193134 hits)

#Двусторонняя карта. (34276 hits)

#Последовательный поиск и его оптимизации. (44876 hits)

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

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

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

Aвтор:this
Дата: 12.08.2004
Просмотров: 62373
реализации(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]

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

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