Вычисление значения полинома, реализации на C#

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

#Постепенное затемнение. (51549 hits)

#Посчитать количество пар чисел (number of equal pairs). (5067 hits)

#Случайный выбор нескольких несовпадающих значений из множества. (58924 hits)

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

#Рисование окружности (по Брезенхэму). (34106 hits)

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

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

#Сохранение данных формы после перезагрузки через куки. (205333 hits)

#Сравнение алгоритмов быстрой сортировки. (74147 hits)

#Рисование полусферы. (29217 hits)

#Древовидные структуры. (57647 hits)

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

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

#Относительный путь к файлу. (40033 hits)

#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (147684 hits)

#Код. (180385 hits)

#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (46493 hits)

#Пирамидальная сортировка. (204527 hits)

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

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

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

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

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

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

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

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