Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Задача № 27. Вычислить значение многочлена в точке





Формулировка. Дано натуральное число n, вещественное число x и набор вещественных чисел an, an-1,..., a0. Вычислить значение многочлена n -ной степени с коэффициентами an, an-1,..., a0 от одной переменной в точке x.

Примечание: многочленом n -ной степени от одной переменной x называется выражение вида anxn + an-1xn-1 +... + a1x + a0, где an, an-1,..., a0 – коэффициенты.

Решение. Собственно, в этой задаче требуется возведение переменной x (точнее, конкретного ее значения) в некоторую степень n – 1 раз, а также n операций умножения и n операций сложения. В принципе, для полноценного решения она не требует одновременного знания более чем одного коэффициента, так как мы можем в цикле ввести коэффициент an в переменную a, умножить его на xn и прибавить полученное число к переменной результата res (которой перед входом в цикл должно быть присвоено значение 0) и повторить этот шаг для всех коэффициентов. Тогда количество операций: (1 + 2 +... + n + 2 n), что примерно соответствует асимптотической сложности O(n2).

Не занимаясь реализацией этого алгоритма, давайте оптимизируем его. Например, пусть нам дан многочлен третьей степени a3x3 + a2x2 + a1x + a0. Вынесем за скобки общий множитель x при слагаемых, в которых это возможно. Получим: (a3x2 + a2x + a1) x + a0. Вынесем за скобки x также и в полученном выражении со скобками, в итоге получим: ((a3x + a2) x + a1) x + a0.

Полученную форму записи называют схемой Горнера. Очевидно, что она существует для многочлена любой степени.

Итак, имея n = 3 и коэффициенты a3, a2, a1 и a0, мы можем посчитать его значение с помощью n операций умножения и n операций сложения, а это значит, что для вычисления требуется порядка 2n операций и алгоритм имеет линейную асимптотическую сложность O(n), что демонстрирует очевидное преимущество перед предыдущим решением.

Посмотрим, как может выглядеть цикл, в котором вычисляется значение многочлена в точке. Для этого немного изменим представление в виде схемы Горнера, не меняя при этом значения многочлена: (((0 x + a3) x + a2) x + a1) x + a0.

Теперь нам требуется n + 1 операций, однако заведя переменную res для накопления результата, которая перед входом в цикл будет равна 0, мы можем, вводя коэффициенты a3, a2, a1 и a0, посчитать значение многочлена в одном цикле:

res:= 0;

for i:= 1 to n + 1 do begin

read(a);

res:= res * x + a

end;

Примечание: оператор read нужен нам для того, чтобы можно было вводить коэффициенты через пробел, а не через Enter.

Теперь разберем сам цикл. На первом шаге мы получаем в res значение выражения 0x + a3 = a3, на втором – a3x + a2, на третьем – (a3x + a2) x + a1, на четвертом – ((a3x + a2) x + a1) x + a0. Как видно, формула полностью восстановилась, причем вычисление идет от наиболее вложенных скобок к верхним уровням.

Код:

1. program ValueOfPolynomial; 2. 3. var 4. i, n: byte; 5. x, a, res: real; 6. 7. begin 8. readln(n, x); 9. res:= 0; 10. for i:= 1 to n + 1 do begin 11. read(a); 12. res:= res * x + a 13. end; 14. writeln(res:4:2) 15. end.

Date: 2015-11-14; view: 401; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию