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

ورودی:

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

// Simple C++ program to multiply two polynomials 
#include <iostream> 
using namespace std; 
  
// A[] represents coefficients of first polynomial 
// B[] represents coefficients of second polynomial 
// m and n are sizes of A[] and B[] respectively 
int *multiply(int A[], int B[], int m, int n) 
{ 
   int *prod = new int[m+n-1]; 
  
   // Initialize the porduct polynomial 
   for (int i = 0; i<m+n-1; i++) 
     prod[i] = 0; 
  
   // Multiply two polynomials term by term 
  
   // Take ever term of first polynomial 
   for (int i=0; i<m; i++) 
   { 
     // Multiply the current term of first polynomial 
     // with every term of second polynomial. 
     for (int j=0; j<n; j++) 
         prod[i+j] += A[i]*B[j]; 
   } 
  
   return prod; 
} 
  
// A utility function to print a polynomial 
void printPoly(int poly[], int n) 
{ 
    for (int i=0; i<n; i++) 
    { 
       cout << poly[i]; 
       if (i != 0) 
        cout << "x^" << i ; 
       if (i != n-1) 
       cout << " + "; 
    } 
} 
  
// Driver program to test above functions 
int main() 
{ 
    // The following array represents polynomial 5 + 10x^2 + 6x^3 
    int A[] = {5, 0, 10, 6}; 
  
    // The following array represents polynomial 1 + 2x + 4x^2 
    int B[] = {1, 2, 4}; 
    int m = sizeof(A)/sizeof(A[0]); 
    int n = sizeof(B)/sizeof(B[0]); 
  
    cout << "First polynomial is n"; 
    printPoly(A, m); 
    cout << "nSecond polynomial is n"; 
    printPoly(B, n); 
  
    int *prod = multiply(A, B, m, n); 
  
    cout << "nProduct polynomial is n"; 
    printPoly(prod, m+n-1); 
  
    return 0; 
}

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

// Java program to multiply two polynomials 
class GFG 
{ 
  
    // A[] represents coefficients  
    // of first polynomial 
    // B[] represents coefficients  
    // of second polynomial 
    // m and n are sizes of A[] and B[] respectively 
    static int[] multiply(int A[], int B[],  
                            int m, int n)  
    { 
        int[] prod = new int[m + n - 1]; 
  
        // Initialize the porduct polynomial 
        for (int i = 0; i < m + n - 1; i++)  
        { 
            prod[i] = 0; 
        } 
  
        // Multiply two polynomials term by term 
        // Take ever term of first polynomial 
        for (int i = 0; i < m; i++)  
        { 
            // Multiply the current term of first polynomial 
            // with every term of second polynomial. 
            for (int j = 0; j < n; j++)  
            { 
                prod[i + j] += A[i] * B[j]; 
            } 
        } 
  
        return prod; 
    } 
  
    // A utility function to print a polynomial 
    static void printPoly(int poly[], int n)  
    { 
        for (int i = 0; i < n; i++)  
        { 
            System.out.print(poly[i]); 
            if (i != 0)  
            { 
                System.out.print("x^" + i); 
            } 
            if (i != n - 1)  
            { 
                System.out.print(" + "); 
            } 
        } 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        // The following array represents  
        // polynomial 5 + 10x^2 + 6x^3 
        int A[] = {5, 0, 10, 6}; 
  
        // The following array represents  
        // polynomial 1 + 2x + 4x^2 
        int B[] = {1, 2, 4}; 
        int m = A.length; 
        int n = B.length; 
  
        System.out.println("First polynomial is n"); 
        printPoly(A, m); 
        System.out.println("nSecond polynomial is n"); 
        printPoly(B, n); 
  
        int[] prod = multiply(A, B, m, n); 
  
        System.out.println("nProduct polynomial is n"); 
        printPoly(prod, m + n - 1); 
    } 
} 
  
// This code contributed by Rajput-Ji

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

# Simple Python3 program to multiply two polynomials 
  
# A[] represents coefficients of first polynomial 
# B[] represents coefficients of second polynomial 
# m and n are sizes of A[] and B[] respectively 
def multiply(A, B, m, n): 
  
    prod = [0] * (m + n - 1); 
      
    # Multiply two polynomials term by term 
      
    # Take ever term of first polynomial 
    for i in range(m): 
          
        # Multiply the current term of first  
        # polynomial with every term of  
        # second polynomial. 
        for j in range(n): 
            prod[i + j] += A[i] * B[j]; 
  
    return prod; 
  
# A utility function to print a polynomial 
def printPoly(poly, n): 
  
    for i in range(n): 
        print(poly[i], end = ""); 
        if (i != 0): 
            print("x^", i, end = ""); 
        if (i != n - 1): 
            print(" + ", end = ""); 
  
# Driver Code 
  
# The following array represents 
# polynomial 5 + 10x^2 + 6x^3 
A = [5, 0, 10, 6]; 
  
# The following array represents  
# polynomial 1 + 2x + 4x^2 
B = [1, 2, 4]; 
m = len(A); 
n = len(B); 
  
print("First polynomial is "); 
printPoly(A, m); 
print("\nSecond polynomial is "); 
printPoly(B, n); 
  
prod = multiply(A, B, m, n); 
  
print("\nProduct polynomial is "); 
printPoly(prod, m+n-1); 
  
# This code is contributed by chandan_jnu

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

// C# program to multiply two polynomials 
using System; 
  
class GFG  
{ 
  
    // A[] represents coefficients  
    // of first polynomial 
    // B[] represents coefficients  
    // of second polynomial 
    // m and n are sizes of A[]  
    // and B[] respectively 
    static int[] multiply(int []A, int []B,  
                            int m, int n)  
    { 
        int[] prod = new int[m + n - 1]; 
  
        // Initialize the porduct polynomial 
        for (int i = 0; i < m + n - 1; i++)  
        { 
            prod[i] = 0; 
        } 
  
        // Multiply two polynomials term by term 
        // Take ever term of first polynomial 
        for (int i = 0; i < m; i++) 
        { 
            // Multiply the current term of first polynomial 
            // with every term of second polynomial. 
            for (int j = 0; j < n; j++)  
            { 
                prod[i + j] += A[i] * B[j]; 
            } 
        } 
  
        return prod; 
    } 
  
    // A utility function to print a polynomial 
    static void printPoly(int []poly, int n) 
    { 
        for (int i = 0; i < n; i++) { 
            Console.Write(poly[i]); 
            if (i != 0) { 
                Console.Write("x^" + i); 
            } 
            if (i != n - 1) { 
                Console.Write(" + "); 
            } 
        } 
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
          
        // The following array represents  
        // polynomial 5 + 10x^2 + 6x^3 
        int []A = {5, 0, 10, 6}; 
  
        // The following array represents 
        // polynomial 1 + 2x + 4x^2 
        int []B = {1, 2, 4}; 
        int m = A.Length; 
        int n = B.Length; 
  
        Console.WriteLine("First polynomial is n"); 
        printPoly(A, m); 
        Console.WriteLine("nSecond polynomial is n"); 
        printPoly(B, n); 
  
        int[] prod = multiply(A, B, m, n); 
  
        Console.WriteLine("nProduct polynomial is n"); 
        printPoly(prod, m + n - 1); 
    } 
} 
  
// This code has been contributed by 29AjayKumar  

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

<?php 
// Simple PHP program to multiply two polynomials 
  
// A[] represents coefficients of first polynomial 
// B[] represents coefficients of second polynomial 
// m and n are sizes of A[] and B[] respectively 
function multiply($A, $B, $m, $n) 
{ 
    $prod = array_fill(0, $m + $n - 1, 0); 
      
    // Multiply two polynomials term by term 
      
    // Take ever term of first polynomial 
    for ($i = 0; $i < $m; $i++) 
    { 
        // Multiply the current term of first  
        // polynomial with every term of  
        // second polynomial. 
        for ($j = 0; $j < $n; $j++) 
            $prod[$i + $j] += $A[$i] * $B[$j]; 
    } 
  
    return $prod; 
} 
  
// A utility function to print a polynomial 
function printPoly($poly, $n) 
{ 
    for ($i = 0; $i < $n; $i++) 
    { 
        echo $poly[$i]; 
        if ($i != 0) 
            echo "x^" . $i; 
        if ($i != $n - 1) 
        echo " + "; 
    } 
} 
  
// Driver Code 
  
// The following array represents 
// polynomial 5 + 10x^2 + 6x^3 
$A = array(5, 0, 10, 6); 
  
// The following array represents  
// polynomial 1 + 2x + 4x^2 
$B = array(1, 2, 4); 
$m = count($A); 
$n = count($B); 
  
echo "First polynomial is \n"; 
printPoly($A, $m); 
echo "\nSecond polynomial is \n"; 
printPoly($B, $n); 
  
$prod = multiply($A, $B, $m, $n); 
  
echo "\nProduct polynomial is \n"; 
printPoly($prod, $m+$n-1); 
  
// This code is contributed by chandan_jnu 
?>

خروجی

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(n2 خواهد بود. راهکارهایی برای انجام ضرب دو چند جمله ای با سرعتی بیش از (O(n2 وجود دارد. این روش‌ها معمولا بر مبنای الگوریتم «تقسیم و حل» (Divide and Conquer) هستند.

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

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

  1. فرض می‌شود دو چند جمله‌ای A و B داده شده‌اند. برای سادگی، فرض می‌شود که هر دو چند جمله‌ای دارای مرتبه مشابهی هستند و مرتبه آن‌ها از توان ۲، یعنی n = 2i. است
  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(n2 است که این عدد برابر با پیچیدگی زمانی راهکار ساده مطرح شده در بالا است. اکنون ایده موجود برای حل این مساله آن است که تعداد ضرب‌ها به ۳ تا کاهش پیدا کند و بازگشت به صورت (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

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

(a + b)(c + d) = ad + bc + ac + bd

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

(ax + b)(cx + d) = acx2 + 
((a + b)(c + d) , ac , bd )x + bd

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

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

اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

بر اساس رای 8 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *