CodeLAB
на главную карта сайта обратная связь

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

#Поверхностное клонирование. (28136 hits)
#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (391200 hits)
#Рисование линии (по Брезенхэму). (34488 hits)
#Интерактивная, динамическая подгрузка картинок. (70337 hits)
#Заливка замкнутой области. (62962 hits)
#Посчитать количество пар чисел (number of equal pairs). (5504 hits)
#Овал, вписанный в прямоугольник. (38426 hits)
#Древовидные структуры. (57867 hits)
#Случайный выбор элемента при неизвестном их количестве. (37142 hits)
#Бинарный поиск в массиве и его разновидности. (170738 hits)
#Замена символа строки. (444005 hits)
#Преобразование сумм из цифрового представления в строковое. (176769 hits)
#Поиск дубликатов внутри файла. (31833 hits)
#Шейкер-сортировка. (71916 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (61499 hits)
#Глубокое полное клонирование. (36337 hits)
#Валидация, динамическая проверка заполнения html форм. (209904 hits)
#Двусторонняя карта. (34504 hits)
#Динамическое формирование выпадающего списка. (52465 hits)
#Создание простейшей таблицы. (37601 hits)


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

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

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

Рассмотрим программу для расчета значения полинома в общем виде:
y = anxn + an-1xn-1 + ... + a1x1 + a0

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

 псевдокод: Первоначальный вариант  ссылка
  1. y = a[0]
  2. xi = 1
  3. for i = 1 to n
  4. xi = x * xi
  5. y = y + a[i] * xi

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

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

 псевдокод: Схема Горнера, вдвое быстрый вариант  ссылка
  1. y = a[n]
  2. for i = n-1 downto 0
  3. y = x * y + a[i]

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

Реализации:

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

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