Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:محاسبه ی مقدار چندجمله ای

محاسبه‌ی مقدار چند‌جمله‌ای

به دنبال راهی با کد کوتاه، عملیات کم و فهم راحت هستیم. در زیر به یک روش با تعداد عملیات ۲n میپردازیم.

تعریف

فرض کنید ضرایب یک چند جمله‌ای را به ترتیب به صورت a0,a1,...,an به شما داده اند که ai ضریب جمله‌ی xi می‌باشد. به ازای یک x خاص، مقدار این چند‌جمله‌ای را محاسبه کنید.

الگوریتم

a0 را از آرایه حذف کنید و فرض کنید آرایه شما به شکل زیر است: a1,a2,...,an که ai ضریب جمله‌ی xi1 است. حال به صورت استقرایی مقدار p را برابر با جواب چند‌جمله‌ای به ازای آرایه بالا در نظر بگیرید. اکنون جواب شما به ازای آرایه‌ی اصلی برابر است با: px+a0

پیچیدگی‌ الگوریتم

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

پیاده‌سازی

‌‌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;
}

مراجع


ابزار صفحه