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

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

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

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

#Простой генератор случайных чисел. (134324 hits)

#Улучшение быстрой сортировки. (77165 hits)

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

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

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

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

#Обработка шаблонных писем. (52921 hits)

#ООП на javascript: классы, наследование, инкапсуляция. (257802 hits)

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

#Простая геометрическая и текстовая анимация. (401127 hits)

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

#Рисование линии (по Брезенхэму). (34191 hits)

#Сортировка вставкой. (112455 hits)

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

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

#Рисование линии. (38964 hits)

#Динамическое формирование выпадающего списка. (52124 hits)

#Интерактивная, динамическая подгрузка картинок. (70014 hits)

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

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

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

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

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

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