Dados dos polinomios en forma de lista enlazada. La tarea es encontrar la multiplicación de ambos polinomios.
Ejemplos:
Input: Poly1: 3x^2 + 5x^1 + 6, Poly2: 6x^1 + 8 Output: 18x^3 + 54x^2 + 76x^1 + 48 On multiplying each element of 1st polynomial with elements of 2nd polynomial, we get 18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48 On adding values with same power of x, 18x^3 + 54x^2 + 76x^1 + 48 Input: Poly1: 3x^3 + 6x^1 - 9, Poly2: 9x^3 - 8x^2 + 7x^1 + 2 Output: 27x^6 - 24x^5 + 75x^4 - 123x^3 + 114x^2 - 51x^1 - 18
Acercarse:
- En este enfoque, multiplicaremos el segundo polinomio con cada término del primer polinomio.
- Almacene el valor multiplicado en una nueva lista enlazada.
- Luego sumaremos los coeficientes de los elementos que tienen la misma potencia en el polinomio resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Node structure containing powerer
// and coefficient of variable
struct Node {
int coeff, power;
Node* next;
};
// Function add a new node at the end of list
Node* addnode(Node* start, int coeff, int power)
{
// Create a new node
Node* newnode = new Node;
newnode->coeff = coeff;
newnode->power = power;
newnode->next = NULL;
// If linked list is empty
if (start == NULL)
return newnode;
// If linked list has nodes
Node* ptr = start;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = newnode;
return start;
}
// Function To Display The Linked list
void printList(struct Node* ptr)
{
while (ptr->next != NULL) {
cout << ptr->coeff << "x^" << ptr->power ;
if( ptr->next!=NULL && ptr->next->coeff >=0)
cout << "+";
ptr = ptr->next;
}
cout << ptr->coeff << "\n";
}
// Function to add coefficients of
// two elements having same powerer
void removeDuplicates(Node* start)
{
Node *ptr1, *ptr2, *dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
// Compare the picked element
// with rest of the elements
while (ptr2->next != NULL) {
// If powerer of two elements are same
if (ptr1->power == ptr2->next->power) {
// Add their coefficients and put it in 1st element
ptr1->coeff = ptr1->coeff + ptr2->next->coeff;
dup = ptr2->next;
ptr2->next = ptr2->next->next;
// remove the 2nd element
delete (dup);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
// Function two Multiply two polynomial Numbers
Node* multiply(Node* poly1, Node* poly2,
Node* poly3)
{
// Create two pointer and store the
// address of 1st and 2nd polynomials
Node *ptr1, *ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != NULL) {
while (ptr2 != NULL) {
int coeff, power;
// Multiply the coefficient of both
// polynomials and store it in coeff
coeff = ptr1->coeff * ptr2->coeff;
// Add the powerer of both polynomials
// and store it in power
power = ptr1->power + ptr2->power;
// Invoke addnode function to create
// a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
// move the pointer of 2nd polynomial
// two get its next term
ptr2 = ptr2->next;
}
// Move the 2nd pointer to the
// starting point of 2nd polynomial
ptr2 = poly2;
// move the pointer of 1st polynomial
ptr1 = ptr1->next;
}
// this function will be invoke to add
// the coefficient of the elements
// having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
}
// Driver Code
int main()
{
Node *poly1 = NULL, *poly2 = NULL, *poly3 = NULL;
// Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 3);
poly1 = addnode(poly1, 6, 1);
poly1 = addnode(poly1, -9, 0);
// Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 9, 3);
poly2 = addnode(poly2, -8, 2);
poly2 = addnode(poly2, 7, 1);
poly2 = addnode(poly2, 2, 0);
// Displaying 1st polynomial
cout << "1st Polynomial:- ";
printList(poly1);
// Displaying 2nd polynomial
cout << "2nd Polynomial:- ";
printList(poly2);
// calling multiply function
poly3 = multiply(poly1, poly2, poly3);
// Displaying Resultant Polynomial
cout << "Resultant Polynomial:- ";
printList(poly3);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
// Node structure containing powerer
// and coefficient of variable
static class Node {
int coeff, power;
Node next;
};
// Function add a new node at the end of list
static Node addnode(Node start, int coeff, int power)
{
// Create a new node
Node newnode = new Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = null;
// If linked list is empty
if (start == null)
return newnode;
// If linked list has nodes
Node ptr = start;
while (ptr.next != null)
ptr = ptr.next;
ptr.next = newnode;
return start;
}
// Function To Display The Linked list
static void printList( Node ptr)
{
while (ptr.next != null) {
System.out.print( ptr.coeff + "x^" + ptr.power + " + ");
ptr = ptr.next;
}
System.out.print( ptr.coeff +"\n");
}
// Function to add coefficients of
// two elements having same powerer
static void removeDuplicates(Node start)
{
Node ptr1, ptr2, dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
// Compare the picked element
// with rest of the elements
while (ptr2.next != null) {
// If powerer of two elements are same
if (ptr1.power == ptr2.next.power) {
// Add their coefficients and put it in 1st element
ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;
}
else
ptr2 = ptr2.next;
}
ptr1 = ptr1.next;
}
}
// Function two Multiply two polynomial Numbers
static Node multiply(Node poly1, Node poly2,
Node poly3)
{
// Create two pointer and store the
// address of 1st and 2nd polynomials
Node ptr1, ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != null) {
while (ptr2 != null) {
int coeff, power;
// Multiply the coefficient of both
// polynomials and store it in coeff
coeff = ptr1.coeff * ptr2.coeff;
// Add the powerer of both polynomials
// and store it in power
power = ptr1.power + ptr2.power;
// Invoke addnode function to create
// a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
// move the pointer of 2nd polynomial
// two get its next term
ptr2 = ptr2.next;
}
// Move the 2nd pointer to the
// starting point of 2nd polynomial
ptr2 = poly2;
// move the pointer of 1st polynomial
ptr1 = ptr1.next;
}
// this function will be invoke to add
// the coefficient of the elements
// having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
}
// Driver Code
public static void main(String args[])
{
Node poly1 = null, poly2 = null, poly3 = null;
// Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 2);
poly1 = addnode(poly1, 5, 1);
poly1 = addnode(poly1, 6, 0);
// Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 6, 1);
poly2 = addnode(poly2, 8, 0);
// Displaying 1st polynomial
System.out.print("1st Polynomial:- ");
printList(poly1);
// Displaying 2nd polynomial
System.out.print("2nd Polynomial:- ");
printList(poly2);
// calling multiply function
poly3 = multiply(poly1, poly2, poly3);
// Displaying Resultant Polynomial
System.out.print( "Resultant Polynomial:- ");
printList(poly3);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the above approach
# Node structure containing powerer
# and coefficient of variable
class Node:
def __init__(self):
self.coeff = None
self.power = None
self.next = None
# Function add a new node at the end of list
def addnode(start, coeff, power):
# Create a new node
newnode = Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = None;
# If linked list is empty
if (start == None):
return newnode;
# If linked list has nodes
ptr = start;
while (ptr.next != None):
ptr = ptr.next;
ptr.next = newnode;
return start;
# Function To Display The Linked list
def printList(ptr):
while (ptr.next != None):
print(str(ptr.coeff) + 'x^' + str(ptr.power), end = '')
if( ptr.next != None and ptr.next.coeff >= 0):
print('+', end = '')
ptr = ptr.next
print(ptr.coeff)
# Function to add coefficients of
# two elements having same powerer
def removeDuplicates(start):
ptr2 = None
dup = None
ptr1 = start;
# Pick elements one by one
while (ptr1 != None and ptr1.next != None):
ptr2 = ptr1;
# Compare the picked element
# with rest of the elements
while (ptr2.next != None):
# If powerer of two elements are same
if (ptr1.power == ptr2.next.power):
# Add their coefficients and put it in 1st element
ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;
else:
ptr2 = ptr2.next;
ptr1 = ptr1.next;
# Function two Multiply two polynomial Numbers
def multiply(poly1, Npoly2, poly3):
# Create two pointer and store the
# address of 1st and 2nd polynomials
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != None):
while (ptr2 != None):
# Multiply the coefficient of both
# polynomials and store it in coeff
coeff = ptr1.coeff * ptr2.coeff;
# Add the powerer of both polynomials
# and store it in power
power = ptr1.power + ptr2.power;
# Invoke addnode function to create
# a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
# move the pointer of 2nd polynomial
# two get its next term
ptr2 = ptr2.next;
# Move the 2nd pointer to the
# starting point of 2nd polynomial
ptr2 = poly2;
# move the pointer of 1st polynomial
ptr1 = ptr1.next;
# this function will be invoke to add
# the coefficient of the elements
# having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
# Driver Code
if __name__=='__main__':
poly1 = None
poly2 = None
poly3 = None;
# Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 3);
poly1 = addnode(poly1, 6, 1);
poly1 = addnode(poly1, -9, 0);
# Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 9, 3);
poly2 = addnode(poly2, -8, 2);
poly2 = addnode(poly2, 7, 1);
poly2 = addnode(poly2, 2, 0);
# Displaying 1st polynomial
print("1st Polynomial:- ", end = '');
printList(poly1);
# Displaying 2nd polynomial
print("2nd Polynomial:- ", end = '');
printList(poly2);
# calling multiply function
poly3 = multiply(poly1, poly2, poly3);
# Displaying Resultant Polynomial
print("Resultant Polynomial:- ", end = '');
printList(poly3);
# This code is contributed by rutvik_56
C#
// C# implementation of above approach
using System;
class GFG
{
// Node structure containing powerer
// and coefficient of variable
public class Node
{
public int coeff, power;
public Node next;
};
// Function add a new node at the end of list
static Node addnode(Node start, int coeff, int power)
{
// Create a new node
Node newnode = new Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = null;
// If linked list is empty
if (start == null)
return newnode;
// If linked list has nodes
Node ptr = start;
while (ptr.next != null)
ptr = ptr.next;
ptr.next = newnode;
return start;
}
// Function To Display The Linked list
static void printList( Node ptr)
{
while (ptr.next != null)
{
Console.Write( ptr.coeff + "x^" + ptr.power + " + ");
ptr = ptr.next;
}
Console.Write( ptr.coeff +"\n");
}
// Function to add coefficients of
// two elements having same powerer
static void removeDuplicates(Node start)
{
Node ptr1, ptr2, dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null)
{
ptr2 = ptr1;
// Compare the picked element
// with rest of the elements
while (ptr2.next != null)
{
// If powerer of two elements are same
if (ptr1.power == ptr2.next.power)
{
// Add their coefficients and put it in 1st element
ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;
}
else
ptr2 = ptr2.next;
}
ptr1 = ptr1.next;
}
}
// Function two Multiply two polynomial Numbers
static Node multiply(Node poly1, Node poly2,
Node poly3)
{
// Create two pointer and store the
// address of 1st and 2nd polynomials
Node ptr1, ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != null)
{
while (ptr2 != null)
{
int coeff, power;
// Multiply the coefficient of both
// polynomials and store it in coeff
coeff = ptr1.coeff * ptr2.coeff;
// Add the powerer of both polynomials
// and store it in power
power = ptr1.power + ptr2.power;
// Invoke addnode function to create
// a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
// move the pointer of 2nd polynomial
// two get its next term
ptr2 = ptr2.next;
}
// Move the 2nd pointer to the
// starting point of 2nd polynomial
ptr2 = poly2;
// move the pointer of 1st polynomial
ptr1 = ptr1.next;
}
// this function will be invoke to add
// the coefficient of the elements
// having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
}
// Driver Code
public static void Main(String []args)
{
Node poly1 = null, poly2 = null, poly3 = null;
// Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 2);
poly1 = addnode(poly1, 5, 1);
poly1 = addnode(poly1, 6, 0);
// Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 6, 1);
poly2 = addnode(poly2, 8, 0);
// Displaying 1st polynomial
Console.Write("1st Polynomial:- ");
printList(poly1);
// Displaying 2nd polynomial
Console.Write("2nd Polynomial:- ");
printList(poly2);
// calling multiply function
poly3 = multiply(poly1, poly2, poly3);
// Displaying Resultant Polynomial
Console.Write( "Resultant Polynomial:- ");
printList(poly3);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of above approach
// Link list node
class Node {
constructor() {
this.coeff = 0;
this.power = 0;
this.next = null;
}
}
// Function add a new node at the end of list
function addnode(start, coeff, power)
{
// Create a new node
var newnode = new Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = null;
// If linked list is empty
if (start == null)
return newnode;
// If linked list has nodes
var ptr = start;
while (ptr.next != null)
ptr = ptr.next;
ptr.next = newnode;
return start;
}
// Function To Display The Linked list
function printList( ptr)
{
while (ptr.next != null) {
document.write( ptr.coeff + "x^" + ptr.power + " + ");
ptr = ptr.next;
}
document.write( ptr.coeff +"</br>");
}
// Function to add coefficients of
// two elements having same powerer
function removeDuplicates( start)
{
var ptr1, ptr2, dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
// Compare the picked element
// with rest of the elements
while (ptr2.next != null) {
// If powerer of two elements are same
if (ptr1.power == ptr2.next.power) {
// Add their coefficients and put it in 1st element
ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;
}
else
ptr2 = ptr2.next;
}
ptr1 = ptr1.next;
}
}
// Function two Multiply two polynomial Numbers
function multiply( poly1, poly2,
poly3)
{
// Create two pointer and store the
// address of 1st and 2nd polynomials
var ptr1, ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != null) {
while (ptr2 != null) {
let coeff, power;
// Multiply the coefficient of both
// polynomials and store it in coeff
coeff = ptr1.coeff * ptr2.coeff;
// Add the powerer of both polynomials
// and store it in power
power = ptr1.power + ptr2.power;
// Invoke addnode function to create
// a newnode by passing three parameters
poly3 = addnode(poly3, coeff, power);
// move the pointer of 2nd polynomial
// two get its next term
ptr2 = ptr2.next;
}
// Move the 2nd pointer to the
// starting point of 2nd polynomial
ptr2 = poly2;
// move the pointer of 1st polynomial
ptr1 = ptr1.next;
}
// this function will be invoke to add
// the coefficient of the elements
// having same powerer from the resultant linked list
removeDuplicates(poly3);
return poly3;
}
// Driver Code
var poly1 = null, poly2 = null, poly3 = null;
// Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
poly1 = addnode(poly1, 3, 2);
poly1 = addnode(poly1, 5, 1);
poly1 = addnode(poly1, 6, 0);
// Creation of 2nd polynomial: 6x^1 + 8
poly2 = addnode(poly2, 6, 1);
poly2 = addnode(poly2, 8, 0);
// Displaying 1st polynomial
document.write("1st Polynomial:- ");
printList(poly1);
// Displaying 2nd polynomial
document.write("2nd Polynomial:- ");
printList(poly2);
// calling multiply function
poly3 = multiply(poly1, poly2, poly3);
// Displaying Resultant Polynomial
document.write( "Resultant Polynomial:- ");
printList(poly3);
// This code is contributed by jana_sayantan.
</script>
Producción
1st Polynomial:- 3x^3+6x^1-9 2nd Polynomial:- 9x^3-8x^2+7x^1+2 Resultant Polynomial:- 27x^6-24x^5+75x^4-123x^3+114x^2-51x^1-18
Publicación traducida automáticamente
Artículo escrito por Deepak_Jaiswal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA