====== محاسبه‌ی مقدار چند‌جمله‌ای ======
به دنبال راهی با کد کوتاه، عملیات کم و فهم راحت هستیم. در زیر به یک روش با تعداد عملیات $۲n$ میپردازیم.

===== تعریف =====
فرض کنید ضرایب یک چند جمله‌ای را به ترتیب به صورت 
$a_0, a_1, ..., a_n$
به شما داده اند که $a_i$ ضریب جمله‌ی $x^i$ می‌باشد.
به ازای یک $x$ خاص، مقدار این چند‌جمله‌ای را محاسبه کنید.

===== الگوریتم =====
$a_0$ را از آرایه حذف کنید و فرض کنید آرایه شما به شکل زیر است: 
$$a_1, a_2, ..., a_n$$
که $a_i$ ضریب جمله‌ی $x^{i-1}$ است. حال به صورت استقرایی مقدار $p$ را برابر با جواب چند‌جمله‌ای به ازای آرایه بالا در نظر بگیرید. اکنون جواب شما به ازای آرایه‌ی اصلی برابر است با:
$$p * x + a_0$$

===== پیچیدگی‌ الگوریتم =====
واضح است که پیچیدگی این الگوریتم از $O(n)$ می‌باشد.

===== پیاده‌سازی =====

<code cpp ‌‌horner.cpp>
#include <iostream>
using namespace std;
const int maxn = 1000 * 1000 + 10;
int a[maxn];
int main() {
    int n, x;
    cin >> n >> x;
    for(int i=0;i<=n;++i)
        cin >> a[i];
    
    int p = 0;
    for(int i=n;i>=0;--i)
       p = p * x + a[i];
    
    cout << p << endl;
    
    return 0;
}
</code>

===== مراجع =====
  * [[http://en.wikipedia.org/wiki/Horner%27s_method]]