Рубрики

Умножим два полинома

Если даны два полинома, представленные двумя массивами, напишите функцию, которая умножает данные на два полинома.

Пример:

Input:  A[] = {5, 0, 10, 6} 
        B[] = {1, 2, 4} 
Output: prod[] = {5, 10, 30, 26, 52, 24}

The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"
The second array represents "1 + 2x^1 + 4x^2" 
And Output is "5 + 10x^1 + 30x^2 + 26x^3 + 52x^4 + 24x^5"

Простое решение состоит в том, чтобы один за другим рассматривать каждый член первого многочлена и умножать его на каждый член второго многочлена. Ниже приведен алгоритм этого простого метода.

multiply(A[0..m-1], B[0..n01])
1) Create a product array prod[] of size m+n-1.
2) Initialize all entries in prod[] as 0.
3) Traverse array A[] and do following for every element A[i]
...(3.a) Traverse array B[] and do following for every element B[j]
          prod[i+j] = prod[i+j] + A[i] * B[j]
4) Return prod[].

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Простая программа на C ++ для умножения двух полиномов
#include <iostream>

using namespace std;

  
// A [] представляет коэффициенты первого полинома
// B [] представляет коэффициенты второго полинома
// m и n - размеры A [] и B [] соответственно

int *multiply(int A[], int B[], int m, int n)

{

   int *prod = new int[m+n-1];

  

   // Инициализация полинома пордукта

   for (int i = 0; i<m+n-1; i++)

     prod[i] = 0;

  

   // Умножаем два полинома на срок

  

   // Взять когда-либо член первого полинома

   for (int i=0; i<m; i++)

   {

     // Умножаем текущий член первого полинома

     // с каждым членом второго многочлена.

     for (int j=0; j<n; j++)

         prod[i+j] += A[i]*B[j];

   }

  

   return prod;

}

  
// Полезная функция для печати полинома

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 << " + ";

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Следующий массив представляет полином 5 + 10x ^ 2 + 6x ^ 3

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

  

    // Следующий массив представляет полином 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-программа для умножения двух полиномов

class GFG

{

  

    // A [] представляет коэффициенты

    // первого полинома

    // B [] представляет коэффициенты

    // второго полинома

    // m и n - размеры A [] и B [] соответственно

    static int[] multiply(int A[], int B[], 

                            int m, int n) 

    {

        int[] prod = new int[m + n - 1];

  

        // Инициализация полинома пордукта

        for (int i = 0; i < m + n - 1; i++) 

        {

            prod[i] = 0;

        }

  

        // Умножаем два полинома на срок

        // Взять когда-либо член первого полинома

        for (int i = 0; i < m; i++) 

        {

            // Умножаем текущий член первого полинома

            // с каждым членом второго многочлена.

            for (int j = 0; j < n; j++) 

            {

                prod[i + j] += A[i] * B[j];

            }

        }

  

        return prod;

    }

  

    // Полезная функция для печати полинома

    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(" + ");

            }

        }

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        // Следующий массив представляет

        // полином 5 + 10x ^ 2 + 6x ^ 3

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

  

        // Следующий массив представляет

        // полином 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);

    }

}

  
// Этот код предоставлен Rajput-Ji

python3

# Простая программа на Python3 для умножения двух полиномов

  
# A [] представляет коэффициенты первого полинома
# B [] представляет коэффициенты второго полинома
# m и n - размеры A [] и B [] соответственно

def multiply(A, B, m, n):

  

    prod = [0] * (m + n - 1);

      

    # Умножим два многочлена на член

      

    # Возьмите когда-либо член первого полинома

    for i in range(m):

          

        # Умножьте текущий срок первого

        # полином с каждым членом

        # второй полином.

        for j in range(n):

            prod[i + j] += A[i] * B[j];

  

    return prod;

  
# Полезная функция для печати полинома

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 = "");

  
Код водителя

  
# Следующий массив представляет
# полином 5 + 10x ^ 2 + 6x ^ 3

A = [5, 0, 10, 6];

  
# Следующий массив представляет
# полином 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);

  
# Этот код предоставлен chandan_jnu

C #

// C # программа для умножения двух полиномов

using System;

  

class GFG 

{

  

    // A [] представляет коэффициенты

    // первого полинома

    // B [] представляет коэффициенты

    // второго полинома

    // m и n - размеры A []

    // и B [] соответственно

    static int[] multiply(int []A, int []B, 

                            int m, int n) 

    {

        int[] prod = new int[m + n - 1];

  

        // Инициализация полинома пордукта

        for (int i = 0; i < m + n - 1; i++) 

        {

            prod[i] = 0;

        }

  

        // Умножаем два полинома на срок

        // Взять когда-либо член первого полинома

        for (int i = 0; i < m; i++)

        {

            // Умножаем текущий член первого полинома

            // с каждым членом второго многочлена.

            for (int j = 0; j < n; j++) 

            {

                prod[i + j] += A[i] * B[j];

            }

        }

  

        return prod;

    }

  

    // Полезная функция для печати полинома

    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(" + ");

            }

        }

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

          

        // Следующий массив представляет

        // полином 5 + 10x ^ 2 + 6x ^ 3

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

  

        // Следующий массив представляет

        // полином 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);

    }

}

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// Простая PHP-программа для умножения двух полиномов

  
// A [] представляет коэффициенты первого полинома
// B [] представляет коэффициенты второго полинома
// m и n - размеры A [] и B [] соответственно

function multiply($A, $B, $m, $n)

{

    $prod = array_fill(0, $m + $n - 1, 0);

      

    // Умножаем два полинома на срок

      

    // Взять когда-либо член первого полинома

    for ($i = 0; $i < $m; $i++)

    {

        // Умножаем текущий член на первый

        // полином с каждым членом

        // второй полином.

        for ($j = 0; $j < $n; $j++)

            $prod[$i + $j] += $A[$i] * $B[$j];

    }

  

    return $prod;

}

  
// Полезная функция для печати полинома

function printPoly($poly, $n)

{

    for ($i = 0; $i < $n; $i++)

    {

        echo $poly[$i];

        if ($i != 0)

            echo "x^" . $i;

        if ($i != $n - 1)

        echo " + ";

    }

}

  
// Код драйвера

  
// Следующий массив представляет
// полином 5 + 10x ^ 2 + 6x ^ 3

$A = array(5, 0, 10, 6);

  
// Следующий массив представляет
// полином 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);

  
// Этот код предоставлен 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 (n 2 ).

Можем ли мы сделать лучше?
Существуют методы, позволяющие выполнять умножение быстрее, чем за время O (n 2 ). Эти методы в основном основаны на разделяй и властвуй . Ниже приведен один простой метод, который делит данный многочлен (степени n) на два многочлена, один из которых содержит члены более низкой степени (меньше n / 2), а другой — содержит тройки более высокой степени (больше или равен n / 2).

Let the two given polynomials be A and B.  
For simplicity, Let us assume that the given two polynomials are of
same degree and have degree in powers of 2, i.e., n = 2i

The polynomial 'A' can be written as A0 + A1*xn/2
The polynomial 'B' can be written as B0 + B1*xn/2

For example 1 + 10x + 6x2 - 4x3 + 5x4 can be
written as (1 + 10x) + (6 - 4x + 5x2)*x2

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

Таким образом, описанный выше подход «разделяй и властвуй» требует 4 умножения и O (n) времени, чтобы сложить все 4 результата. Следовательно, временная сложность T (n) = 4T (n / 2) + O (n). Решением рекуррентности является O (n 2 ), которое совпадает с приведенным выше простым решением.

Идея состоит в том, чтобы уменьшить количество умножений до 3 и сделать повторение как T (n) = 3T (n / 2) + O (n)

Как уменьшить количество умножений?
Это требует небольшого трюка, похожего на умножение матриц Штрассена. Мы делаем следующие 3 умножения.

X = (A0 + A1)*(B0 + B1) // First Multiplication
Y = A0B0  // Second 
Z = A1B1  // Third

The missing middle term in above multiplication equation A0*B0 + (A0*B1 + 
A1*B0)xn/2 + A1*B1*xn can obtained using below.
A0B1 + A1B0 = X - Y - Z  

В глубине объяснения
Обычное полиномиальное умножение использует 4 умножения коэффициента:

(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 (n / 2) + O (n)
Решением вышеупомянутого рецидива является O (n Lg3 ), которое лучше, чем O (n 2 ).

Мы скоро будем обсуждать реализацию вышеуказанного подхода.

Существует также алгоритм O (nLogn), который использует быстрое преобразование Фурье для умножения двух полиномов (подробности см. В этом и в этом )

Источники:
http://www.cse.ust.hk/~dekai/271/notes/L03/L03.pdf

Эта статья предоставлена Harsh. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Умножим два полинома

0.00 (0%) 0 votes