Завдання № 27. Обчислити значення многочлена в точці » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 27. Обчислити значення многочлена в точці

 

Завдання № 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 + 2n), що приблизно відповідає асімптотіче-ської складності 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), що демон-стрірует очевидну перевагу перед попереднім рішенням.
    Подивимося, як може виглядати цикл, в якому обчислюється значення многочлена в точ-ке. Для цього трохи змінимо уявлення у вигляді схеми Горнера, не змінюючи при цьому значення многочлена: (((0x + 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. var
  3. i, n: byte;
  4. x, a, res: real;
  5. begin
  6. readln(n, x);
  7. res := 0;
  8. for i := 1 to n + 1 do begin
  9.   read(a);
  10.   res := res * x + a
  11. end;
  12. writeln(res:4:2)
  13. end.

0027.-ValueOfPolynomial.rar [647 b] (cкачувань: 2)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 28. Обчислити факторіал Попередня сторінка » Завдання № 26. Вирішити квадратне рівн...