Dados dos polinomios representados por dos arrays, escribe una función que multiplique dados dos polinomios.
Ejemplo:
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"
Una solución simple es considerar uno por uno cada término del primer polinomio y multiplicarlo por cada término del segundo polinomio. A continuación se muestra el algoritmo de este método simple.
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[].
La siguiente es la implementación del algoritmo anterior.
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 product 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 ";
printPoly(A, m);
cout <<endl<< "Second polynomial is ";
printPoly(B, n);
int *prod = multiply(A, B, m, n);
cout <<endl<< "Product polynomial is ";
printPoly(prod, m+n-1);
return 0;
}
Java
// 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 product 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
Python3
# 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 product 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
?>
Javascript
<script>
// Simple JavaScript 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){
var prod = [];
for (var i = 0; i < m + n - 1; i++) prod[i] = 0;
// Multiply two polynomials term by term
// Take ever term of first polynomial
for(var i = 0; i < m ; i++){
// Multiply the current term of first
// polynomial with every term of
// second polynomial.
for (var 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){
let ans= '';
for (var i = 0; i < n ; i++){
ans += poly[i];
if (i != 0)
ans +="x^ "+i;
if (i != n - 1)
ans += " + ";
}
document.write(ans)
}
// 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
let B = [1, 2, 4];
let m = (A).length;
let n = (B).length;
document.write("First polynomial is " + "<br>");
printPoly(A, m);
document.write("<br>");
document.write("Second polynomial is " + "<br>");
printPoly(B, n);
let prod = multiply(A, B, m, n);
document.write("<br>");
document.write("Product polynomial is " + "<br>");
printPoly(prod, m+n-1);
</script>
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
La complejidad temporal de la solución anterior es O(mn) . Si el tamaño de dos polinomios es el mismo, entonces la complejidad temporal es O(n 2 ).
Espacio Auxiliar: O(m + n)
¿Podemos hacerlo mejor?
Hay métodos para hacer la multiplicación más rápido que el tiempo O(n 2 ). Estos métodos se basan principalmente en divide y vencerás . El siguiente es un método simple que divide el polinomio dado (de grado n) en dos polinomios, uno que contiene términos de grado inferior (inferior a n/2) y el otro que contiene términos de grado superior (superior o igual a 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
Entonces, el enfoque anterior de divide y vencerás requiere 4 multiplicaciones y O(n) tiempo para sumar los 4 resultados. Por lo tanto, la complejidad del tiempo es T(n) = 4T(n/2) + O(n). La solución de la recurrencia es O(n 2 ) que es la misma que la solución simple anterior.
La idea es reducir el número de multiplicaciones a 3 y hacer la recurrencia como T(n) = 3T(n/2) + O(n)
¿Cómo reducir el número de multiplicaciones?
Esto requiere un pequeño truco similar a la multiplicación de arrays de Strassen. Hacemos las siguientes 3 multiplicaciones.
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
Explicación detallada
La multiplicación de polinomios convencional utiliza multiplicaciones de 4 coeficientes:
(ax + b)(cx + d) = acx2 + (ad + bc)x + bd
Sin embargo, observe la siguiente relación:
(a + b)(c + d) = ad + bc + ac + bd
El resto de los dos componentes son exactamente el coeficiente medio del producto de dos polinomios. Por lo tanto, el producto se puede calcular como:
(ax + b)(cx + d) = acx2 + ((a + b)(c + d) - ac - bd )x + bd
Por lo tanto, la última expresión tiene solo tres multiplicaciones.
Así que el tiempo que toma este algoritmo es T(n) = 3T(n/2) + O(n)
La solución de la recurrencia anterior es O(n Lg3 ) que es mejor que O(n 2 ).
Pronto discutiremos la implementación del enfoque anterior.
También hay un algoritmo O (nLogn) que usa la transformada rápida de Fourier para multiplicar dos polinomios (consulte this y this para obtener más detalles)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA