برنامه ضرب چند جمله ای ها – راهنمای کاربردی

ورودی:

A[] = {5, 0, 10, 6}

B[] = {1, 2, 4}

خروجی:

prod[] = {5, 10, 30, 26, 52, 24}

اولین آرایه ورودی نشانگر چند جمله‌ای $$5 + 0x^1 + 10x^2 + 6x^3$$ است. دومین آرایه ورودی نشانگر چند جمله‌ای «$$1 + 2x^1 + 4x^2$$» است. یک راهکار ساده برای حل مساله بیان شده آن است که هر عبارت از اولین چند جمله‌ای در نظر گرفته و در هر عبارت از دومین چند جمله‌ای ضرب شود. در ادامه، الگوریتم این روش ساده آمده است.

ضرب ([A[0..m-1], B[0..n01)

1. ساخت آرایه حاصل ضرب به صورت []prod با اندازه m+n+1
2. مقداردهی اولیه همه ورودی‌ها در []prod با صفر
3. پیمایش آرایه []A و انجام اقدامات زیر برای هر عنصر [A[i
   • پیمایش آرایه []B و انجام اقدامات زیر برای هر عنصر [B[j
     • [prod[i+j] = prod[i+j] + A[i] * B[j
4. بازگرداندن []prod به عنوان خروجی.

برنامه ضرب دو چند جمله‌ای در ++C

برنامه ضرب دو چند جمله‌ای در جاوا

برنامه ضرب دو چند جمله‌ای در پایتون ۳

برنامه ضرب دو چند جمله‌ای در #C

برنامه ضرب دو چند جمله‌ای در PHP

خروجی

First polynomial is
5 + 0x^1 + 10x^2 + 6x^3
Second polynomial is
1 + 2x^1 + 4x^2
Product polynomial is
5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5

پیچیدگی زمانی

ضرب چند جمله ای ها بر مبنای الگوریتم تقسیم و حل

روشی که در ادامه آمده، راهکاری ساده است که چند جمله‌ای داده شده (از درجه n را) را در دو چند جمله‌ای که یکی دارای عبارات مرتبه پایین‌تر (کمتر از $$\frac{n}{2}$$) و دیگری شامل درجات بیشتر (بزرگ‌تر یا مساوی $$\frac{n}{2}$$) است، ضرب می‌کند.

فیلم آموزش مثال‌های عملی برنامه‌نویسی در پایتون + گواهینامه در فرادرس

کلیک کنید

الگوریتم انجام این کار در ادامه ارائه شده است.

1. فرض می‌شود دو چند جمله‌ای A و B داده شده‌اند. برای سادگی، فرض می‌شود که هر دو چند جمله‌ای دارای مرتبه مشابهی هستند و مرتبه آن‌ها از توان ۲، یعنی n = 2ⁱ. است
2. چند جمله‌ای A را می‌توان به صورت $$A0 + A1*x^{n/2}$$ نوشت.
3. چند جمله‌ای B را می‌توان به صورت $$B0 + B1*x^{n/2}$$ نوشت.
4. برای مثال، $$1 + 10x + 6x^2 - 4x^3 + 5x^4$$ را می‌توان به صورت $$(1 + 10x) + (6 - 4x + 5x^2)*x^2$$ نوشت.

A * B = (A0 + A1*xn/2) * (B0 + B1*xn/2)
= A0*B0 + A0*B1*xn/2 + A1*B0*xn/2 + A1*B1*xn
= A0*B0 + (A0*B1 + A1*B0)xn/2 + A1*B1*xn

رویکرد تقسیم و حل ارائه شده در بالا، نیازمند ۴ ضرب و زمان (O(n برای جمع کردن همه ۴ نتیجه است. بنابراین، پیچیدگی زمانی آن برابر با $$T(n) = 4T(\frac{n}{2}) + O(n)$$ خواهد بود. راهکار، بازگشت از مرتبه (O(n² است که این عدد برابر با پیچیدگی زمانی راهکار ساده مطرح شده در بالا است. اکنون ایده موجود برای حل این مساله آن است که تعداد ضرب‌ها به ۳ تا کاهش پیدا کند و بازگشت به صورت (T(n) = 3T(n/2) + O(n باشد.

روش کاهش تعداد ضرب‌ها

این کار نیاز به ترفند کوچکی دارد که مشابه با ضرب ماتریس‌ها با «الگوریتم استراسن» (Strassen Algorithm) است. سه ضرب زیر انجام می‌شوند.

X = (A0 + A1)*(B0 + B1) // اولین ضرب

Y = A0B0 // دومین ضرب

Z = A1B1 // سومین ضرب

عبارت ناموجود در ضرب بالا برابر است با:

A0*B0 + (A0*B1 + A1*B0)xn/2 + A1*B1*xn

که می‌توان آن را به صورت زیر نوشت.

A0B1 + A1B0 = X - Y - Z

توضیح دقیق

روش مرسوم ضرب چند جمله‌ای‌ها، از ۴ ضریب ضرب استفاده می‌کند.

(ax + b)(cx + d) = acx2 + (ad + bc)x + bd

اگرچه، رابطه زیر شایان توجه است:

باقیمانده دو مولفه، دقیقا ضریب میانی برای دو چند جمله‌ای هستند. بنابراین، ضرب را می‌توان به شیوه زیر محاسبه کرد.

بنابراین، عبارت دوم تنها سه ضرب دارد. در نتیجه، زمانی که توسط این الگوریتم گرفته می‌شود برابر با $$T(n) = 3T(\frac{n}{2}) + O(n)$$ است.

فیلم مجموعه آموزش پروژه محور برنامه‌ نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

راهکار بازگشتی بالا از درجه (O(n^Lg3 است که بهتر از  (O(n² محسوب می‌شود. یک الگوریتم دیگر از مرتبه (O(nLogn نیز وجود دارد که از تبدیل سریع فوریه برای ضرب دو چند جمله‌ای استفاده می‌کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده