Даны натуральное число [latex]n[/latex], действительный числа [latex]x[/latex], [latex]a_{n}, a_{n-1}, \ldots, a_{0}[/latex]. Вычислить используя схему Горнера, значение [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0}.[/latex] [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0} = \left( \ldots \left(a_{n}{x} + a_{n-1}\right)x + \cdots + a_{1}\right)x + a_{0}.[/latex]
| [latex]n[/latex] | [latex]x[/latex] | [latex]{a}_{n}[/latex] | [latex]{a}_{n-1}[/latex] | [latex]{a}_{n-2}[/latex] | [latex]{a}_{n-3}[/latex] | [latex]s[/latex] |
| 3 | 2 | 5 | 4 | 3 | 2 | 64 |
| 2 | 1 | 3 | 4 | 7 | _ | 14 |
| 3 | 0 | 3 | 4 | 12 | 8 | 8 |
| 3 | 5 | 0 | 10 | 12 | 8 | 318 |
| 1 | 5 | 2 | 1 | _ | _ | 11 |
Начинаем с коэффициента с рядом с [latex]X[/latex]-ом c максимальной степенью, у нас это элемент [latex]{a}_{n}[/latex], мы последовательно умножаем его (коэффициент) на [latex]X[/latex], а потом прибавляем следующий считанный коэффициент и сохраняем полученное значение в переменной.
Это был пример решения для [latex]n=2[/latex], если же [latex]n>2[/latex], то мы должны выполнить алгоритм для [latex]n=2[/latex], после чего [latex]n-2[/latex] раз умножать полученное в переменной значение на [latex]X[/latex] и прибавлять последующий элемент.
Осталось только написать программу: http://ideone.com/ScO3aw.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <cstdlib> #include <iostream> using namespace std; int main() { int n, x; cin >> n >> x; int a[n+1]; for (int i = n; i >= 0; --i) { cin >> a[i]; } int s = a[n]; for (int i = 1; i <= n; ++i) { s *= x; s += a[n-i]; } cout << s << endl; } |