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

پیش از این، در مطلب «کد جمع کردن چند جمله ای ها — راهنمای کاربردی» به روش جمع کردن دو چند جمله‌ای و پیاده‌سازی این روش در زبان‌های برنامه‌نویسی گوناگون پرداخته شد. در این مطلب، روش و برنامه ضرب چند جمله ای ها در زبان‌های برنامه‌نویسی گوناگون ارائه شده است. در ادامه، مساله تعریف و سپس حل می‌شود. دو چند جمله‌ای که به وسیله دو آرایه نمایش داده می‌شوند، ارائه شده‌اند. هدف، نوشتن تابعی است که دو چند جمله‌ای را در یکدیگر ضرب کند. به عنوان مثال، داریم:

ورودی:

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

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

پیچیدگی زمانی راهکار بالا برابر با (O(mn است. اگر اندازه دو چند جمله‌ای برابر باشد، پیچیدگی زمانی از درجه (O(n² خواهد بود. راهکارهایی برای انجام ضرب دو چند جمله ای با سرعتی بیش از (O(n² وجود دارد. این روش‌ها معمولا بر مبنای الگوریتم «تقسیم و حل» (Divide and Conquer) هستند.

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

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

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

کلیک کنید

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

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) — به زبان ساده