División de polinomios usando lista enlazada

Dados dos polinomios P1 y P2 en forma de lista enlazada simple respectivamente, la tarea es imprimir las expresiones de cociente y resto en forma de lista enlazada simple, obtenida al dividir los polinomios P1 por P2

Nota: suponga que el polinomio se expresa como la potencia mayor de xa la potencia menor de x (es decir, 0).

Ejemplos:

Entrada: P1 = 5 -> 4 -> 2, P2 = 5 -> 5
Salida:
Cociente = 1 -> 0,2
Resto = 3

Entrada: P1 = 3 -> 5 -> 2, P2 = 2 -> 1
Salida:
Cociente = 1,5 -> 1,75
Resto = 0,25

Enfoque: siga los pasos a continuación para resolver el problema:

  • Cree dos listas enlazadas individualmente, el cociente y el resto , donde cada Node consistirá en el coeficiente de potencia de x y un puntero al siguiente Node.
  • Mientras que el grado del resto es menor que el grado del divisor , haga lo siguiente:
    • Reste la potencia del primer término del dividendo por la del divisor y almacene en potencia .
    • Divide el coeficiente del término principal del dividendo por el divisor y guárdalo en la variable coeficiente .
    • Cree un nuevo Node N a partir de los términos formados en los pasos 1 y 2 e inserte N en la lista de cocientes .
    • Multiplica N por el divisor y resta el dividendo del resultado obtenido.
  • Después de los pasos anteriores, imprima la lista del cociente y el resto .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node structure containing power and
// coefficient of variable
struct Node {
    float coeff;
    int pow;
    struct Node* next;
};
 
// Function to create new node
void create_node(float x, int y,
                 struct Node** temp)
{
    struct Node *r, *z;
    z = *temp;
 
    // If temp is NULL
    if (z == NULL) {
 
        r = (struct Node*)malloc(
            sizeof(struct Node));
 
        // Update coefficient and
        // power in the LL z
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(
            sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
 
    // Otherwise
    else {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(
            sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}
 
// Function to create a LL that stores
// the value of the quotient while
// performing polynomial division
void store_quotient(float mul_c, int diff,
                    struct Node* quo)
{
    // Till quo is non-empty
    while (quo->next != NULL) {
        quo = quo->next;
    }
 
    // Update powers and coefficient
    quo->pow = diff;
    quo->coeff = mul_c;
    quo->next = (struct Node*)malloc(
        sizeof(struct Node));
    quo = quo->next;
    quo->next = NULL;
}
 
// Function to create a new polynomial
// whenever subtraction is performed
// in polynomial division
void formNewPoly(int diff, float mul_c,
                 struct Node* poly)
{
    // Till poly is not empty
    while (poly->next != NULL) {
        poly->pow += diff;
        poly->coeff *= mul_c;
        poly = poly->next;
    }
}
 
// Function to copy one polynomial
// into another linkedlist
void copyList(struct Node* r,
              struct Node** copy)
{
    // Copy the values of r in the
    // polynomial copy
    while (r != NULL) {
 
        struct Node* z
            = (struct Node*)malloc(
                sizeof(struct Node));
 
        // Store coefficient and power
        z->coeff = r->coeff;
        z->pow = r->pow;
        z->next = NULL;
 
        struct Node* dis = *copy;
        if (dis == NULL) {
            *copy = z;
        }
        else {
            while (dis->next != NULL) {
                dis = dis->next;
            }
            dis->next = z;
        }
        r = r->next;
    }
}
 
// Function to subtract two polynomial
void polySub(struct Node* poly1,
             struct Node* poly2,
             struct Node* poly)
{
 
    // Compute until poly1 and poly2 is empty
    while (poly1->next && poly2->next) {
 
        // If power of 1st polynomial
        // > 2nd, then store 1st as
        // it is and move its pointer
        if (poly1->pow > poly2->pow) {
 
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
            poly->next
                = (struct Node*)malloc(
                    sizeof(struct Node));
            poly = poly->next;
            poly->next = NULL;
        }
 
        // If power of 2nd polynomial >
        // 1st then store 2nd as it is
        // and move its pointer
        else if (poly1->pow < poly2->pow) {
 
            poly->pow = poly2->pow;
            poly->coeff = -1 * poly2->coeff;
            poly2 = poly2->next;
            poly->next
                = (struct Node*)malloc(
                    sizeof(struct Node));
            poly = poly->next;
            poly->next = NULL;
        }
 
        // If power of both polynomial
        // is same then subtract their
        // coefficients
        else {
 
            if ((poly1->coeff
                 - poly2->coeff)
                != 0) {
 
                poly->pow = poly1->pow;
                poly->coeff = (poly1->coeff
                               - poly2->coeff);
 
                poly->next = (struct Node*)malloc(
                    sizeof(struct Node));
                poly = poly->next;
                poly->next = NULL;
            }
 
            // Update the pointers
            // poly1 and poly2
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
 
    // Add the remaining value of polynomials
    while (poly1->next || poly2->next) {
 
        // If poly1 exists
        if (poly1->next) {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
        }
 
        // If poly2 exists
        if (poly2->next) {
            poly->pow = poly2->pow;
            poly->coeff = -1 * poly2->coeff;
            poly2 = poly2->next;
        }
 
        // Add the new node to poly
        poly->next
            = (struct Node*)malloc(
                sizeof(struct Node));
        poly = poly->next;
        poly->next = NULL;
    }
}
 
// Function to display linked list
void show(struct Node* node)
{
    int count = 0;
    while (node->next != NULL
           && node->coeff != 0) {
 
        // If count is non-zero, then
        // print the positive value
        if (count == 0)
            cout << node->coeff;
 
        // Otherwise
        else
            cout << abs(node->coeff);
        count++;
 
        // Print polynomial power
        if (node->pow != 0)
            cout << "x^" << node->pow;
        node = node->next;
 
        if (node->next != NULL)
 
            // If coeff of next term
            // > 0 then next sign will
            // be positive else negative
            if (node->coeff > 0)
                cout << " + ";
            else
                cout << " - ";
    }
 
    cout << "\n";
}
 
// Function to divide two polynomials
void divide_poly(struct Node* poly1,
                 struct Node* poly2)
{
    // Initialize Remainder and Quotient
    struct Node *rem = NULL, *quo = NULL;
 
    quo = (struct Node*)malloc(
        sizeof(struct Node));
    quo->next = NULL;
 
    struct Node *q = NULL, *r = NULL;
 
    // Copy poly1, i.e., dividend to q
    copyList(poly1, &q);
 
    // Copy poly, i.e., divisor to r
    copyList(poly2, &r);
 
    // Perform polynomial subtraction till
    // highest power of q > highest power of divisor
    while (q != NULL
           && (q->pow >= poly2->pow)) {
 
        // difference of power
        int diff = q->pow - poly2->pow;
 
        float mul_c = (q->coeff
                       / poly2->coeff);
 
        // Stores the quotient node
        store_quotient(mul_c, diff,
                       quo);
 
        struct Node* q2 = NULL;
 
        // Copy one LL in another LL
        copyList(r, &q2);
 
        // formNewPoly forms next value
        // of q after performing the
        // polynomial subtraction
        formNewPoly(diff, mul_c, q2);
 
        struct Node* store = NULL;
        store = (struct Node*)malloc(
            sizeof(struct Node));
 
        // Perform polynomial subtraction
        polySub(q, q2, store);
 
        // Now change value of q to the
        // subtracted value i.e., store
        q = store;
        free(q2);
    }
 
    // Print the quotient
    cout << "Quotient: ";
    show(quo);
 
    // Print the remainder
    cout << "Remainder: ";
    rem = q;
    show(rem);
}
 
// Driver Code
int main()
{
    struct Node* poly1 = NULL;
    struct Node *poly2 = NULL, *poly = NULL;
 
    // Create 1st Polynomial (Dividend):
    // 5x^2 + 4x^1 + 2
    create_node(5.0, 2, &poly1);
    create_node(4.0, 1, &poly1);
    create_node(2.0, 0, &poly1);
 
    // Create 2nd Polynomial (Divisor):
    // 5x^1 + 5
    create_node(5.0, 1, &poly2);
    create_node(5.0, 0, &poly2);
 
    // Function Call
    divide_poly(poly1, poly2);
 
    return 0;
}
Producción: 

Quotient: 1x^1 - 0.2
Remainder: 3

 

Complejidad temporal: O(M + N)
Espacio auxiliar: O(M + N)

Publicación traducida automáticamente

Artículo escrito por prakhar_kochar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *