Dados dos polinomios representados por una lista enlazada. Escribe una función para realizar su suma algebraica.
Ejemplos:
Entrada:
1er número = 5x^2 + 4x^1 + 2x^0
2do número = 5x^1 + 5x^0
Salida: 5x^2 + 9x^1 + 7x^0
Enfoque: la implementación utiliza la estructura de datos del mapa para que todos los coeficientes del mismo valor de potencia se sumen y se mantengan en pares clave-valor dentro de un mapa.
A continuación se muestra la implementación del enfoque anterior:
// C++ program for addition of two polynomials // represented as linked lists #include <bits/stdc++.h> using namespace std; // Structure of Node used struct Node { // Coefficient of the polynomial int coeff; // Power of the polynomial int pow; Node* next; }; // Function to create new node void create_node(int x, int y, struct Node** temp) { struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node*) malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*) malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node*) malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } // Display Linked list void show(struct Node* node) { if (node == NULL) return; while (node->next != NULL) { printf("%dx^%d", node->coeff, node->pow); node = node->next; if (node->next != NULL) printf(" + "); } } /* Function to print the required sum of a polynomial p1 and p2 as specified in output */ void addPolynomial(Node* p1, Node* p2) { map<int, int> mp; Node* temp1 = p1; Node* temp2 = p2; while (temp1 != NULL) { // Add coefficients of same power value // map contains (powervalue, coeff) pair mp[temp1->pow] += temp1->coeff; temp1 = temp1->next; } while (temp2 != NULL) { mp[temp2->pow] += temp2->coeff; temp2 = temp2->next; } // Started from the end because higher power should // come first and there should be "+" symbol in between // so iterate up to second element and print last out of // the loop. for (auto it = (mp.rbegin()); it != prev(mp.rend()); ++it) cout << it->second << "x^" << it->first << " + "; cout << mp.begin()->second << "x^" << mp.begin()->first; } // Driver function int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; // Create first list of 5x^2 + 4x^1 + 2x^0 create_node(5, 2, &poly1); create_node(4, 1, &poly1); create_node(2, 0, &poly1); // Create second list of 5x^1 + 5x^0 create_node(5, 1, &poly2); create_node(5, 0, &poly2); printf("1st Number: "); show(poly1); printf("\n2nd Number: "); show(poly2); poly = (struct Node*)malloc(sizeof(struct Node)); printf("\nAdded polynomial: "); // Function add two polynomial numbers addPolynomial(poly1, poly2); return 0; }
Producción:
1st Number: 5x^2 + 4x^1 + 2x^0 2nd Number: 5x^1 + 5x^0 Added polynomial: 5x^2 + 9x^1 + 7x^0
Complejidad de tiempo: O((m + n)log(m+n)) donde m y n son números de Nodes en la primera y segunda lista respectivamente y estamos usando un mapa para agregar los coeficientes extra log(m+n) factor es adicional.